Hashing, Dictionaries and Probabilistic Structures

Introduction

Hashing is a family of techniques for transforming a key into a location, identifier, or compact summary. It supports dictionary operations such as search, insertion, and deletion in expected constant time, and it underlies database indexes, caches, symbol tables, deduplication systems, distributed routing, and streaming analytics. Unlike comparison-based search trees, hash-based structures do not require keys to be ordered. Their performance depends instead on the quality of the hash function, table capacity, collision policy, workload distribution, and resizing strategy.

This chapter develops hashing from its classical in-memory form to advanced structures used in large-scale systems. It also examines universal hashing, consistent hashing, dynamic tables, skip lists, Bloom filters, and Count-Min Sketches. A central theme is that exact data structures and probabilistic structures make different trade-offs: exact structures preserve correctness for every query, whereas probabilistic structures reduce memory and communication costs by accepting controlled errors.

Learning Objectives

After studying this chapter, a student should be able to:

• Explain the dictionary abstraction and distinguish hashing from comparison-based indexing.
• Design and analyse separate-chaining and open-addressing hash tables.
• Select hash functions and collision-resolution strategies for realistic workloads.
• Explain universal hashing, dynamic resizing, and consistent hashing.
• Analyse skip lists and compare them with balanced search trees.
• Derive Bloom-filter false-positive probability and choose parameters for a target error rate.
• Explain Count-Min Sketch estimates, error bounds, and conservative updates.
• Evaluate these structures in databases, caches, streaming systems, and distributed architectures.

1. The Dictionary Abstraction

A dictionary stores associations between keys and values. Its principal operations are:

Let n be the number of stored records and let T(n) denote the running time of an operation. A well-designed hash table aims for expected T(n) = Θ(1) time for search, insertion, and deletion, although its worst-case time is typically Θ(n). The distinction between expected and worst-case performance is essential: hashing does not magically eliminate collisions, and an adversarial or highly skewed workload can expose poor behaviour.

A comparison-based search structure obtains information from relations such as k₁ < k₂. A hash table instead computes a hash value h(k), usually an integer, and maps that value to a table position. Consequently, hashing is especially effective when exact equality queries dominate and ordered operations—such as predecessor, range search, or sorted traversal—are not primary requirements.

2. Hash Functions and Collisions

A hash function maps a key domain U to an integer range. For a table with m slots, an index function may be written as:

Here h(k) is a non-negative integer hash value and m is the number of slots. The modulo operation is suitable only if the resulting distribution is adequately uniform; poor choices of m can interact with regular key patterns. For example, if numeric keys are mostly multiples of a power of two, a power-of-two table size combined with a weak hash may produce severe clustering.

A collision occurs when distinct keys k₁ and k₂ satisfy h(k₁) = h(k₂), or when their reduced table indexes are equal. Collisions are unavoidable whenever the key domain is larger than the table. A practical hash function should have the following properties:

1. Determinism: the same key produces the same hash value during the relevant lifetime.
2. Efficiency: hashing should not dominate the cost of a dictionary operation.
3. Avalanche behaviour: a small change in the key should affect many output bits.
4. Distribution: keys expected in the workload should spread across slots.
5. Domain awareness: strings, composite objects, byte arrays, and numerical values may require different treatment.

A cryptographic hash, such as SHA-256, is designed to resist deliberate inversion and collision attacks. A non-cryptographic hash is usually faster and may be adequate for trusted, performance-oriented workloads. Security-sensitive systems often use keyed hashing, such as a pseudorandom function with a secret seed, to prevent attackers from constructing many colliding keys.

Load Factor

For a table of m slots containing n records, the load factor is:

The load factor is dimensionless. In separate chaining, α may exceed 1 because multiple records can occupy one bucket. In open addressing, α must remain below 1 because every record occupies a table slot. As α increases, collisions and probe lengths generally increase.

3. Collision Resolution

3.1 Separate Chaining

In separate chaining, each table slot points to a collection—commonly a linked list, dynamic array, or balanced tree—containing all records mapped to that slot. The expected unsuccessful-search cost is approximately proportional to α under simple uniform hashing. An unsuccessful search examines an average of about α records in the selected chain, while a successful search examines approximately 1 + α/2 records under a standard random-order assumption.

