Hash Tables, Sets and Associative Structures

Introduction

Many software systems must retrieve a value using a key: a user ID must identify an account, a URL must identify cached content, and a word must identify its frequency. A hash table is a data structure designed for this purpose. It stores key–value pairs and uses a hash function to transform a key into an array index. With a well-designed hash function, suitable collision handling, and controlled occupancy, search, insertion, and deletion have expected constant-time complexity.

Hash tables are not ordered structures. Their principal strength is fast associative access rather than sorted traversal. They provide the implementation foundation for dictionaries, maps, sets, symbol tables, caches, database indexes, compiler environments, and many web-service components.

This chapter develops the theory and practice of hash tables, including chaining, open addressing, load factors, resizing, probabilistic membership structures, caching, deduplication, indexing, and security risks.

Learning Objectives

By the end of this chapter, you should be able to:

• Explain the abstract map and set data types.
• Design hash functions and identify desirable properties.
• Implement collision resolution using chaining and open addressing.
• Calculate and interpret load factors and expected complexity.
• Explain resizing, deletion, caching, indexing, and deduplication applications.
• Compare Bloom filters with exact set implementations.
• Identify collision attacks and apply defensive engineering practices.

1. Associative Structures

A map, also called a dictionary or associative array, stores pairs of the form (key, value). Each key is normally unique. Operations include:

• put(key, value): insert a pair or replace the value for an existing key;
• get(key): retrieve the value associated with a key;
• remove(key): delete a pair;
• containsKey(key): test whether a key exists.

A set stores unique elements and supports insertion, deletion, and membership testing. A set can be implemented as a map whose values are irrelevant—for example, a key may map to true.

An associative structure must define key equality. If two keys are equal, they must identify the same logical entry. A crucial consistency requirement is:

If a.equals(b) is true, then hash(a) must equal hash(b).

The reverse is not required: unequal keys may have the same hash value. Such an event is a collision.

Hash tables generally do not guarantee iteration order. If sorted order is required, a balanced search tree or a specialized ordered map may be more appropriate.

2. Hash Functions

A hash function maps a key to an integer hash code. The table then converts that code into a valid bucket or slot index. For a table with m positions, a common index calculation is:

Here, h(key) is a non-negative integer hash code and m is the table capacity. The modulo operation is appropriate only after ensuring that the result is non-negative; this matters in languages where remainder on negative integers can remain negative.

A useful hash function should have the following properties:

1. Determinism: the same key produces the same hash during its lifetime.
2. Consistency with equality: equal keys produce equal hashes.
3. Uniformity: keys should be distributed approximately evenly among positions.
4. Efficiency: hashing should be substantially cheaper than the operation it accelerates.
5. Avalanche behavior: a small change in the key should alter many output bits in suitable hash families.

Uniformity is an engineering goal, not a guarantee. Real workloads can contain patterns that expose weaknesses. Hashing a string might process characters using a recurrence such as:

where h_i is the current hash value, b is a chosen multiplier, c_i is the numeric value of the next character, and p is a large modulus or an implicit machine-word modulus. The exact constants and overflow behavior must be specified by the implementation. A function suitable for a general-purpose table is not automatically suitable for cryptography.

Cryptographic hashes are designed to resist deliberate inversion and collision finding; ordinary table hashes prioritize speed. Conversely, a fast non-cryptographic hash should not be used to authenticate data or protect passwords.

3. Collisions and Chaining

A collision occurs when distinct keys map to the same table position. Since the number of possible keys is usually much larger than the number of slots, collisions are unavoidable. A collision-resolution strategy determines how entries sharing an index are stored.

In separate chaining, each table position refers to a collection—often a linked list, dynamic array, or tree—of entries. To retrieve a key, the table computes its bucket and searches only that bucket.

If n entries are distributed among m buckets, the load factor is:

