Hashing, Sets, and Maps

Introduction

Many programs repeatedly ask questions such as “Have we seen this value?”, “How many times has this item occurred?”, or “What record belongs to this identifier?” A sequential search through an array or list costs O(n) time in the worst case. Hash-based structures address these lookup-intensive tasks by transforming a key into an array position. With a suitable hash function and controlled table occupancy, insertion, deletion, and lookup have expected O(1) time.

Hashing is not magic and O(1) is not guaranteed. Performance depends on hash quality, collision handling, resizing policy, memory, and the cost of equality testing. Java and Python provide mature hash-based collections, but effective use requires understanding their contracts and limitations.

Learning Objectives

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

• explain hash functions, collisions, load factor, and expected complexity;
• compare separate chaining with open addressing;
• describe resizing and capacity selection;
• use Java HashMap and HashSet and Python dict and set correctly;
• apply hashing to indexing, caching, counting, deduplication, and lookup systems;
• identify mutability, collision, memory, security, and ordering concerns.

1. The Hash Table Model

A hash table stores entries associated with keys. A map stores key–value pairs; a set stores keys only. A hash function maps a key to an integer hash code. The table converts that code to an index among m slots, commonly by a remainder operation:

Here, h(k) is the hash code for key k and m is the number of table slots. This formula assumes that the hash code is interpreted as an integer and that the implementation handles negative values safely. Some implementations use power-of-two capacities and bit masking rather than a remainder operation.

A good hash function has three practical properties:

1. Equal keys always produce equal hash codes.
2. Unequal keys should be distributed broadly across slots.
3. Computing the hash should be inexpensive relative to the operation being supported.

The second property is probabilistic: different keys may necessarily share a hash code or table index. Such an event is a collision.

Maps and sets

A map represents a partial function from keys to values. A key normally occurs at most once, although inserting a key again replaces its associated value. A set represents membership: an element is either present or absent. Internally, a set can be implemented as a map whose values are irrelevant placeholders.

Common operations are:

The stated costs are expected amortized costs under reasonable hashing and resizing assumptions. Worst-case lookup can be O(n), for example when many keys occupy one chain or an open-addressed table becomes highly clustered.

2. Collisions and Collision Resolution

A collision occurs when two keys are assigned the same slot, even if their full hash codes differ. The two principal approaches are separate chaining and open addressing.

Separate chaining

With separate chaining, each slot refers to a collection—often a linked list, dynamic array, or tree—of entries assigned to that slot. A lookup computes the slot and then compares the requested key with entries in that collection.

If n entries are distributed over m slots, the load factor is:

where α is the load factor, n is the number of stored entries, and m is the number of slots. In a simple uniform-hashing model, the expected number of entries in a chain is α. A successful lookup examines a constant expected number of entries when α is bounded by a fixed threshold. An unsuccessful lookup examines, on average, approximately α entries, apart from implementation-specific details.

Chaining can continue beyond the nominal table capacity, so insertion remains possible even when n exceeds m. Its disadvantages include extra references, allocation overhead, and poorer cache locality.

Open addressing

Open addressing stores every entry directly in the table. When a preferred slot is occupied, the algorithm probes other slots according to a deterministic sequence.

• Linear probing: probe indices separated by a fixed step, commonly 1. It is simple and cache-friendly but suffers from primary clustering.
• Quadratic probing: use offsets such as 1², 2², 3², reducing some clustering but requiring careful capacity and probe-sequence choices.
• Double hashing: use a second hash function to determine the step size, often producing better probe distributions.

Deletion is more difficult than insertion. Simply clearing a slot may cause a later search to stop too early, so implementations commonly use a tombstone marker or perform cluster repair. Open addressing requires spare capacity; as α approaches 1, probe lengths increase sharply. Consequently, a maximum load factor is normally lower than one.

Comparison

3. Resizing and Amortized Complexity

As a table fills, the implementation allocates a larger table and rehashes existing entries. Rehashing is necessary because an index computed with one capacity is generally invalid after the capacity changes.