Chaining has several engineering advantages. It tolerates α greater than one, supports deletion directly, and is relatively simple to resize. Its disadvantages include pointer overhead, poor cache locality when linked lists are used, and possible latency spikes when a chain becomes unusually long. Modern implementations often use compact arrays or treeify long chains to improve locality and limit worst-case bucket behaviour.

3.2 Open Addressing

Open addressing stores every record directly in the table. If a collision occurs, the algorithm follows a probe sequence until it finds the target key or an empty slot. Deletion cannot usually replace a deleted slot with an ordinary empty marker, because that could prematurely terminate searches for keys inserted later in the probe sequence. Implementations therefore use a tombstone marker or periodically rebuild the table.

#### Linear Probing

Linear probing examines:

It has excellent locality because consecutive probes access adjacent memory. Its principal weakness is primary clustering: occupied runs tend to grow, causing more keys to join the same run.

Under the classical uniform-hashing approximation, the expected number of probes for an unsuccessful linear-probing search is approximately:

and for a successful search approximately:

These expressions assume a sufficiently large table, random-like hashing, and standard linear probing. They are approximations, not guarantees; actual performance depends on clustering and implementation details.

#### Quadratic Probing

A quadratic sequence may be defined as:

where c₁ and c₂ are constants. Quadratic probing reduces primary clustering but can still exhibit secondary clustering: keys with the same initial hash follow the same probe sequence. The choice of m and coefficients must ensure that the sequence can reach enough slots.

#### Double Hashing

Double hashing uses a second hash function:

The second hash must be non-zero modulo m, and its values should be relatively prime to m when full-table coverage is required. Double hashing generally distributes probe sequences better than linear or quadratic probing, but it performs more computation and may have weaker locality.

Worked Example: Linear Probing

Suppose m = 7 and the initial indexes of keys A, B, C, and D are 3, 3, 3, and 5. Inserting A places it at slot 3. B probes slot 3 and moves to slot 4. C probes slots 3 and 4 and moves to slot 5. D begins at slot 5 and moves to slot 6. The final occupied slots are 3, 4, 5, and 6. The cluster from 3 through 6 illustrates how a few collisions can create a longer future probe sequence.

4. Universal Hashing

A fixed hash function can be exploited if an adversary knows its weaknesses. Universal hashing addresses this by selecting a function randomly from a family H before processing the workload. A family is universal if, for any distinct keys x and y,

where the probability is over the random choice of h and m is the number of table slots. The guarantee does not say that every chosen function is perfect; it bounds the collision probability for every pair when the function is selected randomly.

A common construction for integer keys uses a prime p larger than the key universe and parameters a and b selected uniformly with a ≠ 0:

The precise universality guarantee depends on the construction and parameter assumptions. In practice, randomized seeding and strong mixing are used to make collision attacks difficult. Universal hashing is especially important in shared services, language runtimes, packet-processing systems, and any application in which users can influence keys.

5. Dynamic Hash Tables

A static table becomes inefficient as n changes. A dynamic hash table grows when α exceeds an upper threshold and may shrink when α falls below a lower threshold. Resizing generally requires allocating a new table and reinserting every record because the index depends on m. If m changes, h(k) mod m usually changes as well.

If capacity grows geometrically—for example, it doubles—then a sequence of n insertions has amortized constant resizing cost. Although one resize costs Θ(n), the total cost of all resizing operations over many insertions is O(n) when each expansion multiplies capacity by a constant greater than one. Thus the amortized insertion cost remains O(1), assuming hash computation and ordinary insertion are O(1) expected time.

A production design should define:

• upper and lower load-factor thresholds;
• the growth factor and capacity sequence;
• whether deletion uses tombstones or compaction;
• latency limits for a single resize;
• concurrency rules during migration;
• memory overhead and allocation behaviour.

Incremental rehashing distributes migration across ordinary operations and avoids a large pause. During migration, lookup may need to inspect both old and new tables. This complicates concurrency but is valuable for latency-sensitive services.

6. Consistent Hashing

