Hash Table
A hash table is a data structure that stores key-value pairs and supports average O(1) insertion, deletion, and lookup. It achieves this by using a hash fu...
Structure and Operations
A hash table is a data structure that stores key-value pairs and supports average O(1) insertion, deletion, and lookup. It achieves this by using a hash function to map each key to an index in an underlying array, called the bucket array or slot array. The key is stored (or a reference to it is stored) along with its associated value at the computed bucket.
The basic operations work as follows. To insert a key-value pair, compute the hash of the key, find the corresponding bucket, and store the pair there. To look up a key, compute its hash to find the bucket and then retrieve the associated value. To delete a key, compute its hash, find the bucket, and remove the entry.
The load factor of a hash table is the ratio of the number of stored entries to the total number of buckets. A load factor of 0.7 means 70 percent of buckets are occupied. As the load factor increases, the probability of collisions increases and performance degrades. Most hash table implementations maintain the load factor below a threshold, typically between 0.5 and 0.75, by resizing the bucket array when the threshold is exceeded.
Resizing doubles the bucket array and rehashes every existing entry into the new array. A single resize operation takes O(n) time, but since it happens infrequently (after n insertions), its amortized cost per insertion is O(1). This is analogous to dynamic array growth.
A worked example: a hash table with 7 buckets stores the key-value pairs. Inserting the key Alice: hash(Alice) modulo 7 gives bucket 3. Inserting Bob: hash(Bob) modulo 7 gives bucket 5. Inserting Carol: hash(Carol) modulo 7 gives bucket 1. Looking up Alice computes hash(Alice) modulo 7, goes to bucket 3, and returns the associated value in O(1).
Time complexity: O(1) average for insert, lookup, and delete. O(n) worst case when all keys hash to the same bucket. Space complexity: O(n).
Interview tip: always mention the load factor and resizing when describing hash tables. A hash table without resizing degrades to O(n) performance as it fills up, and interviewers test whether candidates understand this fundamental aspect of the data structure.
Implementing a Hash Table from Scratch
Implementing a hash table from scratch in an interview demonstrates mastery of the data structure. A minimal but correct implementation requires a fixed-size bucket array, a hash function, a collision resolution strategy, and resize logic.
Start with an array of size 8 (a power of 2 simplifies modular arithmetic using bitwise AND). Each bucket holds a list of (key, value) pairs to handle collisions via chaining. The hash function converts the key to an integer and takes it modulo the array size.
Insert pseudocode: compute index as hash(key) modulo capacity. Scan the chain at index. If a pair with the same key already exists, update its value. Otherwise, append the new (key, value) pair. Increment the entry count. If entry count exceeds capacity times load_factor_threshold, call resize.
Lookup pseudocode: compute index as hash(key) modulo capacity. Scan the chain at index for a pair with the matching key. Return the associated value if found, or a not-found sentinel otherwise.
Delete pseudocode: compute index as hash(key) modulo capacity. Scan the chain at index and remove the pair with the matching key if found. Decrement the entry count.
Resize pseudocode: create a new bucket array of size 2 times the current capacity. For every existing entry in every chain, re-insert it into the new array using hash(key) modulo new capacity. Replace the old array with the new one.
A worked example: inserting 6 keys into an initial array of size 8 triggers a resize when the load factor reaches 0.75 (after 6 insertions). The array grows to 16 and all entries are rehashed.
Time complexity: O(1) amortized for all operations assuming a good hash function and load factor control. O(n) worst case for resize, O(1) amortized. Space complexity: O(n).
Interview tip: implement the hash table iteratively during the interview and explicitly state that you are using chaining for collision resolution and will resize at a load factor of 0.75. These design choices show informed engineering judgment.
Hash Table Performance Considerations
The O(1) average complexity of hash table operations is an expected value, not a guarantee. Understanding the factors that affect actual performance helps you make better choices and avoid common pitfalls.
The quality of the hash function is the most important factor. A hash function that maps many keys to the same bucket creates long chains, degrading lookup time to O(n) in the worst case. This is not just a theoretical concern: adversarial inputs crafted to cause maximum collisions have been used in denial-of-service attacks against web servers that use hash tables with predictable hash functions. The defense is to seed the hash function with a random value at startup, making the specific bucket mapping unpredictable.
The initial capacity affects performance for small numbers of insertions. Starting too small causes immediate resizing overhead. Starting too large wastes memory and increases cache miss rates. A reasonable default initial capacity is 16.
The resize factor (typically 2) must be chosen to keep amortized cost at O(1). A smaller resize factor reduces memory waste but increases the frequency of resizing. A larger factor wastes more memory. Doubling is the standard choice.
Cache performance matters significantly. Open addressing (probing) tends to be faster in practice than chaining because it stores all data in the main array, leading to better cache locality. Python's dict, Java's HashMap, and C++'s unordered_map all use different strategies, and their performance varies significantly with usage patterns.
A worked example of adversarial collision: early versions of PHP, Ruby, and Python used simple polynomial hash functions without random seeding. An attacker who knew the hash function could craft a POST request with thousands of parameters that all hashed to the same bucket, turning hash table insertion into O(n squared) and causing denial of service. The fix was to add a per-process random seed (called hash randomization or ASLR for hashing).
Time complexity: O(1) expected, O(n) worst case. Space complexity: O(n).
Interview tip: mention hash randomization when discussing hash table security. Knowing about this class of attacks and their mitigations distinguishes candidates with production experience from those who only know the academic version of the data structure.