Dictionaries, Hashing and Set Structures

Introduction and Context

Dictionaries and sets are among the most important abstract data types in computer science. A dictionary, also called a map or associative array, stores pairs of the form \((k,v)\), where a key \(k\) identifies an associated value \(v\). A set stores distinct elements and supports membership and set-algebra operations. Both structures are fundamental in compilers, databases, web services, operating systems, cybersecurity, and machine-learning systems.

Hashing is a principal technique for implementing dictionaries and sets efficiently. It transforms a key into an array position using a hash function. Under suitable assumptions, search, insertion, and deletion have expected constant-time complexity, written \(O(1)\). This does not mean that every operation always takes constant time. Performance depends on the quality of the hash function, the collision-resolution method, the load factor, resizing policy, memory layout, and whether inputs are benign or adversarial.

For AI and machine-learning programmers, hash-based structures are used in vocabulary indexes, feature dictionaries, memoization tables, graph representations, caches, duplicate detection, and data preprocessing pipelines. Understanding their limitations is essential because poorly designed hashing can cause severe performance degradation or security vulnerabilities.

Learning Objectives

After completing this chapter, you should be able to:

1. Explain dictionary and set abstractions and their principal operations.

2. Describe how hash functions map keys to table positions.

3. Analyze collisions, load factors, and expected performance.

4. Implement and compare separate chaining and open addressing.

5. Explain resizing and rehashing policies.

6. Select suitable hash-based structures for practical applications.

7. Identify security risks caused by weak hashing and adversarial inputs.

8. Explain how secure hashing differs from ordinary data-structure hashing.

Dictionary and Set Abstractions

A dictionary maintains a collection of key-value pairs with unique keys. Typical operations are:

• put(k, v): insert a new pair or replace the value associated with \(k\).
• get(k): return the value associated with \(k\), if present.
• remove(k): delete the pair associated with \(k\).
• containsKey(k): test whether a key exists.
• size(): return the number of stored pairs.

A set stores no separate values. Its fundamental operations are:

• add(x)
• remove(x)
• contains(x)
• union: elements in either set.
• intersection: elements in both sets.
• difference: elements in one set but not the other.

A dictionary can be viewed as a set of key-value records, while a set can be implemented as a dictionary whose values are irrelevant markers. In both cases, key equality is central. An implementation must define when two keys are equal and must ensure that equal keys receive compatible hash values.

A critical correctness rule is:

> If \(a = b\), then \(h(a) = h(b)\).

The converse is not required. Different keys may have the same hash value; this event is a collision.

Hash Tables

A hash table is an array of slots or buckets. A hash function \(h\) maps a key to an integer, which is then converted into a valid table index. If the table has \(m\) positions, a common indexing operation is

\[

index(k) = h(k) \bmod m.

\]

Here, \(h(k)\) is an integer hash code and \(m\) is the table capacity. The modulo operation is appropriate when the hash code is nonnegative or is normalized before indexing. Some implementations use bit masking when \(m\) is a power of two, but this is safe only when the hash function distributes low-order bits adequately.

A good general-purpose hash function should be:

• Deterministic: the same key produces the same hash during a table operation.
• Consistent with equality: equal keys produce equal hash codes.
• Fast: hashing should not dominate the operation cost.
• Well distributed: keys should spread across table positions.
• Insensitive to common patterns: simple sequential or structured keys should not cluster unnecessarily.

Hashing is not encryption. A normal hash-table hash function aims primarily at speed and distribution. It generally is not designed to conceal data or resist deliberate collision construction.

Collisions and the Load Factor

A collision occurs when two distinct keys map to the same table position. Collisions are unavoidable in most hash tables because the key space is usually much larger than the table.

The load factor is

\[

\alpha = \frac{n}{m},

\]

where \(n\) is the number of stored elements and \(m\) is the number of buckets or slots. The interpretation of \(\alpha\) depends on the collision-resolution strategy:

• In separate chaining, \(\alpha\) is the average number of entries per bucket and may exceed 1.
• In open addressing, every element occupies a table slot, so \(0 \leq \alpha < 1\), and performance usually deteriorates sharply as \(\alpha\) approaches 1.

