Class Note: Hashing and Hash Tables

Topic: Hashing and Hash Tables - Efficient Data Storage and Retrieval

Date: October 26, 2023 Instructor: Prof. [Your Name/Placeholder] Keywords: Hash
Function, Collision, Separate Chaining, Open Addressing, Load Factor, Rehashing, O(1)
Average Time Complexity

1. Introduction: The Need for Speed

In computer science, efficient data storage and retrieval are paramount. We often need to
store a collection of items and quickly perform operations like searching for an item, inserting
a new item, or deleting an existing item.

• Arrays: Provide O(1) access by index but O(N) for search/insert/delete by value (if not
sorted).
• Linked Lists: O(N) for all operations (search, insert, delete) by value.
• Binary Search Trees (BSTs): Offer O(log N) average time complexity for search, insert,
and delete, which is good, but in the worst case (unbalanced tree), it can degrade to
O(N).

Hash tables, also known as hash maps, dictionaries, or associative arrays, offer a powerful
alternative, aiming for O(1) average time complexity for these crucial operations. They
achieve this by directly computing the location of an element in memory, rather than
searching through a structure.

A Hash Table is a data structure that implements an associative array abstract data type,
mapping keys to values. It uses a hash function to compute an index into an array of
buckets or slots, from which the desired value can be found.

2. Key Concepts

2.1. The Hash Function

The core of a hash table is the hash function.

• Definition: A function that takes an input (the key) and returns an integer (the hash
value or hash code). This hash value is then typically mapped to an index within the
hash table's underlying array structure.
• Goal: To distribute keys uniformly across the array, minimizing the chances of different
keys mapping to the same index.
• Desirable Properties:

○ Deterministic: The same key must always produce the same hash value.
○ Fast to Compute: The function itself shouldn't take long to calculate.
○ Uniform Distribution: It should spread keys evenly across the available indices
to avoid clustering.
○ Low Collision Rate: While not entirely avoidable, a good hash function
minimizes collisions.
Simple Example Hash Functions:

1. Modulo Division: hash(key) = key % table_size

• Commonly used. Works well if table_size is a prime number, as it helps

distribute keys more evenly.

2. Folding Method: For long keys (e.g., large numbers or strings), divide the key into
parts, sum them, and then apply modulo.
3. Mid-Square Method: Square the key, then extract some middle digits as the hash
value.
4. String Hashing: For strings, a common technique involves treating the string as a
polynomial or using a rolling hash: hash(s) = (s[0] * P^(N-1) + s[1] *
P^(N-2) + ... + s[N-1] * P^0) % table_size where P is a prime number
(e.g., 31, 37) and N is the length of the string.

2.2. Collisions

Despite the best efforts of a hash function, it's virtually impossible to guarantee that different
keys will always map to different indices. This is due to the Pigeonhole Principle: if you
have more keys than available slots in your hash table, at least two keys must map to the
same slot. When two or more distinct keys map to the same index, it's called a collision.

Handling collisions efficiently is critical for a hash table's performance. Two primary
strategies exist:

2.3. Collision Resolution Strategies

A. Separate Chaining

• Concept: Instead of storing the actual key-value pair directly in the array slot, each slot
(or "bucket") stores a pointer to a data structure (typically a linked list) that holds all
the key-value pairs that hash to that same index.
• How it Works:

1. To insert a key-value pair: Hash the key to get an index. Add the pair to the
linked list at that index.
2. To search for a key: Hash the key to get an index. Traverse the linked list at that
index to find the matching key.
3. To delete a key: Hash the key to get an index. Traverse the linked list at that
index to find and remove the matching key.

• Pros: Simple to implement, never "fills up" (can always add to a list), deletion is
straightforward, less sensitive to load factor (can exceed 1.0).
• Cons: Requires extra memory for pointers in the linked lists, cache performance might
be poorer due to scattered memory access, overhead of linked list operations.

B. Open Addressing

• Concept: When a collision occurs, instead of forming a list, the algorithm "probes"
(searches) for another empty slot directly within the hash table array. All elements are
stored directly in the table.
• How it Works:
 1. To insert: Hash the key to get an index. If the slot is empty, insert. If occupied,
use a probing sequence to find the next available slot.
2. To search: Hash the key to get an initial index. If the key is found, return. If the
slot is empty, the key is not in the table. If occupied by a different key, follow the
probing sequence until the key is found or an empty slot is encountered.
3. To delete: This is tricky. Simply removing an element can break the search path
for other elements that might have probed past the deleted element. A common
solution is to mark the deleted slot with a special "tombstone" marker, indicating
it's available for insertion but search operations should continue probing past it.

