HashMap Implementation from Scratch in DSA Java - Deep Dive

Overview - HashMap Implementation from Scratch

What is it?

A HashMap is a data structure that stores key-value pairs. It allows quick access, insertion, and deletion of values based on their keys. Internally, it uses a hash function to convert keys into indexes for fast lookup. This topic teaches how to build a simple HashMap from the ground up.

Why it matters

Without HashMaps, programs would have to search through lists or arrays to find data, which is slow for large amounts of data. HashMaps make data retrieval almost instant, improving performance in many applications like databases, caches, and real-time systems. Understanding how they work helps you write efficient code and debug complex issues.

Where it fits

Before learning this, you should know arrays, linked lists, and basic programming concepts like classes and functions. After this, you can learn about advanced hashing techniques, collision resolution methods, and other map implementations like TreeMap or ConcurrentHashMap.

Mental Model

Core Idea

A HashMap uses a hash function to turn keys into array positions, storing values so they can be found quickly without searching everything.

Think of it like...

Imagine a library where books are stored by their unique code. Instead of searching every shelf, you use the code to find the exact shelf and spot where the book is kept instantly.

HashMap Structure:

[Array]
  ↓ Index from hash(key)
┌───────┬───────┬───────┬───────┐
│ 0     │ 1     │ 2     │ 3     │ ...
├───────┼───────┼───────┼───────┤
│ null  │ Entry │ Entry │ null  │
│       │  ↓    │  ↓    │       │
│       │ key1  │ key2  │       │
│       │ val1  │ val2  │       │
│       │  ↓    │  ↓    │       │
│       │ next  │ next  │       │
│       │ null  │ null  │       │
└───────┴───────┴───────┴───────┘

Build-Up - 7 Steps

1

Foundation

Understanding Key-Value Storage

Concept: Learn what key-value pairs are and why they are useful for storing data.

A key-value pair stores two linked pieces of information: a key (like a name) and a value (like a phone number). For example, in a phone book, the name is the key and the phone number is the value. This lets you find the phone number quickly if you know the name.

Result

You understand that data can be stored and retrieved by unique keys instead of searching through all data.

Knowing key-value pairs is the foundation for all map-like data structures, including HashMaps.

2

Foundation

Arrays as Storage Backbones

Concept: Learn how arrays provide fixed-size, indexed storage for data.

An array is a list of items stored in order, each with a number called an index. You can quickly access any item if you know its index. For example, in an array of size 5, the first item is at index 0, the second at 1, and so on.

Result

You understand how arrays allow fast access to data by index but require a way to convert keys into indexes.

Arrays provide the fast access needed for HashMaps but need a method to map keys to indexes.

3

Intermediate

Hash Functions for Indexing

🤔Before reading on: do you think a hash function always produces unique indexes for different keys? Commit to yes or no.

Concept: Introduce hash functions that convert keys into array indexes.

A hash function takes a key and returns a number (hash code). We then use this number to find an index in the array by using modulo operation (hashCode % arraySize). For example, if the hash code is 123 and array size is 10, the index is 3.

Result

You can convert any key into a valid array index to store or find its value.

Understanding hash functions is key to fast data retrieval but also introduces the challenge of collisions.

4

Intermediate

Handling Collisions with Linked Lists

🤔Before reading on: do you think two different keys can have the same index in a HashMap? Commit to yes or no.

Concept: Learn how collisions happen and how to resolve them using linked lists.

Sometimes, two keys produce the same index (collision). To handle this, each array slot holds a linked list of entries. When inserting, if the slot is empty, add the entry. If not, add it to the list. When searching, check each entry in the list for the matching key.

Result

You can store multiple key-value pairs at the same index safely.

Knowing collision handling prevents data loss and ensures correct retrieval even when keys clash.

5

Intermediate

Basic HashMap Operations Implementation

🤔Before reading on: do you think removing a key from a linked list in a HashMap is simpler or more complex than adding? Commit to your answer.

Concept: Implement put, get, and remove methods using hashing and linked lists.

Put: Compute index, check if key exists in list, update value or add new entry. Get: Compute index, search list for key, return value or null. Remove: Compute index, search list, remove entry if found. Example code snippet: class Entry { String key; int value; Entry next; Entry(String key, int value, Entry next) { this.key = key; this.value = value; this.next = next; } } Entry[] table = new Entry[10]; void put(String key, int value) { /* hash, find index, add/update */ } Integer get(String key) { /* hash, find index, search list */ return null; } void remove(String key) { /* hash, find index, remove from list */ }

Result

You can store, retrieve, and delete key-value pairs efficiently.