The quantity α is the average number of entries per bucket. Under simple uniform hashing, the expected chain length is α. Thus, the expected time for a successful or unsuccessful search is commonly described as O(1 + α), assuming hash computation is O(1) and equality checks are O(1). If α is kept bounded by resizing, this becomes expected O(1).

Chaining has practical advantages:

• insertion can remain simple even when a bucket is occupied;
• deletion does not require special marker states;
• the load factor may exceed 1;
• table capacity and entry storage can be managed independently.

Its disadvantages include pointer or object overhead, poorer cache locality in linked structures, and vulnerability to long chains if hashing is poor or attacks are deliberate. Some implementations convert unusually long chains into balanced trees, changing worst-case lookup within a bucket from linear to logarithmic time.

Worked Example: Chaining

Suppose a table has m = 5 buckets and uses index = key mod 5. Inserting keys 12, 7, 22, 14, and 9 gives:

There are n = 5 entries, so:

The hash function is poor for this particular key pattern because several values have the same remainder. A different hash function or a larger capacity would distribute the entries more effectively.

4. Open Addressing

In open addressing, every entry is stored directly in the table array. When the initial position is occupied, a probe sequence examines alternative positions. The table must maintain an occupancy below 100 percent, and performance degrades sharply as the load factor approaches 1.

4.1 Linear Probing

Linear probing uses:

where i = 0, 1, 2, … is the probe number. It is simple and cache-friendly, but it suffers from primary clustering: groups of occupied slots grow together, causing longer probe sequences.

4.2 Quadratic Probing

Quadratic probing uses a sequence such as:

where c_1 and c_2 are constants selected with the table capacity. It reduces primary clustering, but may still exhibit secondary clustering, in which keys with the same initial hash follow the same probe sequence. Correct coverage of the table depends on the capacity and constants.

4.3 Double Hashing

Double hashing uses a second hash function:

The second step size should not be zero and should be relatively prime to m when full-table coverage is required. Double hashing generally distributes probes better than linear probing but requires two hash computations.

Deletion in Open Addressing

Deletion cannot always simply clear a slot. If a later key was inserted after probing through that slot, clearing it could make a search stop prematurely. Implementations therefore use a tombstone, a marker meaning “previously occupied, continue probing.” Tombstones preserve search correctness but increase probe lengths. Periodic rebuilding removes them.

An alternative is backward-shift deletion, applicable to particular probing schemes, which relocates subsequent entries while preserving their search paths. The algorithm must be designed carefully; arbitrary movement can break lookup correctness.

5. Load Factor, Resizing, and Complexity

For chaining, α = n/m may exceed 1. For open addressing, α must remain below 1, and many implementations resize before reaching a threshold such as 0.5–0.8. The precise threshold depends on the probing method, memory constraints, and performance target.

When a table is resized, entries must be rehashed. Merely copying entries to the same numerical positions is incorrect because the index calculation depends on the new capacity. A typical process is:

1. Allocate a new array with larger capacity.
2. Visit every live entry in the old table.
3. Recompute its index using the new capacity.
4. Insert it into the new table.
5. Replace the old array.

If capacity grows geometrically, for example by approximately doubling, the total cost of many resizes is amortized. A single resize costs O(n), but across a long sequence of insertions the average resizing cost per insertion is expected O(1), assuming hashing and insertion are otherwise expected constant time.

The standard complexity summary is:

These bounds assume a suitable hash function and ordinary key operations. They are not guarantees for every input. A malicious or pathological key distribution can make many operations linear. For ordered trees, worst-case bounds may be more predictable, although their typical constant factors differ.

6. Implementation Design

A robust map implementation must address several details:

• Equality: compare keys using the language’s correct equality operation, not object identity unless identity is the intended semantic.
• Null keys and values: explicitly define whether they are permitted.
• Mutable keys: avoid changing fields used by equality or hashing while a key is stored. Otherwise the entry may become unreachable.
• Capacity selection: choose capacities and probing constants compatible with the hash-index strategy.
• Integer overflow: specify whether arithmetic wraps, widens, or uses checked operations.
• Iteration: document whether iteration order is unspecified, insertion-preserving, or sorted.
• Concurrency: ordinary tables are not automatically thread-safe. Concurrent access may require locks, striped locking, or specialized concurrent algorithms.

