DSA 0x106 - HashMap Data structure

Hash Map is another important data structure we need to know about. Lets say we have an array containing a million integers and we want to check whether a particular number exists. How can we do this?

If the array is sorted this would be an easy task. But if it is not? we have no other option. Need to itterate through the arrray checking wether the value we are checking is equal to the current one. That takes O(n) time.

For a small array, that's perfectly fine. But when the array contains millions of elements, repeatedly scanning everything can become expensive.

What if, instead of searching through the entire array, we could go directly to the location where the value should be?

That's the basic idea behind a hash table or Hash Map.

A hash table takes a key, converts it into an array index using a hash function, and uses that index to store or retrieve the associated value.

With a good hash function, lookup takes O(1) on average.

A simple way to think about it is a library.

Suppose books are placed randomly throughout a library. If we want to find a particular book, we may have to search shelf after shelf.

Now imagine every book has a rule that tells us exactly which shelf it belongs on. We can calculate the shelf from the book's name, walk directly there, and look for the book.

That's essentially what hashing does.

flowchart LR
    A["Key : 42"] --> B["Hash Function : 42 % 10"]
    B --> C["Index : 2"]
    C --> D["Array Bucket : [2]"]

What Is a Hash Function?

A hash function takes an input, usually called a key, and produces an integer called a hash value.

That value is then used to determine where the key-value pair should be stored.

For example, suppose our hash table has 10 slots. A very simple hash function for integers would be:

int hash(int key, int arraySize) {
    return key % arraySize;
}

If the key is 42 and the array contains 10 slots:

42 % 10 = 2

So we can store the value at index 2.

flowchart LR
    A["Key: 42"] --> B["42 % 10"]
    B --> C["Index: 2"]
    C --> D["Bucket 2"]

Real hash functions are usually more sophisticated than this.

Hashing Strings

For strings, we need to convert the characters into a numerical value.

One simple approach is to add the character values together:

int hash(String key, int arraySize) {
    int sum = 0;

    for (char c : key.toCharArray()) {
        sum += c;
    }

    return sum % arraySize;
}

Take a key, calculate a number from it, and use that number to determine an array index.

A good hash function should have two important properties:

• Deterministic : the same key should always produce the same hash value.
• Good distribution : keys should be spread across the available buckets as evenly as possible.

Good distribution is important because it reduces the number of collisions.

Building a Hash Table from Scratch

At its simplest, a hash table is just an array. Each position in the array is commonly called a bucket.

Let's build a very simple hash table in Java:

public class HashTable {
    private String[] keys;
    private String[] values;
    private int capacity;

    public HashTable(int capacity) {
        this.capacity = capacity;
        keys = new String[capacity];
        values = new String[capacity];
    }

    private int hash(String key) {
        int hashValue = 0;

        for (char c : key.toCharArray()) {
            hashValue = (hashValue * 31 + c) % capacity;
        }

        return hashValue;
    }

    public void put(String key, String value) {
        int index = hash(key);

        keys[index] = key;
        values[index] = value;
    }

    public String get(String key) {
        int index = hash(key);

        if (keys[index] != null && keys[index].equals(key)) {
            return values[index];
        }

        return null;
    }
}

The basic process is straightforward:

flowchart TD
    A["put(key, value)"] --> B["Calculate hash(key)"]
    B --> C["Convert hash to array index"]
    C --> D["Store key and value in bucket"]

    E["get(key)"] --> F["Calculate hash(key)"]
    F --> G["Convert hash to array index"]
    G --> H["Look in bucket"]
    H --> I["Return value"]

What happens when two different keys produce the same index?

The Collision Problem

Suppose our hash table has 10 buckets.

Lets say:

hash("Neumann")  = 3
hash("Shannon") = 3

Both keys want to use bucket 3.

That's called a collision.

flowchart LR
    A["Neumann"] --> H["Hash Function"]
    B["Shannon"] --> H
    H --> C["Bucket 10"]

    C --> D["Collision!"]

If our simple implementation simply writes the second value into bucket 10, it would overwrite the first value.

