Hashing Techniques

At the heart of countless systems—from database indexing and compiler symbol tables to cryptographic applications—lies a simple yet profound idea: transforming a piece of data directly into the address where it should live. This is the power of hashing, a technique that enables near-instantaneous data retrieval by converting arbitrary keys into array indices. Mastering hashing means understanding how to design the mapping function and manage the inevitable conflicts that arise, turning a theoretical concept into a tool for building blazingly fast, real-world applications.

Understanding Hash Functions

A hash function is a deterministic algorithm that takes an input (or key) of arbitrary size and produces a fixed-size numeric value called a hash code. The primary goal for a hash table is to map this hash code to an index within the bounds of an underlying array. For example, if you have a table of size 10, a simple hash function might compute hash_code % 10 to get an index between 0 and 9.

The quality of a hash function is paramount. A good hash function must possess three key properties:

1. Deterministic: The same key must always produce the same hash code.
2. Uniform Distribution: The function should scatter keys uniformly across the hash table's indices. If a function frequently maps different keys to the same index (collision), performance degrades.
3. Efficient to Compute: The hashing process should be fast, often requiring just $O(1)$ time.

Common strategies include division (using modulo), multiplication, and techniques for string keys like polynomial rolling hashes, which weight each character's position. For instance, hashing a short string "cat" might involve calculating (c * 128^2 + a * 128^1 + t * 128^0) \mod \text{table_size}. The aim is to minimize predictable patterns that lead to clusters of keys in one part of the table.

Collision Resolution: Separate Chaining

Since the range of possible keys is almost always larger than the size of the hash table, collisions are unavoidable. Separate chaining is a classic, intuitive method for resolving them. In this approach, each slot (or "bucket") in the hash table does not store a single element, but rather a pointer to a linked list (or another dynamic structure). All keys that hash to the same index are stored in this chain.

Insertion is straightforward: compute the index, then add the new key-value pair to the front of the linked list at that index. Lookup and deletion follow the same path: find the index, then traverse the list to find the matching key. The cost of operations now depends on the length of the chain. In the worst case, if all keys collide into one bucket, operations degrade to $O(n)$. However, with a good hash function and a reasonable load factor (discussed later), the average chain length remains short, preserving average $O(1)$ performance.

Collision Resolution: Open Addressing

Open addressing takes a different tack. Here, the hash table array stores the key-value pairs directly. When a collision occurs, the algorithm probes for the next available empty slot within the table according to a predefined sequence. The most common probing methods are:

• Linear Probing: If slot $h(x)$ is occupied, check $h(x)+1$, then $h(x)+2$, and so on, wrapping around to the start of the array. The probe sequence is linear: h(x, i) = (h(x) + i) \mod \text{table_size}.
• Quadratic Probing: To avoid the primary clustering (long runs of occupied slots) common with linear probing, quadratic probing uses a squared offset: h(x, i) = (h(x) + c_1i + c_2i^2) \mod \text{table_size}. This spreads subsequent probes more broadly.

For example, with linear probing, if keys A and B both hash to index 3, A takes slot 3. When B is inserted, it finds slot 3 occupied, so it probes and places itself in slot 4. Deletion in open addressing is trickier; you cannot simply empty a slot, as it might break a probe sequence for other keys. A common solution is to mark the slot as "deleted" (a tombstone) so probing can continue past it.

Load Factor, Performance, and Rehashing

The load factor ($\alpha$) is the single most important metric for gauging a hash table's health. It is defined as the number of entries stored divided by the total number of slots in the table: $\alpha =n/m$.

• In separate chaining, a load factor greater than 1.0 is possible (as chains can grow). Performance typically remains good until $\alpha$ becomes quite high (e.g., 5 or 10), though a common rule of thumb is to rehash when $\alpha$ exceeds 0.75 or 1.0.
• In open addressing, the load factor must be less than 1.0. Performance, especially for linear probing, degrades significantly as $\alpha$ approaches 1. Due to clustering, a common trigger for rehashing is when $\alpha$ reaches 0.5 to 0.7.

Rehashing is the process of resizing the table to control the load factor. When the threshold is crossed, a new, larger table (often double the size, preferably a prime number) is allocated. Every key from the old table is re-inserted into the new table using the same hash function but with the new table size. This operation is expensive, costing $O(n)$ time, but it amortizes over many insertions, keeping average performance constant. It's a critical mechanism that allows hash tables to adapt dynamically to the amount of data they store.

Common Pitfalls

1. Choosing a Poor Hash Function: Using a non-uniform hash function (like hashing student IDs by just the last two digits) guarantees collisions and clustering, destroying $O(1)$ average performance. Correction: Implement or select a well-studied hash function designed for your key type (e.g., FNV-1 for strings) that provides good avalanche effect, where small changes in input produce large changes in output.

1. Ignoring the Load Factor: Failing to monitor $\alpha$ or setting an inappropriate rehashing threshold leads to a full or nearly-full table. In open addressing, this makes insertion impossible or turns every lookup into a full-table scan. Correction: Always implement rehashing. For general purposes, rehash when $\alpha$ exceeds 0.75 for chaining or 0.7 for open addressing.

1. Misapplying Open Addressing with High-Frequency Deletions: Using linear or quadratic probing in a scenario with many deletions fills the table with tombstones. This increases the average probe length, harming performance, even if the actual load factor is low. Correction: Use separate chaining for tables with high rates of deletion, or schedule periodic rehashing to clean out tombstones.

1. Using Mutable Keys: If an object's key field changes after it is inserted into a hash table, its hash code will no longer correspond to the table index where it is stored. Future lookups for that key will fail, or worse, retrieve the wrong data. Correction: Use immutable types (like String or Integer) for keys, or ensure key fields are never modified after the object is used in a hashing context.

Summary

• Hashing provides average $O(1)$ time complexity for insertion, deletion, and lookup by using a hash function to map a key directly to an array index. A good hash function is deterministic, efficient, and distributes keys uniformly.
• Collisions are inevitable. Separate chaining resolves them by storing colliding keys in linked lists at each index, while open addressing (linear or quadratic probing) finds the next available slot within the table itself.
• The load factor ($\alpha$) is critical for performance. For open addressing, keep $\alpha$ below 0.7; for separate chaining, a higher threshold (e.g., 0.75-1.0) is acceptable.
• Rehashing—creating a larger table and re-inserting all keys—is an essential maintenance operation triggered by the load factor to maintain efficient performance over the lifetime of the hash table.