Hash Tables and Associative Structures

Introduction

Many software systems must answer questions such as “Does this username exist?”, “What value is associated with this key?”, or “Has this object already been seen?” Searching an unsorted collection may require examining every element. A hash table addresses these questions by transforming a key into an array position, usually providing expected constant-time insertion, lookup, and deletion.

Hash tables are the principal implementation technique behind sets, maps, symbol tables, caches, database indexes, routing tables, and many language runtimes. Their speed, however, is probabilistic rather than absolute. Performance depends on the quality of the hash function, the table’s load factor, collision-handling strategy, resizing policy, and the characteristics of the input. Poor choices can produce severe slowdowns and, in adversarial settings, denial-of-service vulnerabilities.

This chapter develops the design and analysis of hash tables and related associative structures. It distinguishes expected performance from worst-case guarantees and connects implementation decisions with practical software engineering and security.

Learning Objectives

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

1. Explain the abstract map and set interfaces and their relationship to hash tables.
2. Describe hash functions, collisions, load factor, and uniform distribution.
3. Compare separate chaining with open addressing.
4. Analyze expected and worst-case time and space complexity.
5. Explain insertion, lookup, deletion, resizing, and rehashing.
6. Select appropriate structures for maps, sets, caches, and indexes.
7. Identify security risks, including hash flooding and unsafe key handling.
8. Evaluate a hash-table design in a realistic application.

1. Associative Structures: Maps and Sets

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

• put(k, v): associate key k with value v, replacing an existing value if the key is present;
• get(k): return the value associated with k;
• remove(k): delete the association for k;
• containsKey(k): test whether k is present.

A set stores distinct elements and supports insertion, deletion, and membership testing. A set can be implemented as a map whose values are irrelevant or represented by a shared marker. Thus, the same hashing principles support both structures.

A hash table consists conceptually of an array of buckets or slots and a function that maps keys to indices. If the table has capacity m, a hash value is converted to an index in the range 0 through m−1. A common abstract mapping is:

Here, h(k) is a non-negative integer hash value and m is the number of slots. This formula is applicable when indices are obtained by division and the modulus operation is implemented efficiently. Some implementations use power-of-two capacities and select low-order bits instead; in that case, the hash function must adequately mix those bits.

A hash table does not require keys to be numeric. Strings, records, tuples, and objects can be hashed provided that a deterministic hash procedure is defined.

2. Hash Functions and Their Requirements

A hash function maps a key from a potentially large domain to a fixed range of integer values:

Here, U is the key domain and w is the number of output bits. A practical hash function should have the following properties:

Determinism. The same key, under the same hashing rules, produces the same hash value during a table operation. If an object is mutable, fields used in its hash must not change while it is stored.

Consistency with equality. If two keys are equal, they must have equal hash values. The converse is not required: unequal keys may collide.

Efficiency. Hash computation should be substantially cheaper than the operation it accelerates. Hashing a very large object may itself be expensive.

Good distribution. Keys occurring in the application should be spread across the available slots. Uniformity reduces collisions and preserves expected performance.

Appropriate mixing. Simple schemes such as adding character codes can give identical or highly similar values for many different keys. Modern non-cryptographic hashes mix input bits more effectively.

A hash function used for a hash table is not automatically a cryptographic hash. Cryptographic hashes are designed for properties such as preimage resistance and collision resistance against attackers; table hashes generally prioritize speed and distribution. A keyed, randomized hash is often preferable when untrusted users can choose keys.

Equality, Identity, and Mutable Keys

The table must define what it means for two keys to be the same. For strings, equality normally means identical sequences of characters. For objects, a program may use value equality or object identity. These choices must be explicit.

Suppose a key’s hash depends on its account number and the account number is changed after insertion. A lookup using the modified object may search a different bucket and fail to find an entry that remains physically present. Best practice is to use immutable keys, or to remove and reinsert an object after changing any field used by equality or hashing.

3. Collisions

A collision occurs when two unequal keys map to the same slot. Collisions are unavoidable when a large or unlimited key domain is mapped to a finite table. The design question is therefore not how to eliminate collisions, but how to resolve them efficiently.

3.1 Separate Chaining

