The Major Parts Within HashMap
- Initial Capacity: This is the default size of the array in Java (16).
- Load Factor: A loading at which point it chooses to increase the size of the array (defaults to 0.75).
- Threshold: At some point the number of entries is more than (capacity * load factor) two sets will be made from the HashMap which reduces the collisions.
Hashing of HashMap
The ability to find out any element within the HashMap quickly is due to hashing. Once you add a key-value pair, that information does not go at random positions in Java: in fact, Java determines the index in which that entry needs to be inserted into the array. This computation occurs through hash code() method.
Operation of Hashing Hashing takes advantage of the fact that the time it takes to search through a list of words is quite long, but the time to compare two words against each other is but a moment.
The idea of Hashing is; using an appropriately formed list of words as an index in which the words that each person wants to find are stored in some order.
As one of these words is found, a check is made to see whether the word sought has the same hash number as the word found. If these two are the same, then the word is found; otherwise a search must be made through the list or index
- Step 1: Increment hashCode() of the key (e.g. Alice).
- Step 2: Reformat the hash to minimise collisions (Java has an internal scrambling method).
- Step 3: Stating the index as follows:
index = hashCode(key) & (arrayLength -1)
(& operation keeps the index in the array.)
by Example: hashCode() in Action
public class HashingExample {
public static void main(String[] args) {
String key = "Alice";
int hashCode = key.hashCode(); // Returns a large integer (e.g., 123456789)
int arrayLength = 16; // Default HashMap size
int index = hashCode & (arrayLength - 1); // Calculates bucket position
System.out.println("HashCode: " + hashCode);
System.out.println("Index: " + index); // Output: e.g., 5
}
}
You can also try this code with Online Java Compiler
Output:
HashCode: 123456789
Index: 5
In this code:
- "A unique integer is produced by Alice.hashCode().
- & (arrayLength - 1) ensures the index fits within the array (e.g., 0 to 15 for size 16).
Hashing is important because
- Fast Lookups: Directly computes where the key should be stored.
- Collisions: Different keys may land in the same bucket (e.g., "Alice" and "Bob" could have the same index). We’ll handle collisions later.
The Reason behind Hashing
- Fast Lookups: Straight away calculates where the key must go.
- Collisions: A different key can come in the same bucket (for example, there is a possibility that Alice and Bob have same index). Crash of collisions we shall have to do with afterwards.
equals() Method of HashMap
The equals () methods are significant in the HashMaps in cases where two keys have two different keys, yet it has the same hash code(collision). It assists HashMap in deciding whether two keys are really the same or they merely resulted with same hash value.
The Function of equals() to HashMap
- When put(key, value) or get(key) is called, HashMap:
- First finds the bucket using a hash code check
- Then compares keys in this bucket using equals()
When the returns of equals() are true, then two keys are regarded as the same by HashMap and the old value is discarded (while putting) or matched value is given back (while getting).
An example: Action equals()
class Student {
String id;
String name;
public Student(String id, String name) {
this.id = id;
this.name = name;
}
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Student student = (Student) o;
return id.equals(student.id);
}
@Override
public int hashCode() {
return id.hashCode();
}
}
public class EqualsExample {
public static void main(String[] args) {
HashMap<Student, String> studentCourses = new HashMap<>();
Student s1 = new Student("S001", "Alice");
Student s2 = new Student("S001", "Alice");
studentCourses.put(s1, "Computer Science");
System.out.println("Course for s2: " + studentCourses.get(s2)); // Output: Computer Science
}
}
Output:
Course for s2: Computer Science
Key Points:
- Even though s1 and s2 are different objects, they're considered equal because:
- Their hashCode() values are same (based on same ID)
- equals() returns true (compares only ID field)
- Without proper equals() and hashCode(), s2 wouldn't find s1's value
- The contract between equals() and hashCode() is crucial:
- If two objects are equal, they must have same hash code
- But same hash code doesn't guarantee equality
Some Common Mistakes to be Avoided
- During overriding hashCode() failure to override equals()
- Reliance upon mutable fields (can make entries lost) in making equals()
- Failure to observe the equals()-hashCode() contract
Why It is Important
- Makes sure to do right things when storing custom objects as keys
- Avoids the repetition of the keys in the HashMap
- Influences execution (bad equals() can slow lookups down)
Buckets in Hashmap
Buckets resemble small containers within a HashMap where Java holds your key value pairs. Consider these to be the drawers in a filing cabinet - in each drawer there are a number of files (entries) but with the key (hash code) you have a quick way of locating the appropriate drawer.
Buckets Working Process
The HashMap possesses an array (suppose default is 16)
- An array location is referred to as a bucket owing to the bucket idea.
- Your addition of the entry:
- The key is hashed in Java to determine the number of the bucket
- Save the entry on that bucket
Visual Representation
Bucket 0: Empty
Bucket 1: [Key1=Value1] → [Key5=Value5] (linked list)
Bucket 2: Empty
Bucket 5: [Key3=Value3]
Bucket 15: Empty
Example: Seeing Buckets
public class BucketExample {
public static void main(String[] args) {
HashMap<String, Integer> map = new HashMap<>(16); // Explicitly set capacity
// These keys will land in same bucket (for demonstration)
map.put("Aa", 1); // Hash code 2112
map.put("BB", 2); // Hash code 2112 (collision)
System.out.println("Map size: " + map.size()); // 2 entries
System.out.println("Value for Aa: " + map.get("Aa")); // 1
System.out.println("Value for BB: " + map.get("BB")); // 2
}
}
You can also try this code with Online Java Compiler
Output:
Map size: 2
Value for Aa: 1
Value for BB: 2
In this code:
- Both, Aa and BB share a common hash code (2112)
- They fall into same bucket (in this case bucket 4)
- The bucket holds them up, in a linked-list form:
Bucket 4: ["Aa"=1] → ["BB"=2]
You can also try this code with Online Java Compiler
Interesting Data about Buckets
Bucket conversion to tree: If bucket is too full, starting with Java 8 and above, builds tree instead of a linked list at its arms length (8 by default)
- compute Bucket Index: the index of the bucket being used is computed using (hashCode modulo numberOfBuckets)
- Empty Buckets: Accept a memory almost nothing (just a null pointer)
The Rationale of the Need to Have Buckets:
- They help in organizing entries that can easily be searched up
- Elegantly handle collision (more than 1 key in identical bucket)
- The lesser the buckets the fewer the collisions are
HashMap Calculation of Index
The way in which HashMap determines which bucket your key-value pair is going to be in is via index calculation. It is like a one second math trick that reduces any key to the number of a particular bucket.
Operation of Index Calculation
The first way is to obtain the hash code of a key by calling hashCode() method
Then hashs Object your hash to minimize chances of a collision (HashMap does it internally)
At last, apply the following formula:
index = (table.length - 1) & hash
You can also try this code with Online Java Compiler
(The & is a bitwise AND operation that's faster than modulo)
Simple Example
Let's say we have:
- Table size: 16 (default)
- Key: "apple"
- "apple".hashCode(): 93029210
Calculation:
- Internal scrambling of 93029210 → let's say becomes 1234
- index = (16 - 1) & 1234
- 15 in binary: 1111
- 1234 in binary: 10011010010
- 1111 & 10011010010 = 0010 (which is 2 in decimal)
So "apple" goes to bucket 2.
Complete Code Example
public class IndexCalculation {
public static void main(String[] args) {
String key = "apple";
int capacity = 16; // Default HashMap size
int hash = key.hashCode();
// Scramble the hash (similar to HashMap's internal implementation)
int scrambledHash = hash ^ (hash >>> 16);
int index = (capacity - 1) & scrambledHash;
System.out.println("Key: " + key);
System.out.println("Hash code: " + hash);
System.out.println("Scrambled hash: " + scrambledHash);
System.out.println("Bucket index: " + index);
}
}
You can also try this code with Online Java Compiler
Possible Output:
Key: apple
Hash code: 93029210
Scrambled hash: 93029210
Bucket index: 10
This helps in:
- Fast Calculation: Bitwise operations are super fast
- Even Distribution: Helps spread keys across buckets
- Handles Table Resizing: When HashMap grows, it recalculates indexes
Special Cases
- Null Key: Always goes to bucket 0
- Same Hash Codes: Different keys with same hash go to same bucket (collision)
Key Points to Remember:
- The calculation is designed to be extremely fast
- Table size is always a power of two (16, 32, 64...) for this to work
- Better hash codes lead to better distribution
Internal Working of put() Method in HashMap
When you call put(key, value), HashMap performs a carefully choreographed sequence of operations to store your data efficiently. Let's understand this in step by step manner.
Step-by-Step Process of put()
- Hash Calculation
- First, HashMap calculates the hash of your key using hashCode()
- Then it applies an internal scrambling function to prevent clustering
2. Index Determination
index = (n - 1) & hash // Where n is current table size
3. Bucket Inspection
- Checks if the bucket at calculated index is empty
- If empty, creates a new node and stores the entry
- If not empty, handles collision
4. Collision Handling
For Java 8+:
- If bucket has < 8 nodes: stores in linked list
- If bucket has ≥ 8 nodes: converts to balanced tree
- For existing keys: replaces old value with new value
5. Size Check
- If current size exceeds threshold (capacity × load factor), resizes table
Complete put() Operation Example
public class PutMethodDemo {
public static void main(String[] args) {
HashMap<String, Integer> priceMap = new HashMap<>(4); // Small capacity for demo
// Will show different bucket placements
priceMap.put("Laptop", 999);
priceMap.put("Phone", 699);
priceMap.put("Tablet", 399);
priceMap.put("Laptop", 1099); // Update existing
// Force collision
priceMap.put("Aa", 1); // Hash 2112
priceMap.put("BB", 2); // Hash 2112
System.out.println("Final Map: " + priceMap);
}
}
You can also try this code with Online Java Compiler
Sample Output:
Final Map: {BB=2, Tablet=399, Phone=699, Aa=1, Laptop=1099}
Visualizing the Process
- For put("Laptop", 999):
- Calculate hash for "Laptop"
- Determine bucket index (e.g., index 2)
- If bucket empty, create new node
- If updating existing key, replace value
For put("Aa", 1) and put("BB", 2) (collision case):
- Both keys have same hash (2112)
- Both go to same bucket (e.g., index 3)
- Stored as linked list: ["Aa"=1] → ["BB"=2]
Key Technical Details
- Node Structure: Each entry stores:
class Node<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next; // For chaining
}
- Tree Conversion: When list length > 8, converts to tree (TreeNode)
- Value Replacement: If key exists, returns old value
Internal Working of get() Method in HashMap
The get() method is how HashMap retrieves your values lightning-fast. Let’s see exactly what happens when you call map.get(key):
Step-by-Step Retrieval Process:
1. Hash Calculation
hash = key.hashCode() ^ (key.hashCode() >>> 16) // Scramble the hash
2. Bucket Location
index = (table.length - 1) & hash // Same calculation as put()
3. Bucket Examination
- First checks if bucket is empty → returns null
- If bucket has one node → checks if key matches
- If bucket has multiple entries → searches through them
4. Key Matching Logic
- First compares hash values (fast check)
- Then uses equals() for exact match
- For tree nodes, performs tree traversal (O(log n))
Complete get() Example
public class GetMethodDemo {
public static void main(String[] args) {
HashMap<String, Double> productPrices = new HashMap<>();
productPrices.put("Mouse", 19.99);
productPrices.put("Keyboard", 49.99);
productPrices.put("Monitor", 199.99);
// Normal retrieval
System.out.println("Mouse price: " + productPrices.get("Mouse"));
// Collision case (using same hash strings)
productPrices.put("Aa", 1.0);
productPrices.put("BB", 2.0);
System.out.println("BB value: " + productPrices.get("BB"));
// Non-existent key
System.out.println("Speaker price: " + productPrices.get("Speaker"));
}
}
You can also try this code with Online Java Compiler
Output
Mouse price: 19.99
BB value: 2.0
Speaker price: null
What Happens During Collisions
For our collision keys ("Aa" and "BB"):
1. Both have same hash → same bucket
2. get("BB") will:
- Find the bucket
- Traverse the linked list/tree
- Compare keys using equals()
- Return matching value
Performance Implications
- Best Case: O(1) - Direct bucket access, no collisions
- Worst Case: O(n) - All keys in one bucket (linked list)
- Java 8+ Improvement: O(log n) when converted to tree
Frequently Asked Questions
Why is both hashCode() and equals() used by HashMap?
HashMap has first hashCode() to find the bucket quickly. In case more than one key hits the same bucket, then it will seek the equality using equals(). This is a two-step trick, which makes lookups quick, and and error-free.
What will occur when HashMap becomes cluttered?
At a point when the number of entries exceeds multiple of the capacity by the load factor, HashMap resizes itself twice and rehashes each of its entries. This prevents over-crowding of buckets and allows performance.
Why is java 8 using trees to collision?
In cases of buckets that contained numerous collisions, look up operations by linked lists would have been slow (O(n)). Java supports a fast implementation by converting to trees (O(log n)) and continues to perform well in the presence of bad hash functions or a denial-of-service attack.
Conclusion
We have learned the working of HashMap in Java in this article. We began with simple version of its structure with buckets and explained how hashing defines where to store its entries. We have looked at importance of the equals() and hashCode() functions in solving collisions. We got an insight on how the put() method computes indexes, collisions and resizing of the table as required. Lastly, we discussed the attribute of the get() method that retrieves vales effectively through the same hashing mechanism.
7+ registered 