A set implementation can expose only keys while internally using the same table mechanisms as a map. A multiset, by contrast, stores a count for each distinct element and is therefore naturally represented as a map from element to frequency.

7. Applications

Caching

A cache maps a resource identifier to recently computed or retrieved data. A hash table provides fast lookup, while a separate eviction policy—such as least recently used (LRU)—decides which entries to remove. A production cache must also specify expiration, maximum memory, invalidation behavior, concurrency, and what happens when the backing service is unavailable.

Deduplication

A set can detect whether a document ID, event ID, or content fingerprint has already been processed. Exact deduplication requires storing enough information to distinguish every relevant item. Hash fingerprints reduce storage but introduce a collision probability unless the original data or a collision-resistant digest is retained.

Indexing

A database or search service can map a field value to record identifiers. Hash indexes are effective for equality predicates such as WHERE user_id = ?. They are not naturally suited to ordered queries such as ranges, prefix searches, or “next highest” operations; B-trees and related ordered indexes are usually more appropriate there.

Symbol Tables

Compilers use maps to associate variable names, functions, and types with metadata. Scope management may use a stack of tables: entering a scope adds a table, and leaving it removes that table. A lookup searches the current scope first and then enclosing scopes.

8. Bloom Filters and Approximate Sets

A Bloom filter is a compact probabilistic structure for testing set membership. It contains a bit array of m bits and uses k hash functions. To insert an item, the corresponding k bits are set to 1. To query an item, if any corresponding bit is 0, the item is definitely absent; if all are 1, the item may be present.

Bloom filters have no false negatives under correct operation, but they can have false positives. Standard Bloom filters do not support ordinary deletion because clearing a bit might remove evidence belonging to another item. Counting Bloom filters replace bits with small counters to support deletion at additional memory cost.

Under the usual assumptions of independent, approximately uniform hash functions, after inserting n items the approximate false-positive probability is:

where p is the false-positive probability, m is the number of bits, k is the number of hash functions, and n is the number of inserted items. The approximation assumes the standard Bloom-filter model and is not an exact guarantee for arbitrary hash functions.

For fixed m and n, the approximate optimal number of hash functions is:

These formulas guide design but must be validated using realistic workloads. Bloom filters are useful as a preliminary test—for example, a storage engine can avoid an expensive disk lookup when the filter says a key is definitely absent. They do not replace an exact set when false positives are unacceptable.

9. Security and Reliability

Hash tables can become denial-of-service targets when an attacker sends many keys that collide. If all keys enter one chain or probe sequence, expected constant-time operations degrade toward O(n). This is known as a collision attack.

Defensive measures include:

• randomized or per-process hash seeds;
• strong, well-reviewed hash functions for adversarial inputs;
• limits on request size and number of keys;
• monitoring unusually long chains or probe sequences;
• tree-based fallback structures where appropriate;
• rate limiting and resource quotas;
• avoiding exposure of predictable hash-table behavior through APIs.

Randomization does not make collisions impossible, and cryptographic hashing may be too expensive for every table operation. The appropriate choice depends on whether keys are trusted, attacker-controlled, persistent, or processed at high volume.

Hash values must not be treated as secure identifiers. They are not substitutes for authentication, authorization, encryption, or digital signatures. Privacy risks also arise when sensitive keys or values are logged during debugging. Data minimization and access controls remain necessary even when the storage structure is efficient.

10. Applied Case: API Response Cache

Background

Consider an illustrative e-commerce API that repeatedly retrieves product details from a slower service. The application needs fast reads while ensuring that changes to prices and stock become visible.

Problem

A naïve implementation calls the product service for every request. This increases latency and load. A cache keyed by product ID can reduce repeated work, but stale data and unbounded memory are risks.

Analysis