With separate chaining, each array slot refers to a collection—often a linked list, dynamic array, or balanced tree—containing all entries assigned to that slot. To find a key, the implementation hashes it, selects a chain, and searches that chain using equality.

If there are n entries and m buckets, the load factor is:

For chaining, α may exceed 1 because a chain may contain several entries. Under simple uniform hashing, the expected number of entries examined in an unsuccessful search is approximately α, while a successful search examines approximately 1 + α/2 entries when insertion order is not biased. These are average-style estimates, not guarantees, and exact values depend on the chain organization and search convention.

Chaining makes deletion straightforward: find the entry in its chain and remove it. It also tolerates a temporarily high load factor, although long chains increase time and memory overhead.

3.2 Open Addressing

In open addressing, every entry is stored directly in the table array. A collision causes the algorithm to examine a sequence of alternative slots, called a probe sequence, until it finds the key or an unused slot.

Common probing methods include:

• Linear probing: (h(k) + i) mod m, where i = 0, 1, 2, ….
• Quadratic probing: a sequence such as (h(k) + c₁i + c₂i²) mod m.
• Double hashing: (h₁(k) + i h₂(k)) mod m.

In these expressions, m is capacity, i is the probe number, and c₁, c₂ are chosen constants. The constants and capacity must be selected so that the probe sequence reaches enough slots; otherwise insertion may fail even when some slots are unused.

Linear probing is cache-friendly because nearby locations are examined, but it suffers from primary clustering: long occupied runs attract more entries. Quadratic probing reduces some clustering but can still have limitations. Double hashing generally produces more dispersed probe sequences, provided h₂(k) is nonzero and compatible with the capacity.

Deletion is more subtle in open addressing. Simply clearing a slot can break the probe sequence of keys inserted later. Implementations therefore use a tombstone marker, continue probing past deleted slots, and eventually rebuild the table. Tombstones preserve correctness but lengthen searches, so periodic rehashing is useful.

For open addressing, α < 1 is mandatory because every entry occupies a table slot. Performance deteriorates rapidly as α approaches 1. A common implementation resizes before the load factor reaches a threshold such as 0.7 or 0.8, though the best threshold depends on the probing method, memory constraints, and workload.

4. Load Factor, Resizing, and Amortized Cost

The load factor is:

where n is the number of stored entries and m is the table capacity. It measures occupancy relative to available buckets or slots. It is dimensionless because both numerator and denominator count entries or positions.

A table usually grows when α exceeds an upper threshold. A typical strategy doubles capacity, allocates a new array, and reinserts every existing key using the new capacity. This is called rehashing. Entries cannot simply be copied to the same indices because the index calculation depends on m. Some tables shrink when occupancy falls below a lower threshold, but aggressive shrinking can cause repeated expansion and contraction, known as oscillation.

A single resize costs Θ(n) because all current entries are processed. Nevertheless, geometric growth gives amortized constant update cost. If capacity doubles whenever a threshold is exceeded, an entry is moved only a logarithmic number of times over a long sequence of operations, and the total movement over N insertions is O(N). Therefore the amortized cost per insertion is O(1), although an individual insertion that triggers resizing costs Θ(n).

Worked Example: Resizing

Assume a chained table has capacity m = 8, contains n = 6 entries, and grows when α > 0.75. Its load factor is:

An additional insertion produces n = 7 and therefore:

Because 0.875 exceeds 0.75, the table may grow to capacity 16. After rehashing the seven entries, the new load factor is:

The resize is expensive at that moment, but future operations benefit from shorter chains and the total cost remains amortized constant under geometric resizing.

5. Algorithms

Chained Lookup

A chained lookup proceeds as follows:

1. Compute the key’s hash value.
2. Convert it to a valid bucket index.
3. Traverse the selected chain.
4. Compare each stored key with the search key.
5. Return the associated value if equality succeeds; otherwise report absence.

Insertion first searches for the key. If it exists, its value is updated; otherwise a new entry is added to the chain. This distinction prevents accidental duplicate keys in a map.

Open-Addressed Lookup

An open-addressed lookup computes the first probe position and follows the probe sequence. It returns a matching entry if found. It returns “absent” when it reaches a genuinely empty slot, because no later entry could have crossed that never-used position during ordinary insertion. Tombstones are skipped, not treated as evidence of absence.