Suppose a table grows from m slots to approximately 2m slots. A resize costs O(n) for n existing entries. However, if resizing occurs only after the table has accumulated a substantial number of new entries, the total cost spread across many operations is O(1) amortized per insertion. “Amortized” does not mean every insertion is constant time: the resize-triggering insertion may be expensive.

A simplified capacity rule for a chaining table is:

where α_max is the chosen maximum load factor. If n = 750 and m = 1000, then α = 0.75. A table with α_max = 0.75 would resize before accepting another entry, depending on the exact implementation policy.

Resizing improves expected lookup time but consumes memory and temporarily requires space for the new table. A program that knows its approximate input size can often provide an initial capacity and avoid repeated growth.

4. Key Equality and Hash Contracts

Hashing depends on two linked operations: computing a hash and testing equality. A correct key type must obey this rule:

If a.equals(b) is true in Java, then a.hashCode() must equal b.hashCode().

Python expresses the same principle through __eq__ and __hash__: equal objects must have equal hashes. The reverse is not required; unequal objects may share a hash.

Keys should be immutable while stored. If fields used by equality or hashing change after insertion, the entry may remain in a bucket determined by its old hash while future lookup uses its new hash. The data has not necessarily disappeared, but the table can no longer find it normally.

A robust key comparison should also distinguish type and relevant fields appropriately. Hashing only one field when equality uses several fields can produce many collisions, although it remains logically correct if the equality contract is preserved.

5. Java HashMap and HashSet

Java’s HashMap<K,V> stores mappings and permits one null key and multiple null values. HashSet<E> stores unique elements and is implemented conceptually using a hash map. Java’s general-purpose hash collections do not promise iteration order. If predictable insertion order is required, use LinkedHashMap or LinkedHashSet; if sorted order is required, consider TreeMap or TreeSet.

Map<String, Integer> counts = new HashMap<>();
counts.put("blue", 1);
counts.put("blue", counts.getOrDefault("blue", 0) + 1);

Set<String> seen = new HashSet<>();
seen.add("A");
boolean alreadySeen = !seen.add("A");

getOrDefault is useful, but a map may deliberately contain a null value. When absence and null must be distinguished, use containsKey or an appropriate value representation.

Modern Java implementations use collision-management strategies that may transform a heavily populated bucket into a balanced tree under suitable conditions, improving certain worst-case behaviors. Exact thresholds and internal structures are implementation details and should not be treated as portable application contracts.

Java key design

A class used as a key should normally be immutable and override both equals and hashCode consistently. Java records are convenient for value-like keys because their component-based equality and hashing are generated automatically.

record Coordinate(int x, int y) {}

Map<Coordinate, String> labels = new HashMap<>();
labels.put(new Coordinate(2, 3), "entrance");
String label = labels.get(new Coordinate(2, 3));

The two Coordinate objects compare equal by value, so the lookup succeeds.

6. Python dict and set

Python’s dict maps hashable keys to values, and set stores unique hashable elements. Lists, dictionaries, and ordinary mutable sets are not hashable because their contents can change. Tuples may be hashable when all their components are hashable.

counts = {}
for word in text.split():
    counts[word] = counts.get(word, 0) + 1

seen = set()
unique = []
for item in records:
    if item not in seen:
        seen.add(item)
        unique.append(item)

Python dictionaries preserve insertion order in current language specifications, but ordering should not be confused with sorting. A set is unordered for application purposes; code should not depend on a particular set iteration sequence.

Useful operations include mapping.get(key, default), key in mapping, item in set, and set algebra such as union (|), intersection (&), difference (-), and symmetric difference (^). These operations express membership logic clearly and are generally more efficient than repeated list scans.

Python’s hash randomization can cause hash-related iteration details to differ between processes. This improves resistance to some collision attacks but reinforces the rule that serialized or user-visible order should be made explicit.

7. Worked Applications

Counting frequencies

Given 10 million log events and 50,000 possible event codes, a dictionary keyed by event code stores a counter for each code. Each event causes one expected O(1) lookup and update, so the expected total is O(n), where n is the number of events. A list search for the code would cost O(nk) in the worst conceptual arrangement, where k is the number of distinct codes examined per event.

Deduplication