That's obviously not acceptable.

And collisions aren't something we can completely avoid. This is a consequence of the pigeonhole principle.

• If you have more possible keys than available buckets, multiple keys must eventually map to the same bucket.

• Even if there are fewer keys than buckets, a non-perfect hash function can still produce collisions.

So the real question isn't:

"How do we prevent collisions?"

It's:

"How do we handle collisions efficiently?"

There are two major approaches:

1. Chaining
2. Open addressing

Collision Resolution with Chaining

The most straightforward solution is chaining.

Instead of storing only one entry in each bucket, we store a collection of entries.

A common implementation uses a linked list.

For example:

flowchart LR
    A["Bucket 0"] --> A1["null"]
    B["Bucket 1"] --> B1["Ritchie: 25"]
    C["Bucket 2"] --> C1["null"]
    D["Bucket 3"] --> D1["Neumann: 5"]
    D1 --> D2["Shannon: 8"]
    E["Bucket 4"] --> E1["null"]
    F["Bucket 5"] --> F1["Turing: 3"]

Here, both "Neumann" and "Shannon" hash to bucket 3, so they are stored in the same chain.

When we want to retrieve "Shannon", we:

1. Calculate the hash of "Shannon".
2. Find bucket 3.
3. Walk through the entries in that bucket.
4. Compare the keys until we find "Shannon".

Here's a simple implementation:

import java.util.LinkedList;

public class ChainingHashTable<K, V> {

    private class Entry {
        K key;
        V value;

        Entry(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }

    private LinkedList<Entry>[] buckets;
    private int capacity;
    private int size;

    @SuppressWarnings("unchecked")
    public ChainingHashTable(int capacity) {
        this.capacity = capacity;
        this.size = 0;

        buckets = new LinkedList[capacity];

        for (int i = 0; i < capacity; i++) {
            buckets[i] = new LinkedList<>();
        }
    }

    private int hash(K key) {
        return Math.abs(key.hashCode()) % capacity;
    }

    public void put(K key, V value) {
        int index = hash(key);

        // Update the value if the key already exists.
        for (Entry entry : buckets[index]) {
            if (entry.key.equals(key)) {
                entry.value = value;
                return;
            }
        }

        // Otherwise, add a new entry.
        buckets[index].add(new Entry(key, value));
        size++;
    }

    public V get(K key) {
        int index = hash(key);

        for (Entry entry : buckets[index]) {
            if (entry.key.equals(key)) {
                return entry.value;
            }
        }

        return null;
    }

    public boolean remove(K key) {
        int index = hash(key);

        for (Entry entry : buckets[index]) {
            if (entry.key.equals(key)) {
                buckets[index].remove(entry);
                size--;
                return true;
            }
        }

        return false;
    }
}

Chaining is simple and works well as long as the number of entries in each bucket stays reasonably small.

But there's another approach.

Collision Resolution with Open Addressing

With open addressing, we don't create linked lists for the buckets.

Instead, every entry is stored directly inside the array.

When the preferred bucket is already occupied, we follow a probing strategy to find another empty bucket.

There are several probing strategies, including:

• Linear probing
• Quadratic probing
• Double hashing

Linear Probing

Linear probing is probably the easiest one to understand.

If bucket i is already occupied, we try:

i + 1
i + 2
i + 3
...

wrapping around to the beginning of the array when necessary.

For example:

hash("Neumann") = 3

Bucket 3 is empty, so we put "Neumann" there.

Then:

hash("Shannon") = 3

Bucket 3 is already occupied, so we try bucket 4.

If bucket 4 is empty, "Shannon" goes there.

flowchart LR
    A["Neumann"] --> B["hash = 3"]
    B --> C["Bucket 3"]
    C --> D["Empty → store Neumann"]

