Hashing, Maps, and Sets

Introduction

Programs frequently need to answer questions such as: “What is the price associated with this product code?”, “Has this username already been registered?”, or “How many times does each word occur?” Searching an unsorted list may require examining many elements. Hash-based data structures address these tasks by transforming a key into an array position, allowing fast average-case insertion, lookup, and deletion.

This chapter introduces hash functions, collisions, load factors, equality, maps, and sets. It then applies these ideas to indexing, caching, frequency counting, and duplicate detection in Java and Python.

Learning Objectives

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

• Explain the purpose and operation of a hash function.
• Distinguish keys, values, maps, and sets.
• Explain collisions and common collision-resolution methods.
• Calculate and interpret a load factor.
• Explain why hashing and equality must be consistent.
• Use Java maps and sets and Python dictionaries and sets.
• Select appropriate hash-based structures for practical applications.
• Identify security, correctness, and performance limitations.

1. The Hashing Model

A hash table stores records in an array. A record normally consists of a key and, in a map, an associated value. A hash function converts the key into an integer called a hash code. That code is then transformed into a valid table index.

For a table with capacity m, a simple index rule is:

Here, m is the number of table positions. In real implementations, the language runtime may apply additional mixing or masking before calculating the index. The modulo operation must produce a non-negative index.

A good hash function should have the following properties:

1. Determinism: the same key produces the same hash code during its useful lifetime.
2. Efficiency: computing the hash should be inexpensive.
3. Uniform distribution: keys should be spread across the table rather than concentrated in a few positions.
4. Consistency with equality: objects considered equal must have equal hash codes.

A hash function is not required to produce unique results. The number of possible keys is usually much larger than the number of table positions, so collisions are unavoidable.

Example: Index calculation

Suppose a table has 10 positions and a key produces hash code 437. The index is:

The record is initially directed to position 7. This calculation does not mean that the key itself is 7; it means that 7 is the table position selected by the hash process.

2. Maps and Sets

A map stores associations between unique keys and values. A key can occur only once, although multiple keys may have equal values.

Examples include:

• student ID → student record
• product code → price
• username → account object
• word → frequency

A set stores unique elements without associated values. It is useful when membership is the main concern.

Examples include:

• registered usernames
• permitted file extensions
• unique tags
• visited page identifiers

Hash-based maps and sets generally provide expected O(1) insertion, lookup, and deletion. This is an average-case statement, not a guarantee for every operation. Poor hash distribution, excessive collisions, or adversarial input can make operations slower.

3. Collisions and Their Resolution

A collision occurs when two different keys are assigned to the same table position. For example, with capacity 10, hash codes 27 and 47 both produce index 7.

Collisions cannot be eliminated completely in a finite table. They must be managed.

3.1 Separate chaining

In separate chaining, each table position refers to a collection of entries, commonly a linked list or a tree. All entries whose indices are equal are stored in the same bucket.

Advantages include:

• simple insertion and deletion;
• easy handling of a table that becomes moderately full;
• no requirement to find an empty position immediately.

A disadvantage is extra memory for bucket structures and potentially slower access if a bucket becomes long.

3.2 Open addressing

In open addressing, all entries remain inside the table array. If the preferred position is occupied, the implementation examines other positions according to a probing rule.

Common strategies are:

• Linear probing: examine consecutive positions.
• Quadratic probing: use increasing quadratic offsets.
• Double hashing: use a second hash function to determine the step size.

Open addressing can be memory-efficient and cache-friendly. However, deletion is more complicated, and performance falls sharply when the table becomes too full.

3.3 Collision example

Assume a table with capacity 7 and linear probing. Three keys map to indices 3, 3, and 4.

• The first key occupies position 3.
• The second key finds position 3 occupied and moves to position 4.
• The third key finds position 4 occupied and moves to position 5.

A lookup must follow the same probing sequence. Therefore, an entry cannot simply be removed by making its position permanently empty; doing so might incorrectly terminate later searches. Implementations commonly use a special deleted marker or reorganize the cluster.

4. Load Factor and Capacity

The load factor measures how full a hash table is. It is defined as:

where α is the load factor, n is the number of stored entries, and m is the table capacity. Both n and m are counts, so the load factor has no physical unit.

For example, if a table contains 75 entries and has capacity 100:

A high load factor usually increases collisions. Implementations therefore define a threshold. When the number of entries exceeds the threshold, the table is resized, often by allocating a larger table and rehashing every entry into it.

Resizing costs O(n) for that operation because all entries may need to be moved. Nevertheless, if capacity grows geometrically, such as by approximately doubling, the average cost over a long sequence of insertions remains expected O(1) per insertion. This is called amortized analysis.

The exact appropriate load factor depends on the collision strategy. Chaining can tolerate higher occupancy than open addressing, while open addressing commonly requires more empty space for efficient probing.

5. Equality and Hash Codes

Hashing depends on two related but distinct ideas:

• Equality determines whether two keys represent the same logical key.
• Hashing selects a likely storage location.

The essential rule is:

If two objects are equal, they must have the same hash code.

The reverse is not required. Two unequal objects may have the same hash code because that is a collision.

A correct equality relation should normally be reflexive, symmetric, transitive, and consistent. It should also return false when compared with an incompatible type.

Mutable-key danger

A key should not change in a way that affects equality or hashing while it is stored in a map or set. Suppose a customer object is inserted using customer ID 204, and the ID is later changed to 305. A lookup may calculate a different bucket and fail to find the object, even though the object remains physically present.

Good practice is to use immutable keys such as strings, numbers, tuples of immutable values, or carefully designed immutable domain objects.

Java equality

In Java, hash-based collections rely on equals() and hashCode(). If a class overrides equals(), it should also override hashCode() so that equal objects have equal hash codes.

import java.util.HashMap;
import java.util.Map;

Map<String, Integer> scores = new HashMap<>();
scores.put("Asha", 86);
scores.put("Ben", 91);

int score = scores.get("Asha");

For custom classes, equality should be based on stable logical fields. Modern Java development often uses records when an immutable value-like object is appropriate.

Python equality

Python dictionaries and sets use __eq__() and __hash__(). Immutable built-in values such as strings, integers, and tuples containing hashable values are common keys.

scores = {"Asha": 86, "Ben": 91}
score = scores["Asha"]

A mutable object should not be hashable if its equality-relevant state can change. Python commonly makes a class unhashable when it defines equality but does not provide a safe hash implementation.

6. Maps in Java and Python

Core operations

In Java, get() may return null for a missing key, so containsKey() may be needed when null values are permitted. Python’s d[key] raises KeyError for a missing key, whereas d.get(key) returns None or a supplied default.

Counting frequencies

Frequency counting is a central map application. The key is the item being counted, and the value is its current count.

Python:

words = ["data", "code", "data", "map"]
counts = {}

for word in words:
    counts[word] = counts.get(word, 0) + 1

The result is {'data': 2, 'code': 1, 'map': 1}. Java provides similar logic through getOrDefault():

Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
    counts.put(word, counts.getOrDefault(word, 0) + 1);
}

If there are n input items and the map contains k distinct keys, expected running time is approximately O(n) and additional storage is O(k), assuming effective hashing.

7. Sets and Duplicate Detection

A set is particularly useful for detecting repeated values. Process each item as follows:

1. If the item is already in the set, it is a duplicate.
2. Otherwise, add it to the set.

Python:

seen = set()
duplicates = set()

for identifier in identifiers:
    if identifier in seen:
        duplicates.add(identifier)
    else:
        seen.add(identifier)

Java:

Set<String> seen = new HashSet<>();
Set<String> duplicates = new HashSet<>();

for (String id : identifiers) {
    if (!seen.add(id)) {
        duplicates.add(id);
    }
}

The Java expression seen.add(id) returns false when the element was already present. This makes the operation concise while preserving the set’s uniqueness guarantee.

A set does not normally preserve insertion order. If order is required, use an order-preserving alternative, such as Python’s ordered dictionary behavior for dictionaries or Java’s LinkedHashSet. If sorted order is required, use a tree-based structure rather than an ordinary hash set.

8. Indexing and Caching

Indexing

An index maps a frequently searched attribute to an object or collection of objects. For example, a library system can map an ISBN to a book record. Instead of scanning every book, the program performs a direct expected-time lookup.

If an attribute is not unique, the value should be a collection:

by_department = {}
for employee in employees:
    by_department.setdefault(employee.department, []).append(employee)

The index must be updated when records are inserted, modified, or deleted. A stale index can produce incorrect results.

Caching

A cache stores previously computed results in a map. The key represents the request and the value represents the result.

cache = {}

