8. Hashing

Introduction

Hashing is a fundamental technique in computer science that enables constant‑time average‑case performance for insert, delete, and search operations. By mapping keys to indices in an array via a hash function, we can store and retrieve data efficiently. This chapter covers the essential components—hash functions, hash tables, collision handling, load factor, and real‑world applications—providing both theoretical foundations and concrete examples.

Hash Functions

Definition and Desired Properties

A hash function h(k) converts a key k into an integer index suitable for addressing a hash table. To be effective, a hash function must satisfy three key properties:

• Deterministic: The same key always produces the same index.
• Uniform distribution: Keys are spread evenly across the table, minimizing collisions.
• Fast computation: The function should be O(1) in time.

Common Formulas

1. Division method: h(k) = k mod m, where m is the table size (preferably a prime number).
2. Multiplication method: h(k) = floor(m * (k * A mod 1)), with a constant A satisfying 0 < A < 1 (often A = (√5‑1)/2 ≈ 0.618).
3. Universal hashing: h(k) = ((a*k + b) mod p) mod m, where a and b are randomly chosen integers, p is a prime larger than the maximum possible key, and m is the table size.

Example: Division Method

Consider the key set {12, 44, 13, 88, 23} and a table size m = 7.

• h(12) = 12 mod 7 = 5
• h(44) = 44 mod 7 = 2
• h(13) = 13 mod 7 = 6
• h(88) = 88 mod 7 = 4
• h(23) = 23 mod 7 = 2 → collision at index 2.

Hash Table Structure

A hash table is an array of size m where each slot may hold a key‑value pair or be empty. Two primary implementation strategies exist:

Open Addressing

Elements are stored directly in the table. When a collision occurs, a probe sequence determines the next slot to examine.

Separate Chaining

Each table slot contains a reference to a linked list (or dynamic array) of all entries that hash to that index.

Basic Operations

1. Insert: Compute index = h(k). In chaining, append the pair to the list at index; in open addressing, follow the probe sequence until an empty slot is found.
2. Search: Compute index = h(k). Scan the chain (chaining) or follow the probe sequence (open addressing) until the key is found or an empty slot indicates absence.
3. Delete: Locate the element as in search. In chaining, remove the node from the list. In open addressing, mark the slot as a tombstone so future probes can skip it while still allowing insertions to reuse the space.

Collision Handling

Separate Chaining

Each bucket is a linked list; the average chain length equals the load factor α = n / m. Expected time complexities are:

• Insert: O(1) average.
• Search: O(1 + α) average.
• Delete: O(1 + α) average.

Example: with α = 0.75, the expected number of probes for a successful search is approximately 1 + 0.75 = 1.75.

Open Addressing

All elements reside in the table itself; performance degrades as the table fills. Common probe sequences include:

Linear Probing

h'(k,i) = (h(k) + i) mod m, where i is the probe number (0,1,2,…).

Quadratic Probing

h'(k,i) = (h(k) + c1*i + c2*i²) mod m, with constants c1 and c2 chosen to ensure full table coverage.

Double Hashing

h'(k,i) = (h1(k) + i*h2(k)) mod m, where h2(k) ≠ 0 for all keys. A typical choice is h2(k) = 1 + (k mod (m‑1)).

When the load factor approaches 1, the expected probe count grows dramatically. To maintain performance, a rehashing (resize) operation is triggered when α exceeds a threshold (commonly 0.7 for chaining, 0.5 for open addressing).

Load Factor

The load factor quantifies how full the hash table is:

α = n / m, where n is the number of stored elements and m is the table size.

It directly influences collision probability and thus the average operation cost.

• Good performance for chaining: α ≤ 0.7.
• Preferred for open addressing: α ≤ 0.5 to keep probe counts low.
• Resizing strategy: When α exceeds the threshold, allocate a new table (often size 2*m) and re‑hash all existing keys into the new table.

Applications

Login Authentication

Systems store a username mapped to a hashed password (often‑salted hash value in a hash table. During login, the entered password is hashed with the same salt and compared to the stored hash, providing O(1) verification time.

Database Indexing

Hash indexes map key values directly to disk pages or memory locations, enabling point‑lookup queries in constant time. Unlike B‑tree indexes, hash indexes do not support efficient range scans but excel at exact‑match queries.

Caching (LRU Cache)

An LRU (Least Recently Used) cache can be built using a hash table that maps keys to nodes in a doubly linked list representing usage order. Both get and put operations run in O(1) average time: the hash table provides instant node access, while the list maintains recency.

Blockchain

Transaction identifiers are often cryptographic hashes (e.g., SHA‑256) stored in a hash table for rapid lookup of transaction status or Merkle proofs. Hash tables facilitate efficient verification of transaction inclusion in a block by allowing constant‑time retrieval of sibling hashes during Merkle‑tree traversal.

Summary

Hashing provides a powerful mechanism for achieving average‑case constant‑time operations when supported by a well‑designed hash function, appropriate collision resolution strategy, and careful load factor management. Understanding the trade‑offs between separate chaining and open addressing, knowing when to resize, and recognizing where hashing shines in real‑world systems are essential skills for any data structures and algorithms practitioner.