    E["Shannon"] --> F["hash = 3"]
    F --> G["Bucket 3"]
    G --> H["Occupied"]
    H --> I["Try Bucket 4"]
    I --> J["Empty → store Shannon"]

The array now looks like:

Index:    0     1     2       3        4        5
         [ ]   [ ]   [ ]   [Neumann]  [Shannon]   [ ]

A simple implementation looks like this:

public void put(String key, String value) {
    int index = hash(key);

    while (keys[index] != null) {

        if (keys[index].equals(key)) {
            values[index] = value;
            return;
        }

        index = (index + 1) % capacity;
    }

    keys[index] = key;
    values[index] = value;
}

The lookup operation follows the same probing sequence:

public String get(String key) {
    int index = hash(key);

    while (keys[index] != null) {

        if (keys[index].equals(key)) {
            return values[index];
        }

        index = (index + 1) % capacity;
    }

    return null;
}

The Problem with Linear Probing

Linear probing has a major drawback called primary clustering.

Once several entries end up next to each other, they form a cluster.

New entries that happen to hash near the cluster are likely to extend it.

Over time, the cluster can become larger and larger, increasing the number of probes required for future operations.

flowchart LR
    A["Cluster"] --> B["Neumann"]
    B --> C["Shannon"]
    C --> D["Ritchie"]
    D --> E["Turing"]
    E --> F["Ada"]

Quadratic Probing

Quadratic probing tries to reduce primary clustering.

Instead of checking the next bucket one at a time, we use a quadratic offset.

For example, the probe sequence might be:

i + 1
i + 4
i + 9
i + 16
...

In code:

int probe(int index, int attempt) {
    return (index + attempt * attempt) % capacity;
}

So if the original index is 3, we might check:

3 + 1² = 4
3 + 2² = 7
3 + 3² = 12
...

The exact sequence depends on the implementation and table size.

Quadratic probing reduces primary clustering, but it can still suffer from secondary clustering.

Secondary clustering happens when different keys have the same initial hash value and therefore follow the same probing sequence.

Double Hashing

Another approach is double hashing.

Instead of using a fixed probing pattern, we use a second hash function to determine how far we should move after a collision.

Conceptually:

index = hash1(key)

step = hash2(key)

next index = index + step

This generally provides a better distribution than linear or quadratic probing, but it is more complicated to implement correctly.

Load Factor and Rehashing

Another important concept in hash tables is the load factor.

The load factor tells us how full the hash table is.

It's calculated as:

load factor = number of entries / capacity

For example, if a hash table has 100 buckets and contains 75 entries:

load factor = 75 / 100
            = 0.75

As the load factor increases, collisions generally become more frequent.

That means operations can become slower.

flowchart LR
    A["Low Load Factor"] --> B["Fewer collisions"]
    B --> C["Faster operations"]

    D["High Load Factor"] --> E["More collisions"]
    E --> F["More probing / longer chains"]
    F --> G["Slower operations"]

A common rule of thumb is:

• Chaining: resize when the load factor goes above roughly 0.75.
• Open addressing: resize earlier, often around 0.5 to 0.7.

Java's HashMap uses 0.75 as its default load factor.

Rehashing

When the table becomes too full, we resize it.

Suppose we have a table with 10 buckets and decide to increase it to 20.

It might be tempting to simply copy the existing entries into the new array.

But that doesn't work.

Remember that the bucket index is calculated using the table's capacity.

For example:

50 % 10 = 0

But:

50 % 20 = 10

Therefore, after resizing, we need to calculate the new bucket for every entry.

This process is called rehashing.

flowchart TD
    A["Old Hash Table<br/>capacity = 10"] --> B["Resize"]
    B --> C["New Hash Table<br/>capacity = 20"]

