Hash Table / HashMap: Hash Functions, Collision Resolution, and Load Factor (2026)
A hash table (or hash map) is a data structure that maps keys to values using a hash function. It provides average-case O(1) insertion, deletion, and lookup. Hash tables power dictionaries, caches, and database indexing. The core idea is to compute an index from the key using a hash function and store the key-value pair at that index in an array.
This tutorial covers hash functions, collision resolution strategies (chaining and open addressing), load factor, rehashing, and implementations in C++, Java, and Python.
Hash Functions and Collision Resolution — Chaining
A good hash function distributes keys uniformly across the bucket array. Common hash functions include division method (key % table_size), multiplication method, and universal hashing. For strings, polynomial rolling hash is often used: hash = (hash * base + char) % mod.
Chaining (separate chaining) stores multiple entries in the same bucket using a linked list or dynamic array. On collision, the new key-value pair is appended to the list at that index. Search traverses the list to find the matching key. The load factor α = n / m (number of entries / number of buckets) determines performance — when α exceeds a threshold (typically 0.75), the table is resized and rehashed.
// C++ — chaining using vector
class HashTable {
vector>> table;
int cap;
public:
HashTable(int c) : cap(c) { table.resize(c); }
void put(int k, int v) {
int idx = k % cap;
for(auto& p : table[idx])
if(p.first == k) { p.second = v; return; }
table[idx].push_back({k, v});
}
int get(int k) {
int idx = k % cap;
for(auto& p : table[idx])
if(p.first == k) return p.second;
return -1;
}
};
// Java — HashMap (built-in)
HashMap map = new HashMap<>();
map.put(1, "one");
map.get(1); // "one"
// Python — dict (built-in)
d = {}
d["one"] = 1
print(d["one"]) Open Addressing: Linear and Quadratic Probing
Open addressing stores all entries directly in the bucket array. On collision, the algorithm probes for the next available slot. Linear probing checks index + 1, index + 2, ... sequentially. Quadratic probing checks index + 1², index + 2², ... to reduce primary clustering. Double hashing uses a second hash function for the probe step.
Deletion in open addressing requires lazy deletion (tombstone markers) to avoid breaking probe sequences. Rehashing copies entries to a larger table, recomputing indices with the new capacity. The load factor is kept below a threshold to maintain O(1) average performance.
// C++ — linear probing
class LinearProbing {
int *keys, *vals, cap;
public:
LinearProbing(int c) : cap(c) {
keys = new int[c](); vals = new int[c]();
}
void put(int k, int v) {
int idx = k % cap;
while(keys[idx] != 0 && keys[idx] != k)
idx = (idx + 1) % cap;
keys[idx] = k; vals[idx] = v;
}
int get(int k) {
int idx = k % cap;
while(keys[idx] != 0) {
if(keys[idx] == k) return vals[idx];
idx = (idx + 1) % cap;
}
return -1;
}
};
// Java — LinkedHashMap (ordered)
LinkedHashMap map = new LinkedHashMap<>();
// Python — dict probing is built-in
d = dict([(1,"a"), (2,"b")]) Frequently Asked Questions
What is load factor in a hash table?
Load factor α = n/m (entries per bucket). When α exceeds a threshold (usually 0.75), the table is resized to maintain O(1) operations.
What is the worst-case time complexity of a hash table?
O(n) — when all keys hash to the same bucket (chaining) or form a long probe sequence (open addressing). Good hash functions and resizing mitigate this.
Originally published on Ayodhyyya. Last updated June 1, 2026.