1 Introduction

1.1 Definition and purpose

A hash table (also called a hash map) is a data structure that implements an associative array abstract data type, mapping keys to values. It uses a hash function to compute an index (or hash code) into an array of buckets or slots, from which the desired value can be found. Ideally, the hash function assigns each key to a unique bucket, but in practice collisions occur and must be resolved. Hash tables offer average constant-time complexity for insertion, deletion, and lookup operations, making them a fundamental building block in algorithms, databases, and software systems.

1.2 Historical background

The concept of hashing originated in the early 1950s. The first known use was by Hans Peter Luhn at IBM, who invented a hash function for searching text. In 1953, Gene Amdahl and others at IBM developed the first hash table implementation. The method gained wider recognition with the publication of "Hash Coding for Address Lookup" by Robert Morris in 1968. Over the decades, numerous collision resolution strategies and variants have been developed, solidifying hash tables as a cornerstone of computer science.

2 Basic concepts

2.1 Hash functions

A hash function maps a key (of arbitrary size) to a fixed-size integer (the hash code). This code is then used to determine the bucket index, typically via modulo operation with the array size.

2.1.1 Properties of good hash functions

A good hash function should be:

  • Deterministic: The same key always produces the same hash code.
  • Uniform: Hash codes are distributed uniformly across the output space.
  • Fast: Computation of the hash code is efficient.
  • Non‑invertible (for security contexts): It should be difficult to reconstruct the original key from the hash.

2.1.2 Common hash function examples

  • Division hashing: h(k) = k mod m (where m is a prime number).
  • Multiplication hashing: h(k) = floor(m * (k * A mod 1)) with a constant A (e.g., Knuth’s recommendation A ≈ (√5 – 1)/2).
  • Cryptographic hash functions: SHA‑1, SHA‑256 (used when security is required).
  • Non‑cryptographic hash functions: MurmurHash, CityHash, xxHash (optimized for speed).

2.2 Buckets and slots

A hash table consists of an array of buckets (sometimes called slots). Each bucket can hold zero or more key‑value pairs. In open addressing, each bucket stores exactly one entry; in chaining, a bucket holds a pointer to a data structure (e.g., a linked list) for overflow entries.

2.3 Load factor

The load factor α is defined as the number of stored entries divided by the total number of buckets. A high load factor increases the probability of collisions and degrades performance. Most hash tables automatically resize (rehash) when α exceeds a threshold (commonly 0.75 for open addressing, 1.0–2.0 for chaining).

3 Collision resolution

Because the key space is typically larger than the number of buckets, collisions (two keys hashing to the same bucket) are inevitable. Several strategies exist to handle them.

3.1 Separate chaining

In separate chaining, each bucket stores a data structure (e.g., a linked list) containing all key‑value pairs that hash to that bucket. Insertion appends to the list; lookup and deletion scan the list.

3.1.1 Linked list chaining

The simplest form uses a singly or doubly linked list. Insertion is O(1) at the head, but lookup and deletion require linear traversal of the list. Poorly distributed hash functions can degrade performance to O(n).

3.1.2 Dynamic array chaining

Instead of a linked list, each bucket holds a dynamic array (e.g., a std::vector in C++ or an ArrayList in Java). Arrays provide better cache locality and lower memory overhead per entry, but insertion may occasionally trigger array resizing.

3.2 Open addressing

Open addressing stores all entries directly in the bucket array. When a collision occurs, the algorithm probes subsequent buckets according to a predetermined sequence until an empty slot is found.

3.2.1 Linear probing

In linear probing, the probe sequence is h(k), h(k)+1, h(k)+2, ... (mod table size). It is simple and cache‑friendly but suffers from primary clustering—long runs of occupied buckets form, degrading performance.

3.2.2 Quadratic probing

Quadratic probing uses a step that grows quadratically: h(k) + i² (mod table size). This reduces primary clustering but can cause secondary clustering—keys with the same initial hash follow the same probe sequence.

3.2.3 Double hashing

Double hashing uses a secondary hash function to determine the probe step: h₁(k), h₁(k) + h₂(k), h₁(k) + 2·h₂(k), .... This almost eliminates clustering, provided the step size is non‑zero and relatively prime to the table size.

3.3 Cuckoo hashing

Cuckoo hashing uses two separate hash functions and two tables (or two buckets per location). Insertion tries the first table; if the bucket is occupied, it *kicks out* the existing key and re‑inserts it using the second hash function. This process may cascade. Lookups are always O(1) worst‑case, but insertion may require rehashing if cycles occur.

4 Dynamic resizing

Most hash tables start with a fixed size and grow (or shrink) as the number of entries changes.

4.1 Rehashing

Rehashing involves allocating a new, larger (or smaller) array, recomputing hash codes for all existing entries, and moving them into the new table. This operation is expensive—O(n)—but happens infrequently.

4.2 Growth factors and policies

Common growth factors are 2 (doubling) or 1.5–2 (e.g., Java’s HashMap uses 2; Go’s map uses 2). Shrinking policies usually require the load factor to fall below a second threshold (e.g., 0.25) after a resize. Some implementations never shrink.