Ordinary modulo hashing is unsuitable for distributed caches when nodes join or leave. If keys are assigned by h(k) mod N, changing N can remap a large fraction of keys. Consistent hashing instead places both nodes and keys on a logical ring, usually by hashing them into the same circular identifier space. A key is assigned to the first node encountered while moving clockwise from the key’s position.

With ideal random placement of N nodes, adding or removing one node remaps an expected fraction of approximately 1/N of the key space, rather than nearly all keys. Virtual nodes place multiple independently hashed positions on the ring for each physical node. They improve load balance and allow a node’s capacity to be represented by a proportional number of virtual positions.

Consistent hashing does not solve every distributed-systems problem. It does not by itself provide replication, consistency, failure detection, or data migration guarantees. Practical systems often use a replication factor r, assigning a key to the first r distinct nodes clockwise from its position. They must also handle hot keys, heterogeneous node capacities, membership convergence, and removal of failed nodes.

7. Skip Lists

A skip list is a probabilistic ordered dictionary composed of multiple linked-list levels. The bottom level contains all keys in sorted order. Higher levels contain sampled subsets that act as express lanes. Search begins at the highest level and moves forward while the next key remains less than the target; otherwise it descends one level.

If each element independently rises to the next level with probability p, where 0 < p < 1, the expected number of elements at level i is approximately npⁱ. The expected height is O(log n), and search, insertion, and deletion have expected O(log n) time. The structure uses expected O(n) space because the expected total number of forward pointers is proportional to n/(1 − p). A common choice is p = 1/2, although lower values reduce pointer overhead at the cost of longer searches.

Skip lists provide ordered iteration and range queries, which ordinary hash tables do not. They are also attractive in concurrent systems because local pointer changes can be easier to coordinate than global tree rotations. Their probabilistic performance is not a worst-case guarantee unless additional mechanisms limit height or adversarial randomness is controlled.

8. Bloom Filters

A Bloom filter is a compact probabilistic structure for set membership. It supports insertion and membership testing but not ordinary deletion. It consists of m bits initially set to zero and k independent or suitably distinct hash functions. To insert an element, the k corresponding bit positions are set to one. To query an element, all k positions are checked.

• If at least one checked bit is zero, the element is definitely absent.
• If all checked bits are one, the element may be present.

Thus Bloom filters have no false negatives under correct operation, but they can have false positives. Standard deletion is unsafe because clearing a bit may remove evidence belonging to another element. Counting Bloom filters replace each bit with a small counter, permitting deletion at increased memory cost and with counter-overflow considerations.

After inserting n elements, assuming uniform independent hashing, the probability that a particular bit remains zero is approximately:

The false-positive probability is therefore approximately:

where m is the number of bits, k is the number of hash functions, and n is the number of inserted elements. For fixed m and n, the approximate optimal number of hash functions is:

At this choice, the approximate false-positive rate is:

These equations assume uniform hashing, a known or controlled number of insertions, and independent-looking hash outputs. They are planning formulas; finite-size effects and correlated hashes can produce different empirical rates.

Worked Bloom-Filter Example

Suppose a filter has m = 10,000 bits, stores n = 1,000 elements, and uses k = 7 hash functions. Then:

kn/m = 7 × 1000/10000 = 0.7.

The approximate false-positive probability is:

f ≈ (1 − e^(−0.7))⁷.

Since e^(−0.7) ≈ 0.4966, we obtain f ≈ (0.5034)⁷ ≈ 0.0082, or about 0.82%. The filter can safely reject most absent items, but a positive result still requires authoritative verification.

Bloom filters are widely used before disk access in databases, before remote cache access in distributed services, and in storage engines to avoid unnecessary searches of immutable files. They are not appropriate when an occasional false positive is unacceptable unless the result is always verified.

9. Count-Min Sketches

A Count-Min Sketch (CMS) estimates frequencies in a high-volume stream using a two-dimensional array of counters. It has d rows and w counters per row. Each row has a hash function mapping an item to one counter. On observing item x with increment Δ, the counter at each row’s hashed position is increased by Δ. The estimate is the minimum of the d counters selected by x.

For non-negative updates, the estimate is never below the true frequency. Collisions only add mass from other items, so the CMS has one-sided error:

