February 23, 2025

How Hash Code is Computed/ Working

Great question! Let’s clarify how the **hash code** is actually computed in Java and how it is used in a `HashMap`. The hash code is not…

By Imrankhan

3 min read

Great question! Let's clarify how the hash code is actually computed in Java and how it is used in a HashMap. The hash code is not something we assume — it is computed by the hashCode() method, which is defined in the Object class and can be overridden by specific classes (like String, Integer, etc.).

— -

How Hash Code is Computed

  1. Default hashCode() Method: — The Object class provides a default implementation of the hashCode() method. — This default implementation typically converts the memory address of the object into an integer (not guaranteed, but commonly implemented this way). — Example:

Object obj = new Object(); int hash = obj.hashCode(); // Returns a hash code based on the object's memory address


> 2. **Overridden `hashCode()` Method**:
— Many classes in Java (like `String`, `Integer`, etc.) override the `hashCode()` method to provide a meaningful hash code based on the object's content.
— For example:
— **String**: The hash code of a `String` is computed based on its characters.
— **Integer**: The hash code of an `Integer` is simply its integer value.

> — -

> ### **How `HashMap` Uses the Hash Code**

> When you insert a key-value pair into a `HashMap`, the following steps occur:

> 1. **Compute the Hash Code**:
— The `hashCode()` method of the key is called to compute the hash code.
— Example:

String key = "Alice";
int hash = key.hashCode(); // Returns a hash code based on the characters in "Alice"
  1. Adjust the Hash Code: — The HashMap internally applies a supplemental hash function to the hash code to further reduce collisions. This is done using the following formula:

hash = key.hashCode() ^ (key.hashCode() >>> 16)

— This step ensures that the higher bits of the hash code are also considered in the index calculation.

> 3. **Compute the Index**:
— The adjusted hash code is used to compute the index in the array using:

index = (n — 1) & hash

— n is the capacity of the array (number of buckets). — & is the bitwise AND operator.

— -

Example: Hash Code Calculation for a String

Let's take the key "Alice" and compute its hash code step by step.

  1. Compute hashCode() for "Alice": — The String class overrides the hashCode() method to compute the hash code based on the characters in the string. — The formula for String.hashCode() is:
s[0]*31^(n-1) + s[1]*31^(n-2) + … + s[n-1]

— s[i] is the i-th character of the string. — n is the length of the string. — ^ denotes exponentiation.

  • For "Alice":
A = 65, l = 108, i = 105, c = 99, e = 101
hashCode = 65 * 31⁴ + 108 * 31³ + 105 * 31² + 99 * 31¹ + 101 * 31⁰
hashCode = 65 * 923521 + 108 * 29791 + 105 * 961 + 99 * 31 + 101 * 1
hashCode = 60028265 + 3217428 + 100905 + 3069 + 101
hashCode = 63306768
  1. Adjust the Hash Code: — Apply the supplemental hash function:
hash = 63306768 ^ (63306768 >>> 16)

— 63306768 >>> 16 shifts the bits of 63306768 16 places to the right:

63306768 in binary: 00000011 11000101 10100010 10010000
After >>> 16: 00000000 00000000 00000011 11000101

— Perform XOR (^) operation:

00000011 11000101 10100010 10010000
^ 00000000 00000000 00000011 11000101
— — — — — — — — — — — — — — — — — —
00000011 11000101 10100001 01010101

— The adjusted hash is 63306765.

  1. Compute the Index: — Assume the capacity (n) is 16. — Compute the index:
index = (16–1) & 63306765
index = 15 & 63306765

— Binary representation of 15: 00001111. — Binary representation of 63306765: 00000011 11000101 10100001 01010101. — Perform bitwise AND (&):

00001111
& 00000011 11000101 10100001 01010101
— — — — — — — — — — — — — — — — — —
00000101 (5 in decimal)

— The index is 5.

— -

Dry Run with Real Hash Codes

Let's perform a dry run with the following key-value pairs:

  • ("Alice", 25)
  • ("Bob", 30)
  • ("Charlie", 35)

Step 1: Initialize HashMap

  • Capacity (n) = 16.
  • Load factor = 0.75.
  • Threshold = 16 * 0.75 = 12.

Step 2: Insert ("Alice", 25)

  1. Compute hash code for "Alice": — hashCode("Alice") = 63306768.
  1. Adjust the hash code: — hash = 63306768 ^ (63306768 >>> 16) = 63306765.
  1. Compute index: — index = (16–1) & 63306765 = 5.
  1. Insert at index 5: — Bucket at index 5 is empty, so a new node is created:
Node(hash=63306765, key="Alice", value=25, next=null)

Step 3: Insert ("Bob", 30)

  1. Compute hash code for "Bob": — hashCode("Bob") = 2070756.
  1. Adjust the hash code: — hash = 2070756 ^ (2070756 >>> 16) = 2070756.
  1. Compute index: — index = (16–1) & 2070756 = 4.
  1. Insert at index 4: — Bucket at index 4 is empty, so a new node is created:
Node(hash=2070756, key="Bob", value=30, next=null)

Step 4: Insert ("Charlie", 35)

  1. Compute hash code for "Charlie": — hashCode("Charlie") = -204629542.
  1. Adjust the hash code: — hash = -204629542 ^ (-204629542 >>> 16) = -204629542.
  1. Compute index: — index = (16–1) & -204629542 = 10.
  1. Insert at index 10: — Bucket at index 10 is empty, so a new node is created:
Node(hash=-204629542, key="Charlie", value=35, next=null)

— -

Final HashMap Structure

After the above operations, the HashMap looks like this:

Index 0–3: null Index 4: Node("Bob", 30) -> null Index 5: Node("Alice", 25) -> null Index 6–9: null Index 10: Node("Charlie", 35) -> null Index 11–15: null


> — -

> ### **Key Takeaways**
1. The `hashCode()` method is used to compute the hash code of the key.
2. The `HashMap` adjusts the hash code to reduce collisions.
3. The index is computed using `(n — 1) & hash`.
4. Collisions are handled using linked lists or trees.

> This step-by-step explanation and dry run should give you a clear understanding of how hash codes are computed and used in a `HashMap`!