To preserve the first occurrence of records, maintain a set of identifiers. For each record, test membership; if absent, emit the record and insert its identifier. Expected time is O(n), and additional space is O(u), where u is the number of distinct identifiers. A duplicate test based on a mutable record should instead use a stable immutable identifier.

Caching

A cache maps a request signature to a result. The signature must include every input that affects the result. A cache hit avoids recomputation, but stale values, unbounded memory growth, and concurrent updates require policies such as expiration, size limits, invalidation, and synchronization. Hashing improves access; it does not solve cache correctness.

8. Illustrative Case: Indexing a Course Catalogue

Background. A college catalogue contains 120,000 courses. Users search repeatedly by course code, department, and prerequisite identifier.

Problem. A naive implementation scans the entire list for every request. During registration, response time becomes unpredictable, and duplicate course codes are difficult to detect.

Analysis. Course codes are stable, unique identifiers. A map from code to course object supports direct expected-constant-time retrieval. A set of codes detects duplicates during import. A second map from department to a set of course codes supports department membership. A prerequisite graph may use a map from course code to a set of prerequisite codes.

Approach. During loading, validate each code, reject duplicates, and build the indexes. Keep the course objects immutable or ensure that fields used as keys never change. Rebuild indexes when catalogue data is replaced rather than mutating key fields in place. Monitor memory usage and measure real workloads rather than assuming ideal distribution.

Outcome. Lookup becomes independent of catalogue length in expected terms, while import validation identifies data-quality errors early. The design uses maps for association and sets for uniqueness and membership.

Learning points. The correct key is more important than the collection alone; indexes must be maintained as data changes; and expected complexity must be checked against actual workload, memory, and correctness requirements.

9. Limitations, Security, and Best Practices

Hash tables are not suitable when sorted traversal, range queries, or predictable ordering is central. A balanced search tree may be preferable for ordered operations. Hash tables also consume more memory than compact arrays and may perform poorly with adversarial or poor-quality hashes.

Collision attacks can deliberately create many colliding keys, causing excessive CPU use. Public-facing services should use trusted platform implementations, avoid exposing unsafe custom hash functions, impose input and resource limits, and monitor abnormal request patterns. Hashing passwords is a different security task: passwords require dedicated slow password-hashing algorithms with salts, not ordinary collection hashes.

Recommended practices include:

• choose immutable, semantically appropriate keys;
• implement equality and hashing together;
• select an initial capacity when input size is known;
• do not rely on accidental ordering;
• distinguish missing values from legitimate null-like values;
• avoid modifying collections during iteration unless the API explicitly supports it;
• measure memory and latency under realistic data distributions;
• use synchronized or concurrent collections when multiple threads share mutable state;
• never assume expected O(1) means constant latency under all inputs.

Contemporary Perspective

Hash-based collections remain foundational in databases, compilers, interpreters, web services, distributed caches, and analytics pipelines. Modern runtimes improve resilience through treeified buckets, randomized hashing, compact representations, and specialized maps. Distributed hash tables extend the idea across machines, but introduce network latency, partitioning, replication, and consistency concerns. Artificial-intelligence systems also use hash maps and sets for token dictionaries, feature lookup, memoization, and duplicate detection; the same key stability and resource-governance principles apply.

Chapter Summary

Hashing maps keys to table locations to support fast expected lookup, insertion, and deletion. Collisions are unavoidable and are managed primarily through separate chaining or open addressing. The load factor α = n/m describes occupancy and guides resizing; excessive occupancy increases search cost. Resizing costs O(n) at the event but can yield O(1) amortized insertion cost when growth is geometric. Correct equality–hash contracts and immutable keys are essential. Java HashMap and HashSet, and Python dict and set, support indexing, counting, caching, membership, and deduplication. Their performance is expected rather than absolute, and design must also consider memory, ordering, security, concurrency, and data correctness.

Key Terms

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

Hash table: An array-based structure that uses hashes to locate entries.

Key: The identifier used to locate a map value or set element.

Value: Data associated with a map key.

Collision: Assignment of multiple keys to the same table slot.

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

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

Open addressing: Collision resolution by probing alternative table slots.