Let the total stream mass be F = ∑ᵢ f(i), where updates are non-negative. With width w = ⌈e/ε⌉ and depth d = ⌈ln(1/δ)⌉, the standard guarantee for a fixed query is:

Here ε is the additive error fraction and δ is the failure probability. The guarantee assumes suitable independent or pairwise-independent hashing and non-negative updates. The sketch uses O((1/ε) ln(1/δ)) counters.

Example

Suppose a stream contains F = 1,000,000 total events. A design targets ε = 0.001 and δ = 0.01. Then w = ⌈e/0.001⌉ = 2,718 and d = ⌈ln(100)⌉ = 5. The sketch uses 13,590 counters. For a fixed queried item, the estimate is at most its true count plus approximately 1,000 with probability at least 99%, subject to the assumptions above.

CMS is useful for heavy-hitter detection, approximate SQL aggregation, network traffic monitoring, ad-frequency measurement, and telemetry. It is less suitable when exact counts are required, when negative updates are central, or when a small absolute error is needed for very low-frequency items. Variants such as conservative update reduce overestimation in many practical workloads: instead of incrementing every selected counter immediately, the algorithm first finds the current minimum and increments only counters equal to that minimum. This often improves estimates but does not eliminate the need for analysis and validation.

10. Choosing Among Structures

The best architecture often combines structures. For example, a database may use a Bloom filter to avoid reading an absent data block, then use a B-tree or hash index for exact retrieval. A distributed cache may use consistent hashing for placement, a local hash table for storage, and a CMS to identify hot keys.

11. Case Study: A Distributed Product-Search Platform

The following is an illustrative case study.

Background

An online retailer receives tens of millions of product-availability requests per hour. Requests are distributed across cache servers. The catalogue contains billions of product identifiers, while only a small fraction are queried during any short interval.

Problem

A naive design uses modulo hashing across cache servers. When a server is added, most keys map to new servers, causing a cache stampede and excessive database load. Each cache server also performs expensive database lookups for invalid product identifiers. Finally, the operations team needs to identify unusually popular products without storing an exact counter for every product.

Analysis

Three different problems are present:

1. Stable distributed placement is required.
2. Negative membership checks should be cheap and safe.
3. Frequencies must be estimated under a bounded memory budget.

No single structure addresses all three requirements.

Approach and Solution

The platform adopts consistent hashing with virtual nodes. Each physical cache server receives virtual positions proportional to its capacity. A replication factor of two stores each cached object on two distinct clockwise successors. Membership changes trigger controlled migration rather than global remapping.

Each cache server maintains a Bloom filter containing product identifiers known to exist in its assigned catalogue partition. A query whose identifier produces a definite negative result bypasses the expensive storage lookup. A positive Bloom result is not treated as proof; the system still checks the authoritative catalogue.

A Count-Min Sketch processes request events. The sketch estimates product popularity and helps identify hot keys. Hot products are replicated more broadly or assigned dedicated cache policies. Because the sketch may overestimate, candidates are verified using exact counters before major capacity decisions.

Outcome

The design reduces remapping during server changes, avoids many negative database reads, and provides a memory-efficient signal for hot-key management. It preserves correctness because Bloom-filter positives and sketch estimates are advisory rather than authoritative.

Learning Points

• Distribution, membership filtering, and frequency estimation are separate concerns.
• Probabilistic structures should be placed before exact verification, not used as unquestionable sources of truth.
• Capacity planning must include false-positive traffic, hot-key skew, replication, and failure recovery.
• Virtual nodes improve balance but do not remove the need for monitoring.

12. Engineering, Governance, and Research Considerations

Correctness and Failure Modes

Hash-table corruption can arise from unsafe concurrent resizing, inconsistent equality and hashing rules, mutable keys, or incorrect tombstone handling. A key’s hash and equality semantics must remain stable while it is stored. Probabilistic structures require explicit documentation of their error direction: Bloom filters may produce false positives, while a standard non-negative CMS may overestimate counts.

Security and Privacy

Attackers may deliberately generate colliding keys to cause denial of service. Randomized hashing, request limits, and input validation reduce this risk. Bloom filters can leak information when an observer can test membership repeatedly; salted or access-controlled filters may be necessary. Frequency sketches can reveal popularity patterns, and aggregated telemetry may still be sensitive. Retention, access control, and data-minimization policies should therefore apply even when the representation is approximate.

