Hash Tables
A data structure that stores key–value pairs with expected constant-time insertion, lookup, and deletion.
A hash table is a data structure that stores key–value pairs and supports insertion, lookup, and deletion in expected O(1) time. A hash function maps each key to an integer index into an array, and the value is stored at that slot. With a good hash function and a reasonable load, the cost is just the hash computation plus constant-time array access — which is why hash tables are the workhorse behind dictionaries, caches, symbol tables, and many database index structures.
Collisions — two keys hashing to the same slot — are inevitable whenever the key space exceeds the array size. The two standard resolutions are chaining, in which each slot holds a linked list of colliding entries, and open addressing, in which the table probes alternative slots (linear probing, quadratic probing, or double hashing). With chaining and a load factor α — the average number of entries per slot — the expected search cost is O(1 + α), and the table stays efficient as long as it is resized when it becomes too full.
Hash function quality matters. Cryptographic hashes are overkill for hash tables; fast non-cryptographic functions such as FNV-1a, MurmurHash, and xxHash are typical. A poorly chosen function allows adversarial keys to degrade performance to O(n) per operation — a known denial-of-service vector against web frameworks (hash-flooding attacks) that randomized hash seeds mitigate.
Because elements are stored in hash order, iteration is unordered; when sorted order matters, a balanced tree is the alternative, offering O(log n) operations. Hash tables are therefore a perfect illustration of the Big O distinction between expected and worst-case behavior — expected O(1), worst case O(n) — and they are the standard contrast case for the O(log n) lookups of binary search and its tree-based cousins.
Tags
algorithms complexity data structures hashing