8. Hashing and Associative Structures

Introduction and Context

Many computational tasks require a program to associate a key with a value and later retrieve that value efficiently. A compiler associates an identifier with its attributes, a database associates a customer number with a record, and a cache associates a resource name with recently computed data. Searching such associations sequentially in a list takes linear time in the number of stored items. Hashing provides an alternative: it transforms a key into an array position so that insertion, search, and deletion can usually be performed in expected constant time.

Hashing is therefore a central technique for implementing dictionaries, symbol tables, sets, indexes, caches, routing tables, and frequency counters. Its apparent simplicity conceals important design issues. Different keys may produce the same table position, a phenomenon called collision. The implementation must resolve collisions, control the load factor, resize the table when necessary, and remain robust when inputs are unfavorable or deliberately adversarial.

This chapter develops the principles and C implementations of hash tables using separate chaining and open addressing. It also examines expected and worst-case complexity, hash-function design, deletion, resizing, security considerations, and the relationship between hashing and other associative structures such as balanced search trees.

Learning Objectives

After completing this chapter, a student should be able to:

• explain the dictionary abstraction and the role of hashing;
• design and evaluate hash functions for common key types;
• implement collision resolution by separate chaining and open addressing in C;
• distinguish load factor, expected complexity, and worst-case complexity;
• perform insertion, search, deletion, and resizing safely;
• compare chaining, linear probing, quadratic probing, and double hashing;
• identify adversarial inputs, implementation risks, and security implications;
• select an appropriate associative structure for a practical application.

The Dictionary Abstraction

A dictionary stores records of the form `(key, value)` and supports operations such as `insert`, `search`, `update`, and `delete`. A set is a related structure in which only keys are stored. Keys must normally be unique; inserting an existing key may replace its value or be rejected, depending on the application.

An array provides direct access when keys are small, dense integers. If the key itself is used as an index, lookup is constant time, but the array may waste considerable memory when keys are large or sparse. A binary search tree supports ordered traversal and worst-case logarithmic operations when balanced. A hash table sacrifices ordering in exchange for very fast expected lookup.

The central idea is a hash function `h(k)` that maps a key `k` to an integer. For a table of capacity `m`, the table index is commonly obtained as

`index = h(k) mod m`.

A hash function is not required to be collision-free. In fact, when the key universe is larger than the table, collisions are mathematically unavoidable. The purpose of the function is to distribute keys as uniformly as possible over the available positions.

Hash Functions: Distribution Before Speed

A good hash function should be deterministic, efficient, and capable of distributing expected keys evenly. Uniform distribution reduces collisions and keeps the average operation close to constant time. A function that is fast but maps many common keys to the same position is poor in practice.

For non-negative integer keys, a basic function is:

`h(k) = k mod m`.

This can be effective when `m` is selected carefully, but it performs poorly when keys have regular patterns and `m` shares factors with those patterns. For example, if all keys are multiples of 10 and the capacity is 10, every key maps to zero. Prime capacities were traditionally used to reduce some such regularities, although modern power-of-two tables can also work well when the hash mixer thoroughly incorporates low-order bits.

For strings, a polynomial accumulation method is common:

`hash(s) = (((s[0] p + s[1]) p + s[2]) ... ) mod m`,

where `p` is a small base, such as 31 or 37. In C, arithmetic should use an unsigned type when overflow is intentional, because unsigned overflow is defined modulo a power of two. The final reduction must still produce a valid table index.

A hash function should also avoid undefined behavior. In particular, converting a signed negative hash directly with the `%` operator can produce a negative remainder in C. A safe normalization is:

`index = (hash % m + m) % m`.

Alternatively, an unsigned hash value may be used throughout.

Cryptographic hash functions are designed for properties such as preimage resistance and collision resistance, not primarily for low-cost table indexing. A general-purpose hash table usually uses a non-cryptographic function, but a randomized or keyed hash may be appropriate when an attacker can submit keys designed to cause collisions.