Linear probing: Open addressing with a regular, usually one-step, probe sequence.

Quadratic probing: Probing with squared or otherwise quadratic offsets.

Double hashing: Probing whose step is determined by a second hash function.

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

Rehashing: Recomputing positions after a table is resized.

Amortized complexity: Average cost per operation over a sequence of operations.

Map: A collection of key–value associations.

Set: A collection of unique elements used primarily for membership.

Hashable: Suitable for hashing and equality-based collection membership.

Immutable key: A key whose equality-relevant state does not change while stored.

Collision attack: An attempt to degrade performance by generating many colliding keys.

Review Questions

Short Answer Questions

1. What is a collision, and why can collisions not generally be eliminated?
2. Define load factor and explain why it matters.
3. State the equality–hashing contract for Java keys.
4. Why should keys usually be immutable?
5. Give one difference between a map and a set.

Long Answer Questions

1. Compare separate chaining and open addressing, including deletion, memory locality, and load-factor behavior.
2. Explain how geometric resizing produces expected amortized O(1) insertion time.
3. Describe how Java HashMap and Python dict can support frequency counting and deduplication.
4. Explain why iteration order should not automatically be treated as sorted order or a portable design guarantee.
5. Discuss security, memory, and concurrency limitations of hash-based collections.

Analytical / Application Questions

1. Design indexes for a library catalogue that must support lookup by ISBN, detection of duplicate ISBNs, and retrieval of all books in a category. Identify suitable maps and sets.
2. A table has 600 entries and 1,000 slots. Calculate its load factor and explain whether a policy with maximum load factor 0.75 would trigger resizing before the next insertion.
3. A program uses a mutable object as a dictionary key and then changes a field used by equality. Explain the likely lookup failure and propose two safer designs.

Multiple Choice Questions with Answers

Question 1

Which condition is required for a correct hash-based key implementation?

A. Unequal objects must always have different hash codes.

B. Equal objects must have equal hash codes.

C. Every object must use the same hash code.

D. Hash codes must preserve insertion order.

Correct Answer: B. Equal objects must have equal hash codes.

Question 2

A table contains 600 entries and 1,000 slots. What is its load factor?

A. 0.06

B. 0.60

C. 1.67

D. 600

Correct Answer: B. 0.60

Question 3

Which structure is most directly suited to testing whether an item has already been seen?

A. Set

B. Stack

C. Priority queue

D. Linked list only

Correct Answer: A. Set

Question 4

What is the main purpose of rehashing after a table grows?

A. To sort keys alphabetically

B. To recompute positions using the new capacity

C. To remove all duplicate values

D. To convert a map into a set

Correct Answer: B. To recompute positions using the new capacity

Question 5

Which open-addressing method commonly suffers from primary clustering?

A. Linear probing

B. Separate chaining

C. Tree traversal

D. Binary search

Correct Answer: A. Linear probing

Question 6

What is the expected complexity of a hash-table lookup under good hashing and controlled load factor?

A. O(1)

B. O(log n) always

C. O(n log n)

D. O(n²)

Correct Answer: A. O(1)

Question 7

Which Python object is generally not hashable because it is mutable?

A. An integer

B. A string

C. A list

D. A tuple of integers

Correct Answer: C. A list

Question 8

Which Java collection stores unique elements and is designed primarily for membership testing?

A. HashSet

B. HashMap

C. ArrayDeque

D. PriorityQueue

Correct Answer: A. HashSet

Question 9

Why can changing a key after insertion cause a lookup to fail?

A. The table automatically sorts the key.

B. The key may now hash to a different location than the one used during insertion.

C. The value is always deleted when a key changes.

D. Hashing works only for numeric keys.

Correct Answer: B. The key may now hash to a different location than the one used during insertion.

Question 10

What does amortized O(1) insertion mean for a dynamically resizing hash table?

A. Every insertion takes exactly constant time.

B. The total cost averaged over a long sequence is constant per insertion.

C. Insertion always takes logarithmic time.

D. Resizing never costs O(n).

Correct Answer: B. The total cost averaged over a long sequence is constant per insertion.