A hash map provides expected O(1) lookup from product ID to cached response. The cache needs a maximum capacity, an expiration time, and an eviction policy. If requests are attacker-controlled, the system must also prevent arbitrary key generation from exhausting memory. Concurrent requests may attempt to populate the same missing key simultaneously, causing a cache stampede.

Approach and Solution

The service uses:

1. a hash map for key-to-entry lookup;
2. an LRU list to track recency, with map entries pointing to list nodes;
3. time-to-live metadata for expiration;
4. a capacity limit and eviction process;
5. request coalescing so concurrent misses share one refresh operation;
6. explicit invalidation after an authorized product update.

The map handles association, while the list handles order. This illustrates an important design principle: a hash table often forms one component of a larger data structure rather than solving every requirement alone.

Outcome

Cache hits avoid remote calls and typically reduce latency. However, correctness depends on invalidation and expiration rules, not merely on fast lookup. Metrics should include hit rate, miss rate, eviction rate, entry count, memory use, refresh failures, and observed staleness.

Learning Points

• Expected O(1) lookup does not eliminate system-level design constraints.
• A cache requires a consistency policy.
• Memory and adversarial-key controls are as important as hash performance.
• Composite structures can combine a map’s lookup speed with another structure’s ordering behavior.

11. Contemporary Design Considerations and Best Practices

Modern runtimes often optimize hash tables using compact arrays, cached hashes, tree bins, or insertion-order metadata. Distributed systems may partition keys across machines using consistent hashing, reducing the amount of data remapped when nodes join or leave. This is distinct from ordinary in-memory hash-table indexing and introduces replication, failure detection, and network-latency concerns.

AI and data-intensive applications use associative structures for feature lookup, token dictionaries, memoization, and duplicate detection. Large-scale pipelines should assess memory overhead, skewed key distributions, serialization costs, and the consequences of approximate membership decisions.

Best practices are to:

• define equality and hashing together;
• measure with representative and adversarial workloads;
• resize before performance collapses;
• document expected ordering and thread-safety guarantees;
• avoid mutable keys;
• select exact or probabilistic structures according to error tolerance;
• protect attacker-facing services against collision and memory-exhaustion attacks;
• test deletion, resizing, duplicate insertion, empty tables, and extreme key distributions.

Chapter Summary

Hash tables implement maps and sets by transforming keys into array positions. Because different keys can share a position, collision resolution is essential. Separate chaining stores collections at buckets and tolerates load factors above one; open addressing stores entries in the table and requires carefully designed probe sequences and tombstone-aware deletion. The load factor α = n/m predicts occupancy and strongly influences performance. Geometric resizing preserves expected amortized constant-time operations, but entries must be rehashed under the new capacity.

Hash tables support caches, deduplication, symbol tables, and equality-based indexes. Bloom filters provide memory-efficient approximate membership tests with possible false positives and no standard false negatives. Finally, hash-table performance is not automatically secure: adversarial collisions, mutable keys, memory exhaustion, and stale cached data require explicit engineering controls.

Key Terms

Hash table: Array-based associative structure using a hash function for placement.

Map: Structure associating unique keys with values.

Set: Structure storing unique elements.

Hash function: Function that converts a key into a hash code.

Collision: Event in which distinct keys map to the same position.

Bucket: Table position used by a chaining implementation.

Separate chaining: Collision strategy storing multiple entries in one bucket.

Open addressing: Collision strategy storing every entry in the table array.

Linear probing: Probe sequence using consecutive positions.

Quadratic probing: Probe sequence using a quadratic offset.

Double hashing: Probing method using a second hash function for step size.

Load factor: Ratio of entries to table capacity, α = n/m.

Rehashing: Recomputing positions when entries move to a new table.

Tombstone: Deletion marker retained in an open-addressed table.

Amortized complexity: Average cost over a sequence of operations.

Cache: Fast temporary storage of reusable results.

Deduplication: Process of identifying and eliminating repeated items.

