CS205

HashMap

Explore HashMap operations with an interactive table view. See how keys are hashed, where they're stored, and how collisions are handled.

HashMap Operations

Enter a key-value pair and click Put

Size: 0
Capacity: 8
Load Factor: 0.00
Threshold: 6
IndexEntries (Key → Value)Hash Codes
0(empty)
1(empty)
2(empty)
3(empty)
4(empty)
5(empty)
6(empty)
7(empty)
Current Bucket
Current Entry
How put() Works
  1. Calculate the hash code of the key
  2. Compute bucket index: hash % capacity
  3. Search the bucket for existing key
  4. If found: update the value
  5. If not found: add new entry to bucket
  6. Check if rehashing is needed
Java Code
public V put(K key, V value) {
    int hash = key.hashCode();
    int index = hash % capacity;

    // Search for existing key
    for (Entry e : buckets[index]) {
        if (e.key.equals(key)) {
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }

    // Add new entry
    buckets[index].add(new Entry(key, value, hash));
    size++;

    // Check if rehashing needed
    if (size > threshold) {
        rehash();
    }
    return null;
}
Collision Handling: Chaining

When two keys hash to the same bucket index, we have a collision. Java's HashMap uses chaining to handle this — each bucket stores a linked list of entries.

Bucket[3]: "apple"→5 → "grape"→7 → "mango"→3

When searching, we traverse the chain comparing keys until we find a match or reach the end.

Impact on Performance

  • Best case: No collisions → O(1) access
  • Average case: Few collisions → O(1) access
  • Worst case: All keys in one bucket → O(n) access

A good hash function and appropriate load factor minimize collisions.