Collision Resolution by Separate Chaining

Separate chaining stores a collection of entries at each table position. The table is an array of pointers, and each pointer identifies the head of a linked list or another secondary container. If two keys map to the same index, their entries occupy the same chain.

Suppose the table has `m` buckets and contains `n` entries. Its load factor is

`α = n / m`.

For chaining, `α` may exceed one because a bucket can contain several entries. Under a simple uniform hashing assumption, the expected chain length is `α`. An unsuccessful search examines approximately `α` entries on average, while a successful search examines roughly `1 + α/2` entries when insertion places new nodes at the front and keys are equally likely. Thus, expected time is `O(1 + α)`. If resizing keeps `α` bounded by a constant, operations are expected `O(1)`.

A C representation can be written as follows:

```c

typedef struct Entry {

char *key;

int value;

struct Entry *next;

} Entry;

typedef struct {

Entry **bucket;

size_t capacity;

size_t size;

} ChainTable;

```

Insertion computes the bucket, traverses its chain to determine whether the key already exists, and either updates the value or allocates a new node. Search traverses only the selected chain. Deletion requires maintaining a previous pointer or modifying the bucket head when the first node is removed.

```c

Entry chain_find(ChainTable t, const char *key) {

size_t i = hash_string(key) % t->capacity;

for (Entry *p = t->bucket[i]; p != NULL; p = p->next)

if (strcmp(p->key, key) == 0)

return p;

return NULL;

}

```

Chaining is conceptually straightforward and deletion is simple. It tolerates load factors greater than one and does not require special states for deleted entries. Its disadvantages include pointer overhead, separate memory allocations, poorer cache locality, and possible allocator fragmentation. A chain can also become a long list under a poor hash function or an adversarial key set.

The secondary structure need not be a linked list. For large systems, a bucket may contain a small dynamic array, a balanced tree, or a compact collision group. Such hybrid designs can improve locality and protect against long chains.

Open Addressing and Occupied Table Positions

Open addressing stores every entry directly in the table array. When the preferred position is occupied, the algorithm follows a probe sequence until it finds the key or an available position. A general probe function is

`P(k, i) = (h(k) + offset(k, i)) mod m`,

where `i` is the probe number.

Open addressing avoids per-entry pointers and often has excellent cache behavior. However, the table must contain unused positions, and performance deteriorates sharply as the load factor approaches one. In practice, a maximum load factor is selected, often substantially below 1.

Linear Probing

Linear probing uses

`P(k, i) = (h(k) + i) mod m`.

It is simple and cache-friendly. Its major weakness is primary clustering: consecutive occupied positions form clusters, and new keys are likely to extend them. Despite this, linear probing can perform very well at moderate load factors because it uses memory efficiently.

Quadratic Probing

Quadratic probing uses an offset such as

`P(k, i) = (h(k) + c1 i + c2 i²) mod m`.

It reduces primary clustering, although keys with the same initial hash may still follow identical probe sequences, producing secondary clustering. The constants and table capacity must be selected so that the sequence visits enough positions; otherwise an apparently empty slot may not be reached.

Double Hashing

Double hashing uses a second hash function:

`P(k, i) = (h1(k) + i h2(k)) mod m`.

It generally distributes probe sequences better than linear or quadratic probing. The second step must be nonzero and relatively compatible with the table capacity; otherwise the sequence may visit only a subset of positions. If `m` is prime, choosing a step in the range `1` through `m - 1` is a common design.

Searching, Inserting, and Deleting in Open Addressing

A search begins at the key's initial position and follows the same probe sequence used during insertion. It may stop when the key is found or when it reaches a slot that has never been occupied. A never-used slot proves that the key is absent because insertion would have stopped there earlier.

