Back to DSA Course

A hash table is a data structure that provides fast insertion, deletion, and lookup of key/value pairs.

Under the hood, a hash table uses an array of buckets to store key/value pairs. When inserting a key/value pair, a hash function maps the key — which is typically a string or any hashable type — to an integer value and, by extension, to an index in the underlying array. The value associated with the key is stored at that bucket, along with a reference to the key itself (needed to resolve collisions and for equality checks).

Hash tables rely on well-designed hash functions to distribute keys as uniformly as possible across the array and minimize collisions — cases where two different keys hash to the same index.

Collision Resolution

Two main strategies are used in practice:

• Separate Chaining: Each bucket holds a linked list (or other collection) of all key/value pairs that hashed to that index. On lookup, the hash function identifies the bucket, then the list is traversed to find the matching key. Java's HashMap used pure linked lists until Java 8, when it switched to tree buckets (red-black trees) for any bucket exceeding 8 entries, giving O(log n) worst-case lookup per bucket instead of O(n). This is an important implementation detail — the "linked list of collisions" description is accurate for the common case but not complete for modern Java.

• Open Addressing: All key/value pairs are stored directly in the array. On a collision, a probing sequence (linear probing, quadratic probing, double hashing) finds the next available slot. More cache-friendly than chaining since data is in a contiguous array, but requires careful handling of deletions.

Below is an example of how a hash table looks using separate chaining:

[
    0: (value1, key1) -> null
    1: (value2, key2) -> (value3, key3) -> (value4, key4)
    2: (value5, key5) -> null
    3: (value6, key6) -> null
    4: null
    5: (value7, key7) -> (value8, key8)
    6: (value9, key9) -> null
]

In this example, key2, key3, and key4 all collided (hashed to index 1), and key7 and key8 both hashed to index 5.

Load Factor and Resizing

The load factor is the ratio of entries to the number of buckets. When the load factor exceeds a threshold (Java's HashMap uses 0.75 by default), the table is resized — a new, larger array is allocated and all existing entries are rehashed into it. This keeps the average chain length short and O(1) average performance intact. Resizing is O(n) but happens infrequently enough that amortized insertion is still O(1).

Hash Table Operations

Operation | Average | Worst Case
----------|---------|-----------
Insert    | O(1)    | O(n)
Delete    | O(1)    | O(n)
Lookup    | O(1)    | O(n)

The worst case O(n) occurs when the hash function distributes all keys to the same bucket (e.g., all keys have the same hash code), creating a single chain of length n. In practice, with a good hash function and reasonable load factor, this is extremely rare and operations are effectively constant time.

Hash Tables in Java

Java provides several hash table implementations:

• HashMap: General-purpose, permits one null key, not thread-safe, O(1) average for all operations.
• LinkedHashMap: Maintains insertion order (or access order if configured) via a doubly-linked list through entries.
• TreeMap: A sorted map backed by a red-black tree — O(log n) for all operations but keys are always iterated in sorted order. Technically not a hash table.
• Hashtable (legacy): Synchronized version of HashMap. Mostly superseded by ConcurrentHashMap for thread-safe use.
• ConcurrentHashMap: Thread-safe HashMap with better concurrent throughput than Hashtable by using segment-level (Java 7) or node-level (Java 8+) locking.

Common Use Cases

• Caching and memoization (store computed results keyed by input)
• Counting frequencies (e.g., character counts in a string)
• Fast deduplication
• Implementing sets (HashSet is backed by HashMap)
• Index structures for lookup by arbitrary keys