For a uniformly distributed hash function, the expected chain length in separate chaining is \(\alpha\). A successful search generally examines approximately one-half of the relevant chain in a simple unsorted implementation, in addition to computing the hash. A useful approximate expression is

\[

1 + \frac{\alpha}{2},

\]

where the 1 represents the initial bucket access. For an unsuccessful search, the expected number of examined entries is approximately \(\alpha\), again under uniform hashing and a simple chaining implementation.

These are expected-performance models, not worst-case guarantees. If all keys enter one bucket, a hash table with chaining behaves like a linked list and operations can require \(O(n)\) time.

Worked Example: Load Factor

Suppose a chained table has \(m=10\) buckets and stores \(n=25\) key-value pairs. Its load factor is

\[

\alpha = \frac{25}{10}=2.5.

\]

Thus, the average bucket contains 2.5 entries. This does not mean every bucket contains exactly 2 or 3 entries; it is an average. With a reasonably uniform hash function, an unsuccessful search examines about 2.5 stored entries on average, while a successful search examines approximately

\[

1 + \frac{2.5}{2}=2.25

\]

entries under the simple approximation. The exact result depends on which keys are queried and on the distribution of chain lengths.

Separate Chaining

In separate chaining, each table position refers to a collection of entries, commonly a linked list, dynamic array, or balanced search tree. All keys assigned to the same bucket are stored in that collection.

Insertion

To insert \((k,v)\), the implementation computes the bucket index, searches that bucket for \(k\), updates the value if the key exists, or appends a new entry otherwise.

Search

To search for \(k\), the implementation computes the bucket index and compares \(k\) with entries in that bucket using the equality operation.

Deletion

Deletion removes the matching entry from its bucket. With linked-list chaining, deletion is straightforward once the entry or its predecessor has been found.

Advantages and Limitations

Chaining has several advantages:

• The table can store more elements than it has buckets.
• Deletion is conceptually simple.
• High load factors are possible, although performance declines.
• Collisions do not require probing for alternative slots.

Its limitations include pointer or object overhead, poorer cache locality in linked lists, and potentially linear-time behavior under severe clustering. Many modern implementations use small arrays or tree-based buckets rather than linked lists to improve locality or protect against long chains.

Open Addressing

In open addressing, every entry is stored directly in the table array. If the initial position is occupied, the algorithm probes other positions according to a deterministic probe sequence.

A general probe expression is

\[

index(k,i) = (h(k)+f(k,i)) \bmod m,

\]