Implementing these operations solidifies understanding of how HashMaps work internally.

6

Advanced

Resizing and Rehashing the Table

🤔Before reading on: do you think a HashMap's array size stays fixed forever? Commit to yes or no.

Concept: Learn why and how to resize the internal array when it becomes too full.

When many entries fill the array, performance drops due to long linked lists. To fix this, we create a bigger array and re-insert all entries (rehashing). This spreads entries out and keeps operations fast. The threshold to resize is called load factor (e.g., 0.75).

Result

You understand how HashMaps maintain speed by resizing and redistributing entries.

Knowing resizing prevents performance degradation and explains why HashMaps sometimes slow down unexpectedly.

7

Expert

Optimizing HashMap with Better Hashing and Trees

🤔Before reading on: do you think linked lists are always the best way to handle collisions? Commit to yes or no.

Concept: Explore advanced collision handling using balanced trees and improved hash functions.

In Java 8+, when a linked list at an index grows too long, it converts into a balanced tree (like a red-black tree) for faster search. Also, better hash functions reduce collisions by spreading keys more evenly. These optimizations improve worst-case performance from linear to logarithmic time.

Result

You learn how modern HashMaps stay efficient even with many collisions.

Understanding these optimizations reveals how production HashMaps handle edge cases and maintain speed.

Under the Hood

A HashMap uses a hash function to convert keys into integer hash codes. These codes are then compressed into array indexes using modulo or bitwise operations. Each array slot holds a linked list or tree of entries to handle collisions. When inserting or searching, the HashMap computes the index, then traverses the list or tree to find the matching key. When the number of entries grows beyond a threshold, the internal array resizes and all entries are rehashed to new positions.

Why designed this way?

HashMaps were designed to provide average constant-time complexity for insertions, lookups, and deletions. Using arrays allows fast direct access, while linked lists handle collisions simply. Resizing keeps performance stable as data grows. Later, trees replaced lists for long collision chains to avoid slowdowns. Alternatives like balanced trees alone are slower on average, and open addressing has different tradeoffs, so chaining with resizing is a balanced choice.

HashMap Internal Flow:

Key -> Hash Function -> Hash Code -> Index Calculation -> Array Slot
  ↓
Collision?
  ↓ Yes -> Linked List / Tree Traversal -> Find Entry
  ↓ No -> Direct Access

Insertion:
  Compute index -> Add entry to list/tree -> Check load factor -> Resize if needed

Lookup:
  Compute index -> Search list/tree -> Return value or null

Removal:
  Compute index -> Search list/tree -> Remove entry if found

Myth Busters - 4 Common Misconceptions

Quick: Do you think a hash function guarantees unique indexes for different keys? Commit yes or no.

Common Belief: A hash function always produces a unique index for each key, so collisions never happen.

Reality: Hash functions can produce the same index for different keys, causing collisions that must be handled.

Why it matters: Ignoring collisions leads to data loss or incorrect retrieval, breaking the HashMap's correctness.

Quick: Do you think HashMaps keep their array size fixed after creation? Commit yes or no.

Common Belief: Once created, a HashMap's internal array size never changes.

Reality: HashMaps resize their internal array when the number of entries grows to maintain performance.

Why it matters: Without resizing, performance degrades as collisions increase, making operations slower.

Quick: Do you think removing a key from a HashMap is as simple as setting its slot to null? Commit yes or no.

Common Belief: To remove a key, just set the array slot to null.

Reality: Because of collisions, multiple entries may share a slot; removal requires searching and unlinking the correct entry.

Why it matters: Incorrect removal can delete unrelated entries or leave stale data, causing bugs.

Quick: Do you think linked lists are always the best way to handle collisions? Commit yes or no.

Common Belief: Linked lists are the only way to handle collisions in HashMaps.

Reality: Modern HashMaps switch to balanced trees for long collision chains to improve lookup speed.

Why it matters: Not knowing this can lead to inefficient implementations and poor performance in worst cases.

Expert Zone

1

The choice of hash function affects not just speed but also collision distribution, impacting overall performance.

2

Resizing is expensive but amortized; understanding this helps optimize when and how to resize in custom implementations.

3

Treeification of collision chains only happens after a threshold and when the array is large enough, balancing memory and speed.

When NOT to use

HashMaps are not ideal when order matters; use LinkedHashMap or TreeMap instead. For concurrent access, use ConcurrentHashMap. For small datasets or when memory is tight, simpler structures like arrays or lists may be better.

Production Patterns