Bloom filter: Probabilistic set with possible false positives.

Collision attack: Deliberate generation of many hash collisions.

Consistent hashing: Distributed technique limiting key remapping when nodes change.

Review Questions

Short Answer Questions

1. Why must equal keys produce equal hash codes?
2. Define the load factor of a hash table.
3. What problem does a tombstone solve in open addressing?
4. State one advantage and one limitation of a Bloom filter.
5. Why must entries be rehashed after resizing?

Long Answer Questions

1. Compare separate chaining and open addressing in terms of memory, deletion, load factor, cache behavior, and worst-case performance.
2. Explain linear probing, quadratic probing, and double hashing, including the clustering problem associated with probing.
3. Describe how a hash-table implementation should handle mutable keys, equality, resizing, and concurrency.
4. Explain how hash tables support caching and why lookup speed alone does not guarantee cache correctness.
5. Discuss collision attacks and evaluate several defenses for an internet-facing service.

Analytical / Application Questions

1. A table has 12 buckets and 30 entries using chaining. Calculate the load factor and explain what the result implies about average bucket occupancy.
2. Design an exact deduplication service for event IDs arriving from multiple servers. Specify the data structure, memory and expiration policies, duplicate-handling rule, and failure considerations.
3. A storage engine uses a Bloom filter before disk lookup. Explain what actions are safe when the filter returns “absent” or “possibly present,” and discuss how changing the target false-positive rate affects memory and computation.

Multiple Choice Questions with Answers

Question 1

Which condition is required for a correct key type in a hash table?

A. Unequal keys must always have different hash codes.

B. Equal keys must produce equal hash codes.

C. Every key must have a cryptographic hash.

D. Hash codes must preserve sorted key order.

Correct Answer: B. Equal keys must produce equal hash codes.

Question 2

A chaining table contains 24 entries in 8 buckets. What is its load factor?

A. 0.33

B. 2

C. 3

D. 32

Correct Answer: C. 3

Question 3

Which collision strategy stores all entries directly in the table array?

A. Separate chaining

B. Open addressing

C. Tree traversal

D. Bloom filtering

Correct Answer: B. Open addressing

Question 4

Why are tombstones used in open-addressed hash tables?

A. To encrypt deleted keys

B. To preserve probe paths after deletion

C. To reduce the table capacity

D. To sort entries by key

Correct Answer: B. To preserve probe paths after deletion

Question 5

What must normally happen to entries after a hash table is resized?

A. They must be rehashed using the new capacity.

B. They must be discarded.

C. They must be sorted alphabetically.

D. They must be placed at their old indices.

Correct Answer: A. They must be rehashed using the new capacity.

Question 6

Under standard assumptions, what kind of error can a normal Bloom filter produce?

A. False negatives only

B. Both false negatives and false positives during correct operation

C. False positives but not false negatives

D. Neither false positives nor false negatives

Correct Answer: C. False positives but not false negatives

Question 7

Which application is most naturally suited to a hash index?

A. Finding all records with IDs in a numeric range

B. Finding records whose key exactly equals a supplied value

C. Returning records in alphabetical order

D. Finding strings with a given prefix

Correct Answer: B. Finding records whose key exactly equals a supplied value

Question 8

What is a major weakness of linear probing?

A. It cannot store values.

B. It causes primary clustering.

C. It requires linked lists for every bucket.

D. It permits unlimited occupancy.

Correct Answer: B. It causes primary clustering.

Question 9

What is the usual expected complexity of hash-table lookup when the load factor is controlled and hashing is suitable?

A. O(log n)

B. O(n log n)

C. O(1)

D. O(n²)

Correct Answer: C. O(1)

Question 10

Which practice helps defend an attacker-facing hash table against collision attacks?

A. Using predictable hash seeds

B. Removing all capacity limits

C. Using randomized hashing and monitoring pathological behavior

D. Allowing mutable keys

Correct Answer: C. Using randomized hashing and monitoring pathological behavior