    C --> D["Recalculate hash/index<br/>for every entry"]
    D --> E["Insert entries into new buckets"]

A simple implementation might look like this:

private void rehash() {
    int newCapacity = capacity * 2;

    LinkedList<Entry>[] oldBuckets = buckets;

    buckets = new LinkedList[newCapacity];
    capacity = newCapacity;
    size = 0;

    for (int i = 0; i < newCapacity; i++) {
        buckets[i] = new LinkedList<>();
    }

    for (LinkedList<Entry> bucket : oldBuckets) {
        for (Entry entry : bucket) {
            put(entry.key, entry.value);
        }
    }
}

Rehashing takes O(n) because every existing entry has to be processed.

However, resizing doesn't happen on every insertion. It happens only occasionally.

Because of that, the average cost of insertion remains O(1) amortized.

Java's HashMap and HashSet

Fortunately, we usually don't need to implement a hash table ourselves.

Java provides HashMap<K, V> in java.util.

It's one of the most commonly used data structures in Java.

For example:

import java.util.HashMap;

HashMap<String, Integer> map = new HashMap<>();

map.put("alice", 90);
map.put("bob", 85);

int score = map.get("alice");          // 90
boolean exists = map.containsKey("bob"); // true

map.remove("bob");

The basic idea is exactly what we've discussed:

flowchart LR
    A["map.get(\"alice\")"] --> B["hashCode(\"alice\")"]
    B --> C["Find bucket"]
    C --> D["Compare key"]
    D --> E["Return value"]

Java's HashMap implementation has several optimizations.

For example:

• It uses an array of Node objects.
• Each node contains information such as the key, value, hash, and a reference to the next node.
• Its default initial capacity is 16.
• Its default load factor is 0.75.
• When a bucket becomes sufficiently large, Java can convert the bucket's linked structure into a red-black tree, improving lookup performance for heavily-colliding buckets.
• The table grows when the number of entries reaches the resize threshold.

This tree-based optimization was introduced in Java 8.

When Should You Not Use a Hash Table?

Hash tables are incredibly useful, but they aren't the best data structure for every problem.

You Need Ordered Data

Hash tables are designed around fast lookup, not ordering.

If you need keys to remain sorted, a TreeMap may be a better choice.

TreeMap is based on a red-black tree and provides O(log n) operations while maintaining sorted order.

You Need Range Queries

Suppose you need to answer:

"Give me all keys between 10 and 50."

That's a natural operation for a sorted data structure.

A hash table isn't designed for this.

A balanced search tree or sorted array is much more appropriate.

Memory Is Limited

Hash tables trade memory for speed.

They need space for:

• The bucket array
• Entries
• References
• Collision-resolution structures
• Unused capacity maintained to keep the load factor reasonable

For some workloads, an array or another data structure can use memory more efficiently.

Computing the Hash Is Expensive

Hashing isn't literally free.

If calculating the hash of a key is expensive, the practical benefit of O(1) lookup may be smaller.

This is especially relevant when keys are large or complicated objects.

You Need Strict Worst-Case Guarantees

Hash tables generally provide excellent average-case performance, but their traditional complexity guarantees aren't as strong as those of balanced search trees.

If your application requires predictable O(log n) worst-case behavior, a balanced tree may be a better choice.

This can matter in systems where predictable latency is more important than average throughput.

The Dataset Is Very Small

For very small collections, hashing may simply not be worth the overhead.

If you have five or ten elements, a simple array scan can be surprisingly competitive because arrays have excellent cache locality and very little overhead.

Big-O notation doesn't always tell the whole performance story.

Putting It All Together

The core idea behind a hash table is actually quite simple:

flowchart TD
    A["Key"] --> B["Hash Function"]
    B --> C["Bucket Index"]
    C --> D["Store / Find Entry"]

    D --> E{"Collision?"}
    E -->|No| F["Done"]
    E -->|Yes| G["Collision Resolution"]

    G --> H["Chaining"]
    G --> I["Open Addressing"]

A hash table essentially trades memory for speed.

Instead of scanning through a collection every time we need to find something, we spend additional memory on an array of buckets and use a hash function to jump close to the data we want.

Collisions are unavoidable, so we need a strategy for dealing with them.

The two major approaches are:

• Chaining — keep multiple entries in the same bucket.
• Open addressing — find another empty bucket using a probing strategy.

As the table becomes full, we increase its capacity and rehash the existing entries.

In Java, HashMap and HashSet provide highly optimized implementations of these ideas.

And when you're working with custom objects, remember one particularly important rule:

If two objects are equal according to equals(), they must have the same hashCode().