In real systems, HashMaps are used for caches, symbol tables, and indexing. They often combine with other structures for thread safety or ordering. Java's HashMap uses treeification and resizing heuristics to maintain performance. Custom implementations tune load factors and hash functions based on expected data.

Connections

Bloom Filter

Both use hash functions to map data to positions in a structure.

Understanding HashMaps' hashing helps grasp Bloom Filters, which use multiple hashes to test membership probabilistically.

Database Indexing

HashMaps and database indexes both speed up data retrieval using keys.

Knowing HashMaps clarifies how indexes allow databases to find rows quickly without scanning entire tables.

Cache Memory in CPUs

Both use hashing and indexing to quickly locate data in limited storage.

Understanding HashMaps' indexing helps appreciate how CPU caches map memory addresses to cache lines for fast access.

Common Pitfalls

#1 Ignoring collisions and overwriting entries blindly.

Wrong approach:

void put(String key, int value) {
int index = hash(key) % table.length;
table[index] = new Entry(key, value, null); // overwrites existing entry
}

Correct approach:

void put(String key, int value) {
int index = hash(key) % table.length;
Entry current = table[index];
while (current != null) {
if (current.key.equals(key)) {
current.value = value; return;
}
current = current.next;
}
table[index] = new Entry(key, value, table[index]);
}

Root cause:

Not handling collisions by chaining causes data loss when entries share the same index.

#2 Not resizing the array when it becomes too full.

Wrong approach:

HashMap never increases array size regardless of entries count.

Correct approach:

if (size >= loadFactor * table.length) {
resize();
}

Root cause:

Ignoring load factor and resizing leads to long collision chains and slow operations.

#3 Removing entries by setting array slot to null without checking linked list.

Wrong approach:

void remove(String key) {
int index = hash(key) % table.length;
table[index] = null; // removes entire chain
}

Correct approach:

void remove(String key) {
int index = hash(key) % table.length;
Entry current = table[index], prev = null;
while (current != null) {
if (current.key.equals(key)) {
if (prev == null) table[index] = current.next;
else prev.next = current.next;
return;
}
prev = current;
current = current.next;
}
}

Root cause:

Not traversing the linked list causes removal of all entries at that index, not just the target.

Key Takeaways

HashMaps store data as key-value pairs using a hash function to find fast access positions.

Collisions happen when different keys map to the same position and must be handled carefully.

Resizing the internal array keeps operations fast as the number of entries grows.

Advanced HashMaps use balanced trees for long collision chains to maintain performance.

Understanding HashMaps deeply helps in writing efficient code and debugging complex data retrieval issues.

Practice

1. What is the main purpose of a HashMap in Java?

easy

A. To store key-value pairs for fast lookup

B. To store elements in sorted order

C. To store only unique values without keys

D. To store elements in a last-in-first-out order

Solution

1. Step 1: Understand HashMap functionality

   A HashMap stores data as key-value pairs allowing quick access by key.

2. Step 2: Compare with other data structures

   Unlike sorted or stack structures, HashMap focuses on fast lookup, not order or uniqueness of values alone.

3. Final Answer:

   To store key-value pairs for fast lookup -> Option A

4. Quick Check:

   HashMap = key-value fast access [OK]

Hint: HashMap = key-value pairs for quick access [OK]

Common Mistakes:

• Confusing HashMap with TreeMap (sorted)
• Thinking HashMap stores only unique values
• Mixing HashMap with stack or queue behavior

2. Which of the following is the correct way to declare a basic HashMap in Java from scratch?

easy

A. HashMap map = new HashMap<>();

B. HashMap<Integer> map = new HashMap<>();

C. HashMap map = new HashMap();

D. HashMap map = new HashMap();

Solution

1. Step 1: Check generic syntax for HashMap

   Java requires specifying key and value types inside angle brackets <Key, Value>.

2. Step 2: Identify correct generic declaration

   HashMap map = new HashMap(); uses full generic syntax for both declaration and instantiation, which is correct in Java before version 7.

3. Final Answer:

   HashMap map = new HashMap(); -> Option D

4. Quick Check:

   Full generic syntax = HashMap map = new HashMap(); [OK]

Hint: Use on both sides before Java 7 [OK]

Common Mistakes:

• Omitting generic types on instantiation (Option A is Java 7+ syntax)
• Using only one generic type (Option D is invalid)
• Not using generics at all (Option C is raw type)

3. Consider this simplified HashMap put method snippet from scratch:

public void put(K key, V value) {
  int index = key.hashCode() % capacity;
  if (buckets[index] == null) {
    buckets[index] = new Node(key, value);
  } else {
    Node current = buckets[index];
    while (current.next != null) {
      if (current.key.equals(key)) {
        current.value = value;
        return;
      }
      current = current.next;
    }
    current.next = new Node(key, value);
  }
}