Pseudocode for Chained Map Insertion

put(key, value):
    i ← index(hash(key))
    for entry in bucket[i]:
        if equal(entry.key, key):
            entry.value ← value
            return
    append (key, value) to bucket[i]
    n ← n + 1
    if n / m > maximumLoadFactor:
        resize()

A production implementation must also specify behavior for null keys, hash exceptions, concurrent access, memory allocation failure, and key mutation.

6. Complexity Analysis

Under a suitable hash function, a bounded load factor, and a reasonably uniform distribution, map and set operations have expected complexity O(1). This means the expected cost does not grow linearly with the number of entries under the stated assumptions.

The main assumptions are:

1. Hash computation takes O(1) time, or its cost is treated separately.
2. Keys are distributed sufficiently uniformly.
3. The resizing policy controls the load factor.
4. Equality comparisons are constant-time or bounded independently of table size.

Worst-case complexity remains O(n) for lookup, insertion, or deletion if all keys collide or if an open-addressing probe sequence examines nearly the whole table. Some implementations convert long chains into balanced trees, giving approximately O(log n) worst-case search within a bucket, while retaining expected constant-time behavior when chains are short. This improves robustness but does not make hashing universally worst-case constant time.

Space complexity is Θ(n + m) for a table with n entries and m slots, including unused capacity. Chaining requires references and entry objects; open addressing usually has lower pointer overhead but may require more empty slots to maintain speed.

These bounds should not be confused with ordered structures. A hash table is excellent for exact-key access but does not naturally support sorted traversal, predecessor queries, or range searches. A balanced search tree generally offers O(log n) worst-case operations and maintains key order.

7. Hash Tables as Caches and Indexes

A cache stores recently or frequently used results so that an expensive operation can be avoided. A hash map can associate a request key with a cached value. A practical cache usually combines a hash table with a policy such as least recently used (LRU). The hash table gives direct access to an entry, while a doubly linked list records recency. With both structures, lookup and promotion can be expected O(1).

Caches require additional decisions: maximum memory, expiration time, invalidation, concurrent access, duplicate requests, and behavior when the backing data changes. Hashing alone does not solve stale data or consistency problems.

Indexes in databases and storage systems map search attributes to records, pages, or locations. Hash indexes are effective for equality predicates such as WHERE account_id = 42, but poor for ordered queries such as ranges. Database systems may use bucket overflow pages, dynamic hashing, or B-trees depending on workload and persistence requirements. An in-memory hash table should not be assumed durable: crashes, synchronization, and recovery require separate mechanisms.

8. Security and Reliability Risks

Hash Flooding

If an attacker can submit many keys that collide, a chained table may degenerate into a long list and consume O(n) time per operation. Repeated requests can produce denial of service. Open addressing can suffer similarly through long probe sequences.

Defenses include randomized or keyed hashing, limits on request size and key count, load-factor monitoring, tree-based fallback for unusually long chains, and rate limiting. A secret seed makes it harder for an external attacker to predict collisions, although it does not replace resource limits.

Hash-Algorithm Confusion

Cryptographic hashes and table hashes serve different purposes. Using an unkeyed fast hash where adversaries control keys may be unsafe. Conversely, using an expensive cryptographic hash for every ordinary in-memory lookup may impose unnecessary cost. The selection should reflect threat model, input control, and performance requirements.

Denial of Service Through Memory Growth

An attacker may send many distinct keys rather than colliding keys. Even with excellent distribution, an unbounded map consumes memory. Applications should impose quotas, evict cache entries, reject oversized keys, and monitor memory pressure.

Side Channels and Sensitive Data

Hash tables can reveal timing or memory-access patterns. This matters in high-assurance systems and some cryptographic contexts. A general-purpose map should not be used as a constant-time cryptographic primitive unless its implementation and threat model have been specifically analyzed.

Concurrency

Concurrent modifications can corrupt a table or lose updates if operations are not synchronized. Options include locks, segmented or striped tables, atomic techniques, immutable snapshots, and specialized concurrent maps. Resizing is especially difficult because readers and writers may observe different table arrays. The correct choice depends on consistency requirements rather than on speed alone.

9. Meaningful Design Case: A Multi-Tenant API Rate Limiter

The following is an illustrative case, not a report of a particular company.

