Hash Tables
A Hash Table (or Hash Map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
1. The Concept
- Hash Function: A function that takes an input (key) and returns an integer (hash code). Ideally, it distributes keys uniformly across the array.
- Index:
index = hash_code % array_size.
Ideally, the hash function assigns each key to a unique bucket, but most hash table designs employ an imperfect hash function, which might cause hash collisions.
2. Collisions
A Collision occurs when two different keys hash to the same index. Since the array size is finite and the set of possible keys is infinite, collisions are inevitable (Pigeonhole Principle).
3. Collision Resolution Strategies
There are two main ways to handle collisions:
Separate Chaining
Each bucket is independent, and has some sort of list of entries with the same index. The time for hash table operations is the time to find the bucket (constant) plus the time for the list operation.
- Structure: Each slot in the array points to a Linked List (or another data structure like a Tree).
- Insertion: Add the new key-value pair to the list at that index.
- Pros: Simple to implement; hash table never fills up (just grows the lists).
- Cons: Uses extra memory for links; cache performance is poor due to pointers.
Open Addressing
All entry records are stored in the bucket array itself. When a new entry has to be inserted, the buckets are examined, starting with the hashed-to slot and proceeding in some probe sequence, until an unoccupied slot is found.
- Linear Probing: If index
iis full, tryi+1, theni+2, etc.- Issue: Primary Clustering (long runs of occupied slots).
- Quadratic Probing: If index
iis full, tryi + 1²,i + 2²,i + 3²... - Double Hashing: Use a second hash function to determine the step size.
index = (hash1(key) + i * hash2(key)) % size.
4. Time Complexity
| Operation | Average | Worst Case |
|---|---|---|
| Search | $O(1)$ | $O(n)$ |
| Insert | $O(1)$ | $O(n)$ |
| Delete | $O(1)$ | $O(n)$ |
- Average Case: Very fast. Depends on a good hash function and low Load Factor.
- Worst Case: Occurs when all keys hash to the same index (e.g., creating a single long linked list).
5. Load Factor and Resizing
The Load Factor ($\alpha$) is defined as: $$ \alpha = \frac{\text{Number of Entries}}{\text{Number of Buckets}} $$
- Resizing: When the load factor exceeds a threshold (e.g., 0.75), the hash table creates a new, larger array (usually double the size) and rehashes all existing items into the new array. This is an expensive $O(n)$ operation but amortized over time.
programming/dictionaries-and-maps programming/arrays-and-lists programming/algorithms