5 Performance analysis

5.1 Time complexity

5.1.1 Average case

Under the assumption of simple uniform hashing (keys distribute uniformly), the average time for insertion, deletion, and lookup is O(1) (constant). For separate chaining, the average chain length is α, yielding O(1 + α) ≈ O(1) for small α. Open addressing also gives O(1) average for low load factors.

5.1.2 Worst case

In the worst case (e.g., all keys hash to the same bucket or follow the same probe sequence), every operation degenerates to O(n). This can be mitigated by using good hash functions and periodic rehashing.

5.2 Space complexity

Hash tables require O(n) space for the entries plus overhead for the bucket array, which may be as small as O(1) (if resized to match the number of entries) or larger due to load factor thresholds. Chaining adds per‑entry pointers; open addressing wastes unused slots.

5.3 Amortized analysis

Resizing operations are costly but rare. Using a doubling growth policy, the amortized cost of an insertion is O(1). The analysis resembles that of dynamic arrays: each rehash costs O(n), but the number of insertions since the last resize is at least n/2, so the amortized cost per insertion is O(1).

6 Variants and optimizations

6.1 Robin Hood hashing

Robin Hood hashing (1986) aims to reduce probe variance in open addressing. During insertion, if the probing distance of the new key is larger than that of an existing key, they are swapped. This reduces the maximum probe length, improving worst‑case lookup times.

6.2 Hopscotch hashing

Hopscotch hashing (2008) combines open addressing with a small neighborhood (bucket and a few adjacent slots). Insertions use displacement within the neighborhood, ensuring constant‑time lookups and good cache locality. It is widely used in concurrent implementations.

6.3 Perfect hashing

Perfect hashing guarantees no collisions for a static set of keys. The keys are known in advance, and a family of hash functions is used to construct a collision‑free mapping.

6.3.1 Minimal perfect hash functions

A minimal perfect hash function maps n keys onto the integers [0, n‑1] without collisions. Such functions are useful for compact lookup tables and are often constructed using algorithms like the “Hash, Displace, and Compress” method.

A Bloom filter is a probabilistic data structure that uses multiple hash functions to test set membership (with a small false‑positive rate). It is not a hash table, but it is often discussed alongside hashing techniques for memory‑efficient approximate membership queries.

7 Implementation considerations

7.1 Key and value types

Keys must be hashable and comparable for equality. Common types include integers, strings, and tuples. For custom types, the programmer must provide a suitable hash function and equality operator. Values can be any type; some implementations allow null values.

7.2 Memory management

Memory for entries must be allocated and freed. In languages without garbage collection (C, C++), the programmer must manage memory explicitly. In chaining, nodes are typically heap‑allocated; in open addressing, entries may be stored inline in the bucket array, reducing allocation overhead.

7.3 Thread safety and concurrency

Hash tables in single‑threaded contexts are simple. Multi‑threaded use requires synchronization to prevent data races.

7.3.1 Lock‑based approaches

Coarse‑grained locking (one mutex for the entire table) is simple but serializes all access. Fine‑grained locking (per bucket or per segment) improves concurrency. Java’s ConcurrentHashMap uses a striped lock approach.

7.3.2 Lock‑free hash tables

Lock‑free implementations use atomic compare‑and‑swap (CAS) operations and hazard pointers. They avoid deadlocks and priority inversion but are complex. Examples include Cliff Click’s non‑blocking hash table and Intel’s TBB concurrent hash map.

8 Applications

8.1 Database indexing

Hash tables (hash indexes) enable fast equality lookups in databases. They are used for in‑memory joins, grouping, and indexing columns with high cardinality. Systems like MySQL’s MEMORY engine and PostgreSQL’s hash index (though less common than B‑trees) rely on them.

8.2 Caching systems

Memcached, Redis, and similar in‑memory caches employ hash tables to store key‑value pairs, providing sub‑millisecond lookups. The O(1) average access time is critical for high‑throughput caching.

8.3 Symbol tables in compilers

Compilers use hash tables to implement symbol tables, mapping identifiers to their types, scopes, and memory locations. The constant‑time lookup is essential during parsing and semantic analysis.

8.4 Associative arrays in programming languages

Languages like Python (dict), JavaScript (Map), Java (HashMap), C++ (std::unordered_map), and Go (map) expose hash tables as built‑in associative arrays. They are used everywhere from configuration storage to memoization.

9 See also

  • Binary search tree: O(log n) average, supports ordered traversal.
  • Trie: Efficient for string keys and prefix searching.
  • Bloom filter: Probabilistic membership testing.
  • Concurrent hash table: Designed for multithreaded environments.

9.2 Notable hash table libraries

  • Google’s Swiss Table / absl::flat_hash_map: High‑performance open‑addressing implementation using SIMD.
  • Facebook’s Folly F14: Fast open‑addressing hash table with excellent cache behavior.
  • GNU libstdc++ std::unordered_map: Default chaining‑based implementation.
  • Intel TBB concurrent_hash_map: Lock‑free concurrent hash map.