where \(i=0,1,2,\ldots\) is the probe number and \(f

yields an offset. The probe sequence must eventually examine an appropriate set of slots; otherwise, an unused slot might be missed.

Linear Probing

Linear probing uses

\[

index(k,i)=(h(k)+i)\bmod m.

\]

It is simple and cache-efficient. However, it suffers from primary clustering: long consecutive runs of occupied slots form, increasing future probe lengths.

Quadratic Probing

Quadratic probing commonly uses

\[

index(k,i)=(h(k)+c_1i+c_2i^2)\bmod m,

\]

where \(c_1\) and \(c_2\) are chosen constants. It reduces primary clustering, but keys with the same initial hash may still follow related probe sequences, known as secondary clustering. The table size and constants must be selected carefully to ensure sufficient coverage.

Double Hashing

Double hashing uses a second hash function:

\[

index(k,i)=(h_1(k)+i h_2(k))\bmod m.

\]

The step size \(h_2(k)\) should be nonzero and chosen so that the probe sequence can reach all required slots. Double hashing generally reduces clustering more effectively than linear probing, at the cost of computing another hash.

Deletion and Tombstones

Deletion in open addressing cannot simply clear a slot. If a later key was placed after probing past that slot, clearing it could cause a search to stop too early. Implementations therefore use a special marker called a tombstone. Searches continue through tombstones, while insertion may reuse them.

Too many tombstones lengthen probe sequences. Periodic rebuilding or resizing removes them. An alternative is backward-shift deletion, which is appropriate for some linear-probing designs but requires careful maintenance of probe invariants.

Open-Addressing Performance

Open addressing requires an empty slot, so its load factor must remain below 1. Under uniform hashing, expected probe counts increase as \(\alpha\) grows. For linear probing, classical approximations for the expected number of probes are:

• successful search: approximately \(\frac{1}{2}\left(1+\frac{1}{1-\alpha}\right)\),
• unsuccessful search: approximately \(\frac{1}{2}\left(1+\frac{1}{(1-\alpha)^2}\right)

under the standard simplified model and sufficiently suitable table conditions. These formulas illustrate the sharp cost increase near \(\alpha=1\); they should not be treated as exact values for every implementation.

For example, at \(\alpha=0.5\), the unsuccessful-search approximation is

\[

\frac{1}{2}\left(1+\frac{1}{(1-0.5)^2}\right)

=\frac{1}{2}(1+4)=2.5

\]

probes. At \(\alpha=0.9\), it becomes

\[

\frac{1}{2}\left(1+\frac{1}{0.1^2}\right)=50.5

\]

probes. The dramatic difference explains why practical implementations resize before the table becomes nearly full.

Resizing and Rehashing

When a table becomes too full, the implementation allocates a larger table and inserts all existing entries into it again. This process is called rehashing. Entries cannot normally be copied to the same numerical positions because the index calculation depends on the new capacity.

A typical policy is geometric growth, such as doubling the capacity. If the capacity changes from \(m\) to approximately \(2m\), the amortized cost of repeated resizing remains constant per insertion under standard assumptions. A single resize costs \(O(n)\), but it occurs infrequently, so a sequence of \(n\) insertions has total expected cost \(O(n)\), or amortized \(O(1)\) per insertion, excluding unusually expensive hash computations.

A table may also shrink when its occupancy becomes sufficiently low. Shrinking too aggressively can cause resize thrashing, in which repeated insertions and deletions trigger alternating growth and shrink operations. Separate thresholds, such as a higher threshold for growth and a lower threshold for shrinking, reduce this risk.

Resizing must preserve the dictionary's logical contents. During rehashing, implementations must also preserve key equality semantics, handle exceptions safely, and avoid exposing a partially rebuilt structure to concurrent users.

Sets and Set Algebra

Hash-based sets use the same principles as hash-based dictionaries. A set stores each key once, often by using a dummy value in a map implementation.

If two sets are represented by hash tables, their operations have the following expected costs, assuming good hashing:

• membership in a set of size \(n\): expected \(O(1)\),
• union of sets of sizes \(n\) and \(r\): expected \(O(n+r)\),
• intersection: commonly \(O(\min(n,r))\) expected if the smaller set is scanned and membership is tested in the larger,
• difference: commonly \(O(n)\) when scanning the first set and testing membership in the second.

Choosing the smaller set for iteration is an important optimization. For example, to compute an intersection, insert the larger set into a hash set and scan the smaller set. This reduces the number of membership checks.

Sets are useful for duplicate removal, visited-node tracking in graph algorithms, feature vocabulary construction, permission checks, and maintaining active identifiers.

Correctness, Equality, and Mutable Keys

A dictionary implementation depends on a stable relationship between equality and hashing. If a key is mutable and its fields used by equality or hashing are changed after insertion, the key may become unreachable in the table even though it remains physically present.

For example, suppose a user object is inserted using its email address as the hash-relevant field. If the email is changed while the object remains in the table, a later lookup using the new email may search a different bucket, and lookup using the old email may fail because equality no longer matches. The safe practice is to use immutable keys or remove and reinsert an object after changing hash-relevant state.

Implementations must also define behavior for null keys, heterogeneous key types, custom equality, and hash-code overflow. These details differ among programming languages and libraries, so developers should consult the language specification rather than assume identical behavior across platforms.

Hash Functions: General-Purpose and Secure

A general-purpose hash function for a data structure prioritizes speed and statistical distribution. Examples include non-cryptographic functions designed for strings, integers, or byte sequences. Such functions are suitable for in-memory maps when input is trusted or when the implementation includes protection against collision attacks.

A cryptographic hash function has stronger properties, including resistance to finding preimages and collisions under specified computational assumptions. It is designed for integrity, digital signatures, password protocols, and content addressing—not necessarily for high-speed table indexing.

A secure hash for a hash table usually means a keyed or randomized hashing strategy that prevents an attacker from predicting collision patterns. A secret random seed can make it difficult for an attacker to construct many colliding keys. This differs from using a cryptographic digest directly: a cryptographic function may be unnecessarily expensive, and truncating its output must be done carefully.

Password storage requires a different approach again. Passwords should not be stored with a fast general-purpose hash. Password-hashing functions such as Argon2, scrypt, or bcrypt are deliberately expensive and memory-intensive, and should be combined with salts and appropriate operational controls.

Adversarial Inputs and Denial of Service

If an attacker can submit keys designed to collide, a hash table may degrade from expected \(O(1)\) operations to \(O(n)\) per operation. Repeated requests can then consume excessive CPU and memory, creating a denial-of-service condition.

Defensive measures include:

• randomized or keyed hash functions;
• limits on request size and number of parameters;
• maximum table or bucket thresholds;
• balanced trees for unusually long chains;
• periodic rebuilding with a new random seed;
• timeouts and rate limiting;
• monitoring for abnormal collision or probe behavior;
• using mature standard-library implementations.

Security analysis must consider the entire input path. Even if an application uses a robust hash table, parsing millions of keys, allocating large strings, or repeatedly resizing a table can still be exploited. Hashing is one part of a broader resource-management strategy.

Illustrative Case: A Vocabulary Service for Machine Learning

Background

Consider an illustrative natural-language processing service that converts tokens into integer identifiers for a neural-network pipeline. It receives documents from many users and maintains a dictionary mapping each token to a vocabulary ID. It also uses a set to track tokens already seen in a training batch.

Problem

The first implementation uses a small table with a deterministic, weak string hash and never resizes. Normal development data performs well, but production traffic contains many structured identifiers. Lookup latency increases sharply, memory use grows, and some requests consume excessive CPU.

Analysis

The table has a fixed capacity, so its load factor rises continuously. Structured inputs also produce clustering because the hash function does not distribute similar strings adequately. Since the service accepts user-controlled tokens, a malicious client could intentionally submit collision-heavy inputs. The set used for duplicate detection experiences the same weaknesses because it uses the same hashing strategy.

Approach and Solution

The engineering team adopts a mature hash-table implementation with randomized hashing and automatic resizing. The vocabulary table grows geometrically when its load factor crosses a configured threshold. Keys are immutable strings, and equality is defined by exact normalized token content. The service limits document size, applies request quotas, and records lookup latency and table occupancy. For very large or persistent vocabularies, it periodically writes a compact sorted representation to storage rather than retaining everything in memory.

The team also distinguishes responsibilities: a fast in-memory hash function is used for table indexing, while cryptographic hashes are used separately when verifying model artifacts and vocabulary files. Passwords and access credentials are not placed in the vocabulary dictionary.

Outcome

Average lookup remains close to constant time under ordinary workloads, memory use becomes predictable, and intentionally structured inputs no longer cause the same degree of clustering. Operational limits provide protection even if future implementation weaknesses are discovered.

Learning Points

The case demonstrates that good average complexity depends on design assumptions. A suitable hash function, resizing, immutable keys, input controls, observability, and separation of security functions are all necessary for a reliable production system.

Choosing Between Hash Tables and Alternatives

Hash tables are preferable when fast average membership or key lookup is required and sorted order is not central. A balanced search tree may be preferable when ordered traversal, range queries, or worst-case logarithmic guarantees are important. A sorted array can outperform both for static data because of compact storage and excellent cache locality, although insertion is expensive. A trie may be suitable for prefix queries on strings. Bloom filters can provide space-efficient approximate membership tests, but they permit false positives and cannot normally support exact deletion without specialized variants.

Professional design therefore begins with workload analysis:

• Are keys trusted or attacker-controlled?
• Is ordering required?
• What are the expected and maximum sizes?
• Are operations read-heavy, write-heavy, or deletion-heavy?
• Is memory locality important?
• Are deterministic worst-case guarantees required?
• Must the structure be concurrent or persistent?

Best Practices

1. Use established library implementations unless a specialized requirement justifies custom code.

2. Ensure equality and hashing obey the same logical definition of a key.

3. Prefer immutable keys.

4. Select a load-factor threshold appropriate to the collision strategy.

5. Resize before performance deteriorates sharply.

6. Account for tombstones in open-addressed tables.

7. Benchmark with realistic and adversarially structured inputs.

8. Separate ordinary indexing hashes from cryptographic and password hashes.

9. Bound input sizes and resource consumption in exposed services.

10. Measure memory as well as time; object and pointer overhead can dominate.

11. Document ordering guarantees, null behavior, concurrency properties, and worst-case behavior.

12. Test collisions, deletion, resizing, duplicate insertion, and mutable-key misuse.

Challenges and Limitations

Hash tables do not provide universal constant-time guarantees. Poor hash functions, adversarial keys, high load factors, expensive key comparisons, and resizing can all increase cost. Memory overhead may be substantial, especially for chained tables containing many objects. Hash-based structures also do not naturally support sorted iteration or range queries.

Concurrency introduces additional challenges. A table may require locks, striped synchronization, atomic operations, or a specialized concurrent algorithm. A resize that is safe in a single-threaded program may be unsafe when readers and writers operate simultaneously. Distributed dictionaries add concerns such as partitioning, replication, consistency, and network latency.

Finally, benchmark results are environment-dependent. Processor caches, allocator behavior, garbage collection, language runtime details, and key size can change the relative performance of chaining, probing, trees, and arrays.

Contemporary Developments

Modern runtimes increasingly use cache-friendly open addressing, compact metadata arrays, SIMD-assisted probing, and treeification of long collision chains. Randomized hashing is common in systems that process untrusted input. Immutable and persistent maps support functional programming and safe sharing, while distributed key-value stores extend dictionary concepts across machines.

In AI systems, hash-based feature maps and vocabulary tables may be replaced or supplemented by specialized structures such as count-min sketches, locality-sensitive hashing, approximate nearest-neighbor indexes, and embedding databases. These structures solve different problems: a conventional hash table answers exact equality queries, whereas locality-sensitive methods intentionally place similar—not identical—objects near one another. Selecting among them requires understanding the query semantics rather than treating all indexing methods as interchangeable.

Chapter Summary

Dictionaries map unique keys to values, while sets store distinct elements and support membership and set-algebra operations. Hash tables implement these abstractions by mapping keys to table positions. Collisions are unavoidable and must be managed through separate chaining or open addressing. The load factor \(\alpha=n/m\) is a central performance measure: in chaining it represents average entries per bucket, while in open addressing it must remain below one and usually be kept substantially lower.

Separate chaining simplifies deletion and tolerates high occupancy, but may incur pointer overhead and long chains. Open addressing offers compact, cache-friendly storage but requires careful probing, tombstones or specialized deletion, and conservative load-factor limits. Resizing and rehashing maintain performance as the table grows, with geometric resizing providing amortized constant-time updates under standard assumptions.

Correctness requires compatible equality and hashing and stable keys. General-purpose hashes optimize speed and distribution; cryptographic hashes serve integrity and security purposes; password hashing is deliberately slow and specialized. Attacker-controlled keys can cause collision-based denial of service, so randomized hashing, resource limits, monitoring, and mature implementations are important. Finally, hash tables should be selected according to workload, ordering needs, security assumptions, memory constraints, and required performance guarantees.

Key Terms

Hash table: An array-based structure that stores entries according to hash-derived positions.

Dictionary: An abstract data type mapping unique keys to values.

Set: An abstract data type containing distinct elements.

Key: An object used to identify a dictionary entry or set member.

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

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

Load factor: The ratio of stored elements to table capacity, \(\alpha=n/m\).

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

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

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

Linear probing: Open addressing that examines consecutive table positions.

Quadratic probing: Open addressing using a quadratic offset sequence.

Double hashing: Open addressing using a second hash function as the probe step.

Tombstone: A deletion marker retained in an open-addressed table.

Rehashing: Recomputing positions for entries after a table is rebuilt.

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

Clustering: The concentration of entries or probes in related table positions.

Cryptographic hash: A hash designed to provide security properties such as collision resistance.

Randomized hashing: Hashing that uses a random seed or secret to resist predictable collisions.

Mutable key: A key whose hash-relevant state can change after insertion.

Review Questions

Short Answer Questions

1. What is the difference between a dictionary and a set?

2. Define a collision and explain why collisions are unavoidable.

3. What does the load factor measure?

4. Why are tombstones used in open addressing?

5. Why should hash-relevant keys generally be immutable?

Long Answer Questions

1. Compare separate chaining and open addressing in terms of memory, deletion, clustering, and load-factor behavior.

2. Explain linear probing, quadratic probing, and double hashing, including one advantage and limitation of each.

3. Describe resizing and rehashing and explain why geometric growth gives amortized constant-time insertion.

4. Distinguish general-purpose, cryptographic, and password-hashing functions.

5. Explain how an attacker could exploit hash collisions and discuss several appropriate defenses.

Analytical / Application Questions

1. A chained hash table has 40 buckets and 120 entries. Calculate its load factor and discuss whether the value is necessarily unacceptable.

2. Design a set-based duplicate-detection component for a machine-learning data pipeline. Specify key representation, resizing policy, security controls, and how you would test it.

3. An open-addressed table shows rapidly increasing unsuccessful-search latency although its number of entries has barely changed. Analyze at least three possible causes and propose diagnostic actions.

Multiple Choice Questions with Answers

Question 1

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

A. If two keys have different values, their hashes must differ

B. If two keys are equal, their hash values must be equal

C. Every key must hash to a unique table position

D. The table capacity must equal the number of keys

Correct Answer: B. If two keys are equal, their hash values must be equal

Question 2

A hash table has 18 buckets and 45 stored entries. What is its load factor?

A. 0.4

B. 1.8

C. 2.5

D. 27

Correct Answer: C. 2.5

Question 3

Which collision-resolution method stores all 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 simply clearing a deleted slot break open-addressed search?

A. It changes the hash function

B. It may cause a later key's probe sequence to stop too early

C. It increases the table capacity

D. It converts the key into a tombstone

Correct Answer: B. It may cause a later key's probe sequence to stop too early

Question 5

Which technique is specifically associated with primary clustering?

A. Linear probing

B. Separate chaining with trees

C. Cryptographic hashing

D. Binary search

Correct Answer: A. Linear probing

Question 6

What normally happens during rehashing?

A. Only deleted entries are removed

B. Existing entries are placed into a new table using the new capacity

C. All keys are sorted permanently

D. Hashing is eliminated

Correct Answer: B. Existing entries are placed into a new table using the new capacity

Question 7

For two sets of sizes n and r, what is a common expected-time strategy for intersection?

A. Scan the larger set and linearly search the smaller

B. Hash the larger set and scan the smaller

C. Sort both sets using insertion sort regardless of size

D. Compare every pair of elements

Correct Answer: B. Hash the larger set and scan the smaller

Question 8

Which statement best distinguishes a cryptographic hash from an ordinary table hash?

A. A cryptographic hash is designed for security properties, not merely speed and distribution

B. A cryptographic hash never produces collisions

C. An ordinary table hash must conceal its input

D. Cryptographic hashes cannot process strings

Correct Answer: A. A cryptographic hash is designed for security properties, not merely speed and distribution

Question 9

At a load factor of 0.9, why can unsuccessful linear-probing searches become expensive?

A. The table has too many empty slots

B. The approximate probe cost rises sharply as 1 minus the load factor becomes small

C. Hash functions stop producing integers

D. Deletion becomes impossible in chaining

Correct Answer: B. The approximate probe cost rises sharply as 1 minus the load factor becomes small

Question 10

Which practice best protects an exposed service from collision-based denial of service?

A. Use a fixed tiny table and disable resizing

B. Accept unlimited attacker-controlled keys

C. Use randomized or keyed hashing together with resource limits

D. Store every key in the first bucket

Correct Answer: C. Use randomized or keyed hashing together with resource limits