HashMap / HashTable / Dictionary

A HashMap is a data structure that allows you to store and manage key-value pairs. They are also called Hash Table or Dictionary (in python) data structure.

Unlike arrays or lists, where you access elements using an index, HashMaps let you use a “key” to find the corresponding “value.”

How Does HashMap Work?

A HashMap uses a technique called “hashing” to convert the key into an index in an array. If two keys have the same hash, they are stored in a linked list at the same index. This is called “collision resolution.”

What is Hashing?

In the context of HashMaps, hashing is the process of mapping the given key to the location where the key-value pair is stored. The key is passed through a hash function to generate an index where the corresponding value should be stored or retrieved.

Note that hashing has a different meaning in cryptography or security applications. Here we are discussing it in the context of HashMap only.

What is Collision in HashMap?

Collision occurs when two different keys hash to the same index in the array. Since two values can’t be stored in a single slot, we need a way to handle this scenario.

Collision Resolution Techniques

1. Separate Chaining: Each array slot contains a linked list. When a collision occurs, the new key-value pair is added to the end of the linked list at the colliding index.
2. Open Addressing: When a collision occurs, we look for the next available slot within the same array according to a probing sequence.
   • Linear Probing: Look for the next available slot in a linear sequence.
   • Quadratic Probing: Use a quadratic function to define the sequence to find the next slot.
   • Double Hashing: Use a secondary hash function to find the next slot.

These techniques aim to minimize collision and distribute keys uniformly across the hash table, thereby ensuring efficient operations.

Java Implementation

Let’s take a look at a simple implementation of a HashMap in Java.

public class MyHashMap<K, V> {
    private Entry<K, V>[] table;
    private int capacity = 16;

    static class Entry<K, V> {
        K key;
        V value;
        Entry<K, V> next;

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

    public MyHashMap() {
        table = new Entry[capacity];
    }

    // Put operation
    public void put(K newKey, V data) {
        int hash = hash(newKey);
        Entry<K, V> newEntry = new Entry<>(newKey, data);

        if (table[hash] == null) {
            table[hash] = newEntry;
        } else {
            Entry<K, V> previous = null;
            Entry<K, V> current = table[hash];
            while (current != null) {
                if (current.key.equals(newKey)) {
                    if (previous == null) {
                        newEntry.next = current.next;
                        table[hash] = newEntry;
                        return;
                    } else {
                        newEntry.next = current.next;
                        previous.next = newEntry;
                        return;
                    }
                }
                previous = current;
                current = current.next;
            }
            previous.next = newEntry;
        }
    }

    // Get operation
    public V get(K key) {
        int hash = hash(key);
        if (table[hash] == null) {
            return null;
        } else {
            Entry<K, V> current = table[hash];
            while (current != null) {
                if (current.key.equals(key)) {
                    return current.value;
                }
                current = current.next;
            }
            return null;
        }
    }

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

HashMap Operations and Their Time Complexity

1. Put (Insertion):
   • Average Time Complexity: O(1)
   • Worst-Case Time Complexity: O(n) due to collisions
2. Get (Retrieval):
   • Average Time Complexity: O(1)
   • Worst-Case Time Complexity: O(n) due to collisions

Applications of HashMap

1. Caching: Storing temporary data that’s expensive to fetch or compute.
2. Frequency Counting: Counting occurrences of items in an array or string.
3. Substring or Pattern Matching: Often used in text analytics or search algorithms.
4. Implementing Associative Arrays: Because of the key-value pair structure.
5. Database Indexing: HashMaps can be used to index large datasets, making retrieval operations faster.