Deletion is more subtle. If a slot is simply marked empty, a later search may stop prematurely and fail to find keys placed farther along the probe sequence. The standard solution is a tombstone: a slot marked as previously occupied but currently deleted. Search continues past a tombstone, while insertion may reuse it.

Tombstones preserve correctness but gradually lengthen probe sequences. Periodic rebuilding or resizing removes them. An alternative is backward-shift deletion, which is safe for some probing schemes when entries are shifted toward their ideal positions, but it requires careful reasoning and is not universally applicable.

A simplified linear-probing table may use a state field:

```c

typedef enum { EMPTY, OCCUPIED, DELETED } State;

typedef struct {

char *key;

int value;

State state;

} Slot;

```

Insertion should first remember the first tombstone encountered, continue searching for an existing key, and use the tombstone only if the key is not already present. Otherwise, inserting a duplicate key can create multiple records for one logical key.

Load Factor, Resizing, and Amortized Cost

The load factor is a central operational measure. In chaining, it expresses average entries per bucket. In open addressing, it is the fraction of occupied slots; tombstones may make the effective search behavior worse than the numerical value suggests.

When a threshold is reached, the table is resized, commonly by allocating a larger array and rehashing every live entry. Entries cannot generally be copied to the same indices because the modulus, and sometimes the probe sequence, has changed. Rehashing costs `O(n)` for `n` entries, but if capacity grows geometrically—for example, by doubling—then the total cost of a sequence of insertions is `O(n)` across all resizings. Consequently, insertion has amortized expected `O(1)` time, even though an individual insertion that triggers resizing costs linear time.

A robust resizing policy should consider both growth and shrinkage, impose minimum capacity, and avoid repeated grow-shrink oscillation. For open addressing, a table may be rebuilt even without growth when the number of tombstones becomes large. During resizing, allocation failure must be handled without losing the original table. A safe implementation constructs the new table first, transfers entries, and releases the old table only after success.

Capacity selection is an engineering choice. Prime capacities can simplify some modular schemes, while power-of-two capacities make index computation inexpensive and work well with high-quality bit-mixing functions. The function and capacity policy must be considered together rather than selected independently.

Complexity: Expected Is Not Guaranteed

Under a uniform hashing assumption and a controlled load factor, dictionary operations have expected `O(1)` time. This is an average-case statement based on a distribution model, not a guarantee for every input. The worst case is `O(n)` for both chaining and open addressing: all keys may collide, producing a long chain or a probe sequence that examines nearly the whole table.

This distinction matters in real systems. A workload may be non-random, keys may have visible structure, and an attacker may intentionally select colliding inputs. A complexity claim should therefore specify its assumptions:

• expected constant time assumes a sufficiently uniform hash distribution and controlled load factor;
• amortized constant insertion assumes geometric resizing;
• worst-case lookup remains linear for an ordinary hash table;
• memory usage includes buckets, entries, pointers, metadata, and unused capacity.

Hash tables do not provide sorted order. Iteration order may change after insertion or resizing and should not be treated as a stable interface unless explicitly guaranteed.

Associative Structures in C: Design and Ownership

A production-quality C dictionary requires more than a hash formula. It must define ownership of keys and values, behavior on duplicate keys, failure handling, and destruction. If the table copies a string key, it must allocate and later free that copy. If it stores a caller-owned pointer, the caller must keep the object alive and must not modify it in a way that changes its hash or equality behavior.

The equality operation must agree with hashing: whenever `key1` equals `key2`, both must produce the same hash value. Hashing only part of a string while comparing the complete string violates this requirement and can cause failed searches or duplicate logical keys.

Integer overflow in hash accumulation should be intentional and implemented with unsigned arithmetic. Table sizes and allocation calculations should be checked for overflow. NULL pointers, zero capacity, failed allocation, and malformed input should have defined behavior. A destructor should release every allocated key, value object if owned, entry, bucket array, and table structure.