Concurrency and Distribution

Atomic counter updates may be required for sketches, while lock-free or partitioned designs can improve throughput. Distributed filters and sketches must define merge semantics. Bloom filters merge naturally by bitwise OR only when their dimensions, hash functions, and interpretation are compatible. CMS structures can be added cell by cell under compatible configurations, but error bounds must account for the combined stream mass.

Contemporary Directions

Modern systems increasingly use learned and adaptive components to select indexes, predict hot keys, or tune cache policies. Such methods can complement hashing but should not obscure deterministic correctness boundaries. Hardware-conscious hashing, SIMD-friendly probing, compact filters such as quotient and cuckoo filters, and privacy-preserving sketches are active areas of systems research. Evaluation should measure throughput, tail latency, memory, error distributions, resize pauses, and behaviour under adversarial or highly skewed workloads—not merely average lookup time.

Best-Practice Checklist

1. Define key equality and immutability before selecting a hash function.
2. Measure workload skew rather than assuming uniform keys.
3. Choose capacity and load thresholds using latency and memory objectives.
4. Use randomized or keyed hashing for attacker-controlled input.
5. Prefer incremental migration when resizing pauses are unacceptable.
6. Use Bloom filters only as probabilistic gates before authoritative checks.
7. State CMS error bounds in terms of stream mass and confidence.
8. Test deletion, crashes, concurrent updates, and membership changes.
9. Monitor collision rates, probe lengths, false-positive rates, and tail latency.
10. Treat approximate results as decisions requiring validation when consequences are material.

Chapter Summary

Hashing transforms keys into locations and enables expected constant-time dictionary operations, but performance depends on collision behaviour, load factor, resizing, and workload assumptions. Separate chaining tolerates high load factors and simplifies deletion, whereas open addressing offers compact storage and strong locality but requires careful probing and deletion policies. Universal hashing randomizes function selection to limit pairwise collision probability, and dynamic resizing preserves amortized efficiency as the table changes.

Consistent hashing reduces key movement when distributed nodes change, especially when virtual nodes represent heterogeneous capacity. Skip lists provide expected logarithmic ordered operations through probabilistic express lanes. Bloom filters provide compact membership screening with no false negatives under standard insertion-only use, but they permit false positives. Count-Min Sketches estimate frequencies with one-sided error and explicit ε–δ guarantees for non-negative streams. In professional systems, these structures are usually composed: probabilistic filters reduce expensive work, exact indexes establish correctness, and distributed hashing manages placement. Sound design requires attention to assumptions, security, concurrency, privacy, and empirical workload behaviour.

Key Terms

Hash function: A deterministic mapping from a key to a hash value.

Collision: The event that distinct keys map to the same hash-table position or hash value.

Load factor: The ratio n/m of stored records n to table capacity m.

Separate chaining: Collision resolution using a collection associated with each table slot.

Open addressing: Collision resolution in which records are stored directly in table slots.

Linear probing: Open addressing that examines consecutive slots.

Primary clustering: Formation of long contiguous probe runs in linear probing.

Double hashing: Probing based on two hash functions.

Universal hashing: Random selection from a hash-function family with bounded pairwise collision probability.

Dynamic hashing: Resizing and rehashing as the number of records changes.

Amortized analysis: Analysis of average cost over a sequence of operations.

Consistent hashing: Ring-based assignment designed to limit remapping after membership changes.

Virtual node: A logical ring position representing part of a physical node’s capacity.

Skip list: A probabilistic multilayer linked structure supporting ordered operations.

Bloom filter: A compact probabilistic set-membership structure.

False positive: A report that an absent item may be present.

Count-Min Sketch: A matrix of hashed counters for approximate frequency estimation.

Heavy hitter: An item whose frequency is large relative to total stream activity.

Tail latency: A high-percentile response time, such as the 99th percentile.

Review Questions

Short Answer Questions

1. Why can a hash table provide expected O(1) lookup but still have Θ(n) worst-case lookup?
2. Define load factor and explain why its acceptable range differs between chaining and open addressing.
3. What is primary clustering, and which common probing method exhibits it?
4. Why does a standard Bloom filter not support safe deletion?
5. State the direction of estimation error for a Count-Min Sketch with non-negative updates.