• Types of Probing:

○ Linear Probing: If hash(key) is occupied, try (hash(key) + 1) %

table_size, then (hash(key) + 2) % table_size, and so on.

■ Issue: Primary Clustering - long runs of occupied slots form, leading to slow
search times.

○ Quadratic Probing: If hash(key) is occupied, try (hash(key) + 1^2) %

table_size, then (hash(key) + 2^2) % table_size, etc.

■ Issue: Secondary Clustering - keys that hash to the same initial index
follow the exact same probe sequence.

○ Double Hashing: Uses a second hash function hash2(key). The probe sequence
is (hash1(key) + i * hash2(key)) % table_size for i = 0, 1, 2,
....

■ Advantage: Provides better distribution, reducing clustering significantly.

hash2(key) must never return 0.

• Pros: Better cache performance (elements are contiguous), no extra memory for
pointers.
• Cons: More complex deletion, susceptible to clustering (except double hashing),
performance degrades sharply as the table fills up, requires careful selection of probing
strategy.

2.4. Load Factor (α)

The load factor is a crucial metric that indicates how full a hash table is.

• Definition: α = (Number of elements) / (Number of buckets)

• Impact: A higher load factor means more collisions and longer probe sequences/linked
lists, leading to degraded performance.
• Guidelines:

○ For separate chaining, α can be greater than 1 (e.g., 0.7 to 2.0 is common).
○ For open addressing, α should ideally be kept below 0.5 to 0.7 to prevent severe
performance degradation and to ensure there are always empty slots for insertion.

2.5. Rehashing (Resizing)

When the load factor exceeds a certain threshold (e.g., 0.75 for open addressing, 1.0-2.0 for
separate chaining), the performance starts to suffer. To maintain the O(1) average time
complexity, the hash table needs to be rehashed or resized.

• Process:

1. Create a new hash table (internal array) that is typically twice the size of the
original.
2. Iterate through all elements in the old hash table.
3. For each element, re-calculate its hash value using the new table_size and
insert it into the new hash table.
4. Discard the old hash table.

• Cost: Rehashing is an O(N) operation (where N is the number of elements), as every

element must be re-inserted. However, because it happens infrequently and the cost is
amortized over many O(1) operations, the average time complexity for insert/delete
remains O(1).

3. Performance Analysis

• Average Case (with good hash function and proper load factor management):

○ Search: O(1)
○ Insert: O(1)
○ Delete: O(1)

• Worst Case (poor hash function, high load factor, all elements collide):

○ Search: O(N) (degrades to linked list or linear scan)

○ Insert: O(N)
○ Delete: O(N)

This near-constant time performance in the average case is what makes hash tables
incredibly powerful and widely used.

4. Applications of Hash Tables

Hash tables are fundamental and pervasive in computer science:

1. Dictionaries/Maps (Key-Value Stores): The most common application. Programming

languages provide built-in Dictionary (C#), HashMap (Java),
std::unordered_map (C++), dict (Python), Object (JavaScript) types, all
typically implemented using hash tables.
2. Symbol Tables in Compilers/Interpreters: Used to store information about identifiers
(variables, functions) during compilation or execution, allowing for quick lookup of
their properties.
3. Database Indexing: Used to quickly locate records in a database based on a key (e.g.,
primary key).
4. Caches: Used to store frequently accessed data in a fast-access memory area. When a
request comes in, the cache quickly checks if the item is present using a hash table.
5. Set Data Structures: To store a collection of unique items and perform fast
membership testing (e.g., std::unordered_set in C++, HashSet in Java).
6. Password Verification: Instead of storing plaintext passwords, their cryptographic
hash (a one-way hash function) is stored. When a user logs in, their entered password is
hashed and compared to the stored hash.
7. Data Integrity Checks (Checksums): Cryptographic hash functions are used to
 generate a unique "fingerprint" of a file or message. Any alteration to the data will
result in a different hash, indicating tampering. (Note: This is a specific type of hash
function, designed for security, not just distribution.)
8. Routers: Maintain routing tables to map IP addresses to network interfaces for efficient
packet forwarding.

5. Conclusion

Hash tables are a cornerstone data structure, valued for their exceptional average-case
performance in searching, insertion, and deletion. Their efficiency is critically dependent on
a well-designed hash function and effective collision resolution strategies. While they have a
worst-case O(N) complexity, careful design and dynamic resizing ensure that O(1) average
performance is maintained in most practical scenarios, making them indispensable in a vast
array of computing applications. Understanding hash tables is crucial for anyone delving into
efficient algorithm design and data management.