Background. A service exposes an API to thousands of organizations. It must count requests for each pair of tenant identifier and time window, reject requests exceeding a quota, and keep the decision fast.

Problem. The service receives untrusted tenant identifiers and traffic can be highly uneven. A few tenants may generate most requests, while an attacker may submit many fabricated identifiers. The system must avoid unbounded memory use and must remain responsive during bursts.

Analysis. A composite key such as (tenantId, windowStart) can be stored in a hash map. Expected lookup and update are constant time, making a hash table more appropriate than scanning a list. However, the key domain is attacker-influenced, so predictable hashing may enable flooding. Counters also expire, meaning entries must not live indefinitely.

Approach. The design uses a keyed, well-distributed hash function; an explicit maximum key length; per-client and global limits; and a bounded cache with expiration. Each request hashes its composite key, retrieves the counter, checks the timestamp, increments the count, and rejects or permits the request. Periodic expiration removes old windows. The implementation monitors table size, average probe or chain length, and resize frequency. In a distributed deployment, the counters are kept in a shared store or partitioned consistently; a local hash table alone cannot enforce a global quota.

Outcome. Under ordinary traffic, expected constant-time access supports high throughput. Resource bounds limit memory exhaustion, while keyed hashing reduces the feasibility of deliberate collision attacks. The system still must address clock consistency, network failure, race conditions, and the semantics of requests arriving at a window boundary.

Learning points. Data-structure selection is only one part of system design. Correctness depends on key equality and time-window rules; security depends on adversarial analysis; and scalability depends on whether state is local or distributed.

10. Best Practices and Selection Guidance

Use a hash table when the dominant operation is exact-key membership or retrieval and ordering is unnecessary. Prefer a tree when sorted iteration, range queries, or predictable logarithmic worst-case behavior is important. Use a specialized cache when eviction and expiration are central requirements.

Good engineering practice includes:

• define equality and hashing together;
• keep keys immutable while stored;
• measure realistic workloads rather than assuming uniform random keys;
• choose and document load-factor thresholds;
• resize geometrically, while preventing unbounded growth;
• account for the cost of hashing long keys;
• use keyed or randomized hashing for attacker-controlled keys;
• handle deletion correctly, especially with tombstones;
• test empty tables, duplicate keys, collisions, resize boundaries, and deletion sequences;
• instrument chain lengths, probe lengths, memory use, and resize events;
• make concurrency and failure semantics explicit.

Modern runtimes often optimize hash tables with compact layouts, treeified buckets, randomized seeds, or specialized representations for small maps. These optimizations do not change the fundamental contracts: equality must agree with hashing, collisions must be handled correctly, and expected complexity depends on assumptions.

Chapter Summary

Hash tables implement associative access by transforming keys into array positions. They support maps and sets and normally provide expected O(1) lookup, insertion, and deletion when hashing is efficient, keys are well distributed, and load is controlled. Collisions are inevitable and are handled primarily through separate chaining or open addressing. Chaining simplifies deletion and permits load factors above one; open addressing improves locality but requires careful probing and a load factor below one.

The load factor α = n/m guides resizing. Geometric resizing causes occasional Θ(n) operations but gives amortized O(1) updates. Worst-case operations remain O(n) unless additional mechanisms, such as balanced-tree buckets, are used. Hash tables are valuable in maps, sets, caches, and equality-based indexes, but they are not naturally suited to ordered or range queries.

Correct hashing requires determinism, equality consistency, efficiency, and good distribution. Security requires attention to hash flooding, memory exhaustion, untrusted keys, concurrency, and sensitive timing behavior. Sound design therefore combines algorithmic analysis with application requirements, threat modeling, resource limits, and testing.

Key Terms

Hash table: An array-based structure that uses hashes to support associative access.

Map: A collection of unique keys associated with values.

Set: A collection of distinct elements supporting membership operations.

Hash function: A function that maps a key to an integer hash value.

Bucket: A location containing one or more entries, especially in chaining.

Slot: A position in an array, especially in open addressing.

Collision: The event in which unequal keys map to the same position.

Load factor: The ratio α = n/m of entries to table capacity.

Separate chaining: Collision resolution using a collection at each bucket.

Open addressing: Collision resolution in which entries remain in the table array.

