Interview frequency: …
Short answer
A hash function maps a key to a numeric index in an internal array for O(1) access. If two different keys map to the same index (a collision), resolve it with linked lists (chaining) or by searching for available slots (open addressing).
Explanation
In separate chaining, each table position holds a linked list or red-black search tree that groups colliding elements in the same bucket. In open addressing (such as linear or quadratic probing), all elements remain in the main array; when a collision occurs, the algorithm searches for the next empty slot according to a probing formula. The load factor determines when to resize the table and rehash it.
Code example
class ChainedMap: # collision → append to the bucket's list
def __init__(self, size=8):
self.buckets = [[] for _ in range(size)]
def put(self, key, value):
bucket = self.buckets[hash(key) % len(self.buckets)]
for i, (k, _) in enumerate(bucket):
if k == key:
bucket[i] = (key, value)
return
bucket.append((key, value))
def get(self, key):
for k, v in self.buckets[hash(key) % len(self.buckets)]:
if k == key:
return v
raise KeyError(key)
class ProbingMap: # collision → try the next free slot (linear probing)
def __init__(self, size=8):
self.slots = [None] * size # fixed size: a real table resizes at ~70% load
def put(self, key, value):
i = hash(key) % len(self.slots)
while self.slots[i] is not None and self.slots[i][0] != key:
i = (i + 1) % len(self.slots)
self.slots[i] = (key, value)Common mistakes
- Using a poor hash function that clusters elements in nearby indexes, turning the hash table into a slow O(N) list.