For concurrent programs, an ordinary table is not automatically thread-safe. Possible approaches include external locks, per-bucket locks for chained tables, immutable snapshots, or specialized concurrent maps. Lock-free designs require advanced memory-reclamation techniques and should not be improvised from a sequential implementation.

Applications of Hashing

Hashing appears wherever rapid association is useful. A compiler's symbol table maps names to type and scope information. A web service may use a cache keyed by a normalized request. A graph algorithm can use a set of visited vertex identifiers. A text-processing program can count word frequencies by mapping each word to a counter. Database systems use hash indexes for equality predicates, although ordered indexes are preferable for range queries.

Hashing is also useful for deduplication, membership testing, memoization, session lookup, routing, and maintaining frequency maps in streaming analytics. Bloom filters extend the membership idea to highly compact probabilistic structures: they may report false positives but not false negatives under normal operation. A Bloom filter is not a replacement for a dictionary when the associated value must be retrieved.

Choosing hashing requires understanding the query pattern. Equality lookup favors hash tables; sorted output, predecessor queries, and range searches favor balanced trees or other ordered indexes. Memory constraints, predictability, concurrency, and security may also outweigh raw average lookup speed.

An Illustrative Case Study: A Compiler Symbol Table

Background

Consider a compiler front end processing a large source file. Every identifier must be associated with attributes such as type, scope level, storage class, and declaration location. During parsing and semantic analysis, the compiler repeatedly searches for identifiers and inserts newly declared names.

Situation and Problem

A simple list-based symbol table is easy to implement, but each lookup may scan many declarations. In a large procedure with thousands of names, repeated linear searches can become a significant cost. The compiler also needs predictable handling of duplicate declarations and scope removal.

Analysis

Identifier names are strings and are likely to contain common prefixes. A hash function that uses only the first character would produce severe clustering. The table should hash the complete normalized identifier, compare complete strings for equality, and maintain a load factor low enough for rapid lookup. Since compilation is usually a trusted workload, a non-cryptographic string hash may be adequate, but a randomized seed can reduce sensitivity to pathological input.

Scope management affects the data structure. One approach is to maintain a separate table for each scope and search from the innermost scope outward. Another is one table containing a stack or linked list of declarations for each identifier, with the most recent declaration visible. The correct choice depends on the compiler's operations and memory policy.

Approach and Outcome

An illustrative implementation uses chained buckets. Each entry contains the identifier string, semantic attributes, and a link to the next entry. On entering a scope, a scope marker is pushed. On leaving it, declarations made after that marker are removed or hidden. The table resizes when the average chain length becomes too large. Duplicate declarations are detected by searching the current scope before insertion, while lookup proceeds outward through visible scopes.

The resulting structure provides expected constant-time name lookup per scope and supports explicit ownership of identifier strings. It also preserves a clear policy for shadowing: an inner declaration is found before an outer declaration with the same spelling.

Learning Points

The case demonstrates that a hash table is part of a larger design. Hash quality, equality semantics, resizing, memory ownership, and application-specific rules such as scope visibility must be designed together. It also shows why a technically fast table may still be unsuitable if it cannot express the required semantics.

Risks, Failure Modes, and Adversarial Inputs

A poor hash function is the most obvious failure. Other mistakes include using a negative index, forgetting to rehash after resizing, stopping at a tombstone, allowing the table to become full, failing to distinguish an empty string from an empty slot, and freeing a key while retaining its pointer.

Adversarial collision attacks are especially important in network-facing services. If an attacker can predict the hash function and submit many keys with the same index, request processing can degrade from expected constant time to linear time per operation. Mitigations include keyed or randomized hashing, input limits, collision-resistant fallback structures, rate limiting, and monitoring unusually long chains or probe lengths. Randomization does not remove all risks, but it makes precomputed collision sets less reliable.

Hash tables can also leak information through timing or memory-access behavior. In security-sensitive contexts, equality comparisons, hash seeds, and error reporting should be considered carefully. Sensitive data should not be placed in a table without a suitable lifecycle and access-control policy.