What happens if we insert two keys with the same hashCode but different values?

medium

A. A runtime error occurs due to collision

B. The second key-value pair overwrites the first one

C. Both key-value pairs are stored in a linked list at the same bucket

D. Only the first key-value pair is stored, second is ignored

Solution

1. Step 1: Understand collision handling in code

   If bucket is occupied, code traverses linked nodes to check keys and appends new node if key not found.

2. Step 2: Analyze insertion of different keys with same hash

   Since keys differ but hash is same, new node is added at end of linked list, preserving both pairs.

3. Final Answer:

   Both key-value pairs are stored in a linked list at the same bucket -> Option C

4. Quick Check:

   Collision handled by chaining = Both key-value pairs are stored in a linked list at the same bucket [OK]

Hint: Same hash keys chain in linked list bucket [OK]

Common Mistakes:

• Assuming second key overwrites first without key match
• Thinking collision causes error
• Ignoring linked list chaining for collisions

4. Given this buggy put method snippet from a HashMap implementation:

public void put(K key, V value) {
  int index = key.hashCode() % capacity;
  if (buckets[index] == null) {
    buckets[index] = new Node(key, value);
  } else {
    Node current = buckets[index];
    while (current != null) {
      if (current.key.equals(key)) {
        current.value = value;
        return;
      }
      current = current.next;
    }
    current.next = new Node(key, value);
  }
}

What is the error in this code?

medium

A. The loop condition should be while (current.next != null) instead of while (current != null)

B. The hashCode modulo operation should use capacity - 1

C. The key comparison should use == instead of equals()

D. The new node is added before checking existing keys

Solution

1. Step 1: Analyze the while loop condition

   The loop runs while current != null, so after loop current becomes null.

2. Step 2: Check where new node is added

   After loop, code tries current.next = new Node(...), but current is null causing NullPointerException.

3. Step 3: Correct loop condition

   Changing loop to while (current.next != null) stops at last node, allowing safe addition at current.next.

4. Final Answer:

   The loop condition should be while (current.next != null) instead of while (current != null) -> Option A

5. Quick Check:

   Loop must stop at last node to add new node [OK]

Hint: Loop to last node, not null, to add new node safely [OK]

Common Mistakes:

• Using current != null causes NullPointerException on insertion
• Incorrect modulo operation for bucket index
• Using == instead of equals() for key comparison

5. You are implementing a HashMap from scratch with an array of buckets and linked lists for collisions. If the initial capacity is 4 and you insert keys with hashCodes: 2, 6, 10, 14, what will be the structure of the buckets after all insertions?

Assume bucket index = hashCode % capacity and each bucket holds a linked list of nodes.

Choose the correct bucket contents representation (keys only):

hard

A. Bucket 0: 2 -> 6 -> 10 -> 14Bucket 1: nullBucket 2: nullBucket 3: null

B. Bucket 0: nullBucket 1: nullBucket 2: 2 -> 6 -> 10 -> 14Bucket 3: null

C. Bucket 0: nullBucket 1: nullBucket 2: 2Bucket 3: 6 -> 10 -> 14

D. Bucket 0: nullBucket 1: nullBucket 2: 2 -> 6Bucket 3: 10 -> 14

Solution

1. Step 1: Calculate bucket index for each key

   Using index = hashCode % 4:
   2 % 4 = 2
   6 % 4 = 2
   10 % 4 = 2
   14 % 4 = 2

2. Step 2: Re-examine calculation carefully

   Actually:
   2 % 4 = 2
   6 % 4 = 2
   10 % 4 = 2
   14 % 4 = 2
   All keys map to bucket 2, so all should be in bucket 2 linked list.

3. Step 3: Check options for matching bucket 2 content

   Bucket 0: null
   Bucket 1: null
   Bucket 2: 2 -> 6 -> 10 -> 14
   Bucket 3: null shows all keys in bucket 2 linked list, which matches calculation.

4. Step 4: Verify other buckets are null

   Other buckets 0,1,3 are null as no keys map there.

5. Final Answer:

   Bucket 0: null
   Bucket 1: null
   Bucket 2: 2 -> 6 -> 10 -> 14
   Bucket 3: null -> Option B

6. Quick Check:

   All keys % 4 = 2, so bucket 2 holds all [OK]

Hint: Calculate hashCode % capacity for each key [OK]

Common Mistakes:

• Miscomputing modulo operation
• Distributing keys incorrectly across buckets
• Assuming keys spread evenly without modulo check