Long Answer Questions

1. Compare separate chaining, linear probing, quadratic probing, and double hashing in terms of memory locality, deletion, clustering, and expected performance.
2. Explain universal hashing and discuss why randomized hashing is valuable in adversarial environments.
3. Derive the approximate Bloom-filter false-positive probability and explain the role of the optimal number of hash functions.
4. Explain consistent hashing with virtual nodes and analyse its limitations in a replicated distributed cache.
5. Compare skip lists with hash tables and balanced search trees for an ordered, concurrent dictionary.

Analytical / Application Questions

1. A table has 12,000 slots and stores 9,000 records using open addressing. Compute its load factor and discuss whether a resize is advisable if the engineering threshold is 0.70.
2. Design a Bloom filter for 500,000 expected elements with a target false-positive probability of approximately 1%. State the formulas, estimate the required bits per element, and discuss what happens if the actual population doubles.
3. A telemetry stream has total mass F = 20,000,000 events. A CMS is configured with ε = 0.0005 and δ = 0.01. Compute suitable width and depth using w = ⌈e/ε⌉ and d = ⌈ln(1/δ)⌉, then interpret the additive error bound for a fixed query.

Multiple Choice Questions with Answers

Question 1

Which statement best describes a standard Bloom filter?

A. It has false negatives but no false positives.

B. It has no false negatives under standard insertion-only operation, but may have false positives.

C. It stores every key exactly once and supports sorted traversal.

D. It estimates frequencies with a guaranteed lower bound.

Correct Answer: B. It has no false negatives under standard insertion-only operation, but may have false positives.

Question 2

A hash table contains 600 records in 1,000 slots. What is its load factor?

A. 0.06

B. 0.6

C. 1.67

D. 600

Correct Answer: B. 0.6

Question 3

Which collision-resolution method generally has the best locality because it examines adjacent memory locations?

A. Linear probing

B. Separate chaining with linked lists

C. Double hashing

D. Random balanced-tree insertion

Correct Answer: A. Linear probing

Question 4

In a standard Count-Min Sketch with non-negative updates, the estimated frequency is generally:

A. Always less than the true frequency

B. Equal to zero for unseen items only

C. At least the true frequency, subject to possible overestimation

D. Exactly equal to the true frequency

Correct Answer: C. At least the true frequency, subject to possible overestimation

Question 5

What is the principal purpose of virtual nodes in consistent hashing?

A. To eliminate all network failures

B. To improve load balance and represent heterogeneous node capacity

C. To guarantee zero replication overhead

D. To sort all keys globally

Correct Answer: B. To improve load balance and represent heterogeneous node capacity

Question 6

If a Bloom filter uses m = 10,000 bits, n = 1,000 elements, and k = 7 hash functions, its approximate false-positive probability is closest to:

A. 0.0000082%

B. 0.082%

C. 0.82%

D. 8.2%

Correct Answer: C. 0.82%

Question 7

Which structure is most naturally suited to exact range queries over ordered keys?

A. A Bloom filter

B. A Count-Min Sketch

C. A skip list

D. A standard unordered hash table

Correct Answer: C. A skip list

Question 8

Why is deletion difficult in ordinary open addressing?

A. Hash functions cannot process deleted keys.

B. Clearing a slot can incorrectly terminate a later search in the probe sequence.

C. Deletion always changes the table capacity.

D. Open addressing stores keys only in linked lists.

Correct Answer: B. Clearing a slot can incorrectly terminate a later search in the probe sequence.

Question 9

For a CMS with ε = 0.001 and total stream mass F = 1,000,000, the standard additive error allowance is approximately:

A. 1

B. 10

C. 1,000

D. 1,000,000

Correct Answer: C. 1,000

Question 10

What does universal hashing primarily protect against?

A. All memory-allocation failures

B. Adversarially chosen keys that cause excessive collisions for a fixed known hash function

C. False positives in Bloom filters

D. The need for table resizing

Correct Answer: B. Adversarially chosen keys that cause excessive collisions for a fixed known hash function