Current Developments and Professional Practice

Modern high-performance hash tables increasingly emphasize cache locality, compact metadata, SIMD-assisted probing, and control of clustering. Some use groups of metadata bytes to test many candidate slots at once. Other systems combine hashing with tree-based collision buckets to obtain better worst-case behavior. These techniques do not change the basic principles of hashing, but they demonstrate that memory hierarchy is as important as asymptotic complexity.

Distributed systems introduce another layer: consistent hashing maps keys to nodes while minimizing remapping when nodes join or leave. This is distinct from ordinary table indexing, although both depend on balanced key distribution. Distributed caches may also use virtual nodes, replication, and failure detection.

For professional software, benchmarks should use realistic key distributions, successful and unsuccessful searches, resizing events, deletion patterns, and adversarial cases. Measuring only random successful lookups can conceal poor behavior in the actual workload.

Best-Practice Checklist

A sound hash-table implementation should:

• define key equality and ownership explicitly;
• use a hash function consistent with equality and appropriate for the key distribution;
• normalize indices safely and avoid undefined arithmetic;
• monitor load factor and resize geometrically;
• handle duplicate keys according to a documented policy;
• implement deletion correctly, including tombstone management where needed;
• check allocation and size arithmetic for failure;
• test empty tables, duplicate insertion, absent deletion, full or nearly full tables, long keys, and resize boundaries;
• consider randomized hashing and operational limits for untrusted input;
• choose an ordered structure instead when range queries or stable ordering are essential.

Chapter Summary

Hashing implements the dictionary abstraction by transforming keys into table positions. Because multiple keys may map to one position, collision resolution is essential. Separate chaining stores colliding entries in buckets and offers simple deletion and flexible load factors, while open addressing stores entries in the table itself and provides strong locality at the cost of careful probing and deletion rules. Linear probing is simple but clusters; quadratic probing reduces primary clustering; double hashing usually provides more independent probe sequences.

Load factor controls performance. With a suitable hash function, bounded load, and geometric resizing, dictionary operations have expected amortized constant time, although their worst-case time remains linear. Correct C implementations must address ownership, equality, overflow, allocation failure, resizing, tombstones, and thread safety. Hashing is valuable for symbol tables, caches, indexes, sets, frequency maps, and many other applications, but balanced trees or probabilistic structures may be preferable when ordering, predictable worst-case behavior, or compact membership testing is required. In adversarial environments, randomized hashing and defensive operational policies are part of responsible design.

Key Terms

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

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

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

Bucket: A table position that stores one or more entries, commonly in chaining.

Separate chaining: Collision resolution by storing colliding entries in a secondary structure at each bucket.

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

Probe sequence: The ordered sequence of positions examined by an open-addressing operation.

Linear probing: Open addressing that examines consecutive table positions.

Quadratic probing: Open addressing whose offsets grow according to a quadratic expression.

Double hashing: Open addressing that uses a second hash function to determine probe steps.

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

Tombstone: A marker showing that an open-addressing slot was occupied but has been deleted.

Rehashing: Reinserting entries into a new table, usually after resizing.

Primary clustering: Formation of long contiguous groups under linear probing.

Secondary clustering: Similar probe sequences caused by keys sharing an initial hash.

Dictionary: An abstract data type supporting association between keys and values.

Expected complexity: Performance averaged under stated assumptions about inputs or hashing.

Amortized complexity: Average cost per operation over a sequence that may include occasional expensive operations.

Adversarial input: Input deliberately selected to cause poor performance or exploit implementation weaknesses.

Bloom filter: A compact probabilistic membership structure that permits false positives but normally not false negatives.

Review Questions

Short Answer Questions

1. What is the relationship between a hash function and a table index?

2. Define load factor for separate chaining and open addressing.