def square(n):
    if n not in cache:
        cache[n] = n * n
    return cache[n]

Caching can reduce computation and latency, but it introduces concerns about memory use, expiration, invalidation, and stale data. A cache policy may limit its size or remove entries using least-recently-used behavior. A cache must also consider whether two requests are genuinely equivalent before using the same key.

9. Illustrative Case: Duplicate Student Registration

Background

A training provider receives a daily file of student registrations. Each record contains a registration ID, student email address, course code, and date. Duplicate registration IDs may result from repeated submissions or file-merging errors.

Problem

The provider needs to identify duplicate IDs efficiently while preserving the original records for later review. A nested comparison of every record with every other record would require approximately O(n²) comparisons for n records.

Analysis

A set can record IDs already encountered. A map can also store the first record associated with each ID, allowing the system to report both the original and duplicate records.

Approach

first_record = {}
duplicates = []

for record in registrations:
    key = record["registration_id"]
    if key in first_record:
        duplicates.append({
            "original": first_record[key],
            "duplicate": record
        })
    else:
        first_record[key] = record

Expected processing time is O(n) under effective hashing, and storage is O(u), where u is the number of unique registration IDs retained.

Outcome

The provider can process large files in one pass and produce an audit list. The map also makes it possible to compare the duplicate with the first occurrence. In production, the system should normalize identifiers, for example by applying a documented case policy to email addresses, and should validate missing or malformed IDs.

Learning points

• A set is sufficient when only membership matters.
• A map is preferable when an associated record must be retrieved.
• Equality rules must be defined before duplicate detection.
• Input normalization can affect whether two records are considered equal.
• Audit requirements may require retaining the source record and timestamp.

10. Limitations, Security, and Best Practices

Hash-based structures are powerful but not universally appropriate.

Limitations

• They do not usually provide sorted traversal.
• Worst-case performance can degrade because of collisions.
• They consume memory for buckets, entries, and resizing.
• Mutable keys can make entries inaccessible.
• Iteration order may be unspecified or implementation-dependent.
• Hash tables are not automatically thread-safe.

Use a list when indexed order or small sequential data is more important. Use a tree-based map or set when sorted order and predictable logarithmic performance are required.

Security considerations

Attackers may deliberately submit keys that cause many collisions, potentially producing denial-of-service conditions. Modern runtimes may randomize string hashing, treeify long collision chains, or use other defenses. Developers should still validate input, avoid exposing internal hash assumptions, and use framework-supported collections.

Hashing passwords is a different problem from ordinary table hashing. Password storage requires a slow, salted password-hashing scheme such as Argon2, scrypt, or bcrypt—not a general-purpose map hash function. Cryptographic hashes and table hashes have different design goals.

Best practices

1. Choose immutable, stable keys.
2. Define equality according to domain meaning.
3. Ensure equal keys produce equal hashes.
4. Pre-size collections when the approximate size is known.
5. Use a set for membership and a map for associations.
6. Treat missing values explicitly.
7. Do not rely on unspecified iteration order.
8. Consider concurrency requirements.
9. Measure performance with realistic data.
10. Protect sensitive data and distinguish table hashing from cryptographic hashing.

Contemporary Developments

Modern systems increasingly use distributed key-value stores and in-memory caches. These systems extend map concepts across multiple machines. A technique called consistent hashing helps distribute keys among servers while reducing the number of keys that must move when a server is added or removed. This is useful in distributed caches and scalable services, although it introduces network latency, replication, failure handling, and consistency concerns.

Programming languages also provide specialized structures: concurrent maps, immutable maps, ordered dictionaries, weak-key maps, and probabilistic membership structures such as Bloom filters. A Bloom filter can quickly indicate that an item is definitely absent or possibly present, but it can produce false positives and cannot normally retrieve the stored item.

Chapter Summary

Hashing converts keys into locations that support fast average-case access. A hash table must manage collisions, commonly through separate chaining or open addressing. The load factor, α = n/m, indicates how full a table is and influences collision frequency and resizing decisions.

Maps store key–value associations, while sets store unique elements. Both depend on consistent equality and hashing; equal keys must have equal hash codes, and keys should remain immutable while stored. Maps are effective for indexing, frequency counting, and caching. Sets are effective for membership testing and duplicate detection.

Hash-based structures provide expected O(1) operations under suitable assumptions, but they do not guarantee constant-time performance in every case. Developers must consider memory, ordering, concurrency, security, stale caches, and the distinction between ordinary table hashing and cryptographic password hashing.

Key Terms

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

Hash code: An integer representation produced from a key.

Hash table: An array-based structure that stores entries using hashed positions.

Collision: The assignment of different keys to the same table position.

Separate chaining: Collision resolution using a collection at each table position.

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

Linear probing: Open addressing that checks consecutive positions.

Load factor: The ratio of stored entries to table capacity.

Map: A collection of key–value associations.

Set: A collection of unique elements.

Key: The identifying object used to locate a map value.

Value: Data associated with a map key.

Equality: The rule determining whether two objects represent the same logical value.

Rehashing: Recomputing positions after a table is resized.

Immutable object: An object whose relevant state cannot change after creation.

Index: A structure that accelerates retrieval by an attribute.

Cache: Stored results used to avoid repeated computation or retrieval.

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

Consistent hashing: A distribution technique designed to minimize key movement in changing distributed systems.

Bloom filter: A probabilistic structure that may report false positives but not false negatives under normal operation.

Review Questions

Short Answer Questions

1. What is the purpose of a hash function in a hash table?
2. Define a collision and name two collision-resolution methods.
3. What does the load factor measure?
4. Why must equal objects have equal hash codes?
5. State one difference between a map and a set.

Long Answer Questions

1. Explain separate chaining and open addressing, including one advantage and one limitation of each.
2. Describe how resizing affects the performance of a hash table.
3. Explain why mutable keys are dangerous in maps and sets.
4. Compare Java HashMap and Python dict in terms of insertion, retrieval, and missing keys.
5. Discuss the role of maps in indexing and caching.

Analytical / Application Questions

1. Design an algorithm using a set to detect duplicate usernames in a registration file. State its expected time and space complexity.
2. A system must retrieve employees by department, where many employees may belong to one department. Should the map value be one employee or a collection? Justify your answer.
3. A password system currently stores passwords using a general-purpose hash-table hash function. Explain why this is unsafe and recommend a more appropriate approach.

Multiple Choice Questions with Answers

Question 1

What is the main purpose of a hash function in a hash table?

A. To sort all keys alphabetically

B. To map a key to a likely table position

C. To guarantee that every key is unique

D. To compress every value to one byte

Correct Answer: B. To map a key to a likely table position

Question 2

If a hash table stores 75 entries in a capacity of 100, what is its load factor?

A. 0.25

B. 0.50

C. 0.75

D. 1.75

Correct Answer: C. 0.75

Question 3

Which statement about collisions is correct?

A. They can always be completely eliminated

B. They occur only when keys are equal

C. They occur when different keys map to the same position

D. They occur only in open addressing

Correct Answer: C. They occur when different keys map to the same position

Question 4

Which structure is most appropriate for testing whether a username has already appeared?

A. Set

B. Stack

C. Queue

D. Sorted list only

Correct Answer: A. Set

Question 5

What must be true when two objects are equal and used as hash-based keys?

A. They must have different hash codes

B. They must have the same hash code

C. They must occupy adjacent positions

D. They must have different values

Correct Answer: B. They must have the same hash code

Question 6

Which operation is typically expected to take constant time in a well-designed hash map?

A. Lookup by key

B. Sorting all values

C. Printing keys in sorted order

D. Finding the minimum key without ordering

Correct Answer: A. Lookup by key

Question 7

What is a common consequence of an excessively high load factor?

A. Fewer collisions and faster access

B. More collisions and slower access

C. Automatic data encryption

D. Guaranteed sorted iteration

Correct Answer: B. More collisions and slower access

Question 8

Which Python expression safely retrieves a dictionary value with a default for a missing key?

A. d.get(key, default)

B. d.sort(key, default)

C. d.hash(key, default)

D. d.index(key, default)

Correct Answer: A. d.get(key, default)

Question 9

Why is a set useful for duplicate detection?

A. It stores every item more than once

B. It automatically preserves sorted order

C. It records membership while rejecting repeated elements

D. It converts all values into keys and values

Correct Answer: C. It records membership while rejecting repeated elements

Question 10

Which technique is designed to reduce key movement when servers are added to a distributed cache?

A. Linear search

B. Consistent hashing

C. Bubble sorting

D. Depth-first traversal

Correct Answer: B. Consistent hashing