Probe sequence: The ordered positions examined during open-addressed access.

Linear probing: Probing successive positions with a fixed step of one.

Tombstone: A marker for a deleted open-addressed entry.

Rehashing: Reinserting entries using a newly sized table or new hash parameters.

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

Hash flooding: A deliberate collision attack that degrades table performance.

Key immutability: The property that hash-relevant key state does not change while stored.

Cache: A bounded store of reusable data or results.

Hash index: An index supporting efficient equality-based retrieval.

Review Questions

Short Answer Questions

1. What is the difference between a map and a set?
2. Why are collisions unavoidable in a finite hash table?
3. Define the load factor and identify its variables.
4. Why must a key remain stable while it is stored in a hash table?
5. What is the purpose of a tombstone in open addressing?

Long Answer Questions

1. Compare separate chaining and open addressing in terms of memory layout, deletion, locality, and load-factor requirements.
2. Explain why geometric resizing provides amortized constant-time insertion even though an individual resize costs linear time.
3. Describe the requirements of a reliable hash function and explain why equality consistency is essential.
4. Compare the suitability of hash tables and balanced search trees for exact lookup, ordered traversal, and range queries.
5. Explain how hash flooding and unbounded key creation can threaten an online service, and discuss appropriate defenses.

Analytical / Application Questions

1. A table has 32 slots, 20 entries, and a growth threshold of 0.75. Determine whether inserting one additional entry should trigger resizing, and calculate the load factor after resizing to 64 slots.
2. Design a data structure for an LRU cache. Explain how a hash map and a doubly linked list cooperate to achieve expected constant-time lookup, insertion, promotion, and eviction.
3. An API rate limiter stores attacker-controlled composite keys. Evaluate the risks of a basic hash table and propose a design covering hashing, memory bounds, expiration, concurrency, and distributed deployment.

Multiple Choice Questions with Answers

Question 1

Which condition is required for a correct hash-based map?

A. Equal keys must always have equal hash values.

B. All unequal keys must have different hash values.

C. Every key must map to bucket zero.

D. Hash values must be cryptographic.

Correct Answer: A. Equal keys must always have equal hash values.

Question 2

A table contains 12 entries and has capacity 16. What is its load factor?

A. 0.25

B. 0.50

C. 0.75

D. 1.33

Correct Answer: C. 0.75

Question 3

Which collision-resolution method stores entries directly in the table array?

A. Separate chaining

B. Open addressing

C. Tree traversal

D. External sorting

Correct Answer: B. Open addressing

Question 4

Why can a table not simply clear an occupied slot after deletion in open addressing?

A. It would change the hash function.

B. It would make the table too sparse immediately.

C. It could break the probe sequence for another key.

D. It would convert the table into a set.

Correct Answer: C. It could break the probe sequence for another key.

Question 5

Under suitable distribution and controlled load, the expected lookup time in a hash table is:

A. O(log n)

B. O(n log n)

C. O(n)

D. O(1)

Correct Answer: D. O(1)

Question 6

What is the main reason entries must be rehashed after a capacity change?

A. Entry values become encrypted.

B. The index calculation depends on the table capacity.

C. Equality comparisons stop working.

D. Tombstones cannot be copied.

Correct Answer: B. The index calculation depends on the table capacity.

Question 7

Which workload is generally best suited to a hash index?

A. Finding records with an exact key

B. Returning all keys in sorted order

C. Finding every key in a numeric range

D. Computing a minimum key repeatedly

Correct Answer: A. Finding records with an exact key

Question 8

What attack deliberately creates many hash collisions?

A. Buffer overflow

B. Hash flooding

C. Cache warming

D. Deadlock

Correct Answer: B. Hash flooding

Question 9

A chained table has 7 entries and 8 buckets. After inserting one entry, what is the load factor if capacity remains 8?

A. 0.75

B. 0.875

C. 1.125

D. 8.0

Correct Answer: B. 0.875

Question 10

Which practice is safest for objects used as hash keys?

A. Mutate hash-relevant fields after insertion.

B. Use mutable fields without defining equality.

C. Keep hash-relevant key state immutable while stored.

D. Use a different equality rule for every lookup.

Correct Answer: C. Keep hash-relevant key state immutable while stored.