3. Why can an open-addressing table not treat a deleted slot as never used?

4. State one advantage and one disadvantage of separate chaining.

5. Why must equal keys always produce equal hash values?

Long Answer Questions

1. Explain separate chaining in detail, including insertion, search, deletion, load factor, and expected complexity.

2. Compare linear probing, quadratic probing, and double hashing with respect to clustering and implementation requirements.

3. Describe a complete resizing policy for a C hash table, including growth, rehashing, failure handling, and shrinkage.

4. Explain why ordinary hash-table operations are expected `O(1)` but worst-case `O(n)`.

5. Discuss the memory-ownership, equality, overflow, and allocation issues that must be addressed in a C dictionary implementation.

Analytical / Application Questions

1. A table of capacity 11 uses linear probing. Several identifiers produce consecutive occupied positions. Analyze the performance problem and recommend a collision strategy or redesign.

2. Design a hash-based symbol table for nested compiler scopes. Specify how insertion, lookup, shadowing, scope exit, resizing, and key ownership should operate.

3. A public service receives user-controlled keys and experiences long lookup times despite a moderate average load factor. Identify plausible causes and propose technical and operational defenses.

22. Multiple Choice Questions with Answers

Question 1

Which condition is required for a hash function and equality operation to work correctly in a dictionary?

A. Unequal keys must always have different hash values

B. Equal keys must produce the same hash value

C. Every key must map to an unused table position

D. The table capacity must always be a power of two

Correct Answer: B. Equal keys must produce the same hash value

Question 2

A chained hash table contains 240 entries in 60 buckets. What is its load factor?

A. 0.25

B. 2

C. 4

D. 300

Correct Answer: C. 4

Question 3

Why is a tombstone needed in open addressing?

A. It permanently prevents reuse of a deleted slot

B. It allows searches to continue past a previously occupied slot

C. It reduces the table capacity after deletion

D. It converts open addressing into chaining

Correct Answer: B. It allows searches to continue past a previously occupied slot

Question 4

Which collision method is most directly associated with primary clustering?

A. Linear probing

B. Double hashing

C. Separate chaining with trees

D. Cryptographic hashing

Correct Answer: A. Linear probing

Question 5

Why must entries normally be rehashed after a table is resized?

A. Their values become invalid after allocation

B. The equality operation changes automatically

C. The table capacity affects their computed indices

D. Hash functions cannot process more than one table size

Correct Answer: C. The table capacity affects their computed indices

Question 6

Under uniform hashing and a controlled load factor, what is the expected time for a dictionary lookup?

A. O(log n)

B. O(n log n)

C. O(1)

D. O(n²)

Correct Answer: C. O(1)

Question 7

Which situation is a particularly strong reason to prefer a balanced search tree over a hash table?

A. The application requires equality lookup only

B. The application requires range queries and sorted traversal

C. The keys are short strings

D. The table can be resized geometrically

Correct Answer: B. The application requires range queries and sorted traversal

Question 8

An implementation marks a deleted open-addressing slot as EMPTY. What failure can result?

A. The hash function becomes randomized

B. A search may stop early and miss a key farther along the probe sequence

C. All existing values are automatically duplicated

D. The load factor becomes negative

Correct Answer: B. A search may stop early and miss a key farther along the probe sequence

Question 9

Which measure is most relevant when defending a public hash table against collision attacks?

A. Using a predictable hash function based only on the first character

B. Disabling resizing permanently

C. Using randomized or keyed hashing and monitoring pathological behavior

D. Allowing unlimited chain lengths without monitoring

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

Question 10

What is the main reason geometric resizing can give amortized constant-time insertion?

A. Every insertion immediately takes constant time

B. The total cost of occasional linear rehashes is spread across many insertions

C. Resizing eliminates the need for a hash function

D. Deletion becomes impossible after the first resize

Correct Answer: B. The total cost of occasional linear rehashes is spread across many insertions