Source: Comprehensive Guide on Hash Tables and Collision Resolution Techniques (UCF Computer Science I)
Tags: hash table, hash map, hashing, hash function, dictionary ADT, table ADT, key-value pair, chaining, separate chaining, collision resolution, load factor, division method, direct addressing, O(1) lookup
Difficulty: Introductory to Intermediate
Prerequisites: Basic understanding of arrays, linked lists, and Big-O notation.
Hash tables are one of the most frequently used data structures in computing, and they show up in nearly every CS course from this point forward. They solve a fundamental problem: how do you look something up by its key as fast as possible? The answer is to convert the key into an array index using a hash function, giving you expected O(1) access. This set of notes covers what hash tables are, how hash functions work, and how chaining handles the inevitable case where two keys land on the same slot.
A hash table maps keys to array indices using a hash function, enabling near-instant lookups. When two keys map to the same index (a collision), chaining stores them in a linked list at that slot. Performance stays close to O(1) as long as the load factor (elements / slots) remains low.
Table (Abstract Data Type)
A data structure that stores records as key-value pairs, allowing you to retrieve information by its unique key. Think of it as a digital filing cabinet where every folder has a label and you pull the one you need.
Dictionary
A dynamic collection that supports three core operations: Insert, Search, and Delete. In simple terms, it is the general concept that hash tables implement.
Hash table
An array-based implementation of a dictionary. It uses a hash function to convert a key into an index, then stores the record at that index. Think of it as a shortcut that tells you exactly which shelf to check.
Hash function
A function that takes a key as input and returns an integer index within the table's range. In simple terms, it is the rule that decides where each record lives in the array.
Hash value (hash code)
The index returned by the hash function for a given key.
Collision
The event where two different keys produce the same hash value, so they both want to occupy the same slot. This is unavoidable when the key space is larger than the table.
Direct addressing
A lookup strategy where the key itself is the index. Fast (O(1)), but only practical when the range of possible keys is small and dense enough to fit in memory.
Division method
A common hash function: h(key) = key mod m, where m is the number of slots. Simple and widely used.
Chaining (separate chaining)
A collision resolution strategy where each slot in the hash table points to a linked list. All keys that hash to the same slot live in that list.
Load factor (α)
The ratio n/m, where n is the number of stored elements and m is the number of slots. It measures how full the table is. A lower load factor means shorter chains and faster lookups.
Direct addressing uses the key as the array index, giving O(1) lookup with zero computation beyond the index itself.
Requires the key space to equal the address space.
Impractical when keys are sparse or very large (e.g., 10-digit ID numbers would need a billion-slot array).
Hashing compresses a large key space into a smaller address space by computing h(key).
The trade-off: you gain memory efficiency but introduce the possibility of collisions.
Deterministic: the same key always produces the same hash value. Without this, you could never find your data again.
Uniform distribution: keys should spread evenly across all available slots, minimising collision clusters.
Computationally efficient: the function should be quick to evaluate, since it runs on every insert, search, and delete.
Formula: h(key) = key mod m
m is the number of hash table slots.
Works well when m is a prime number not close to a power of 2, because this reduces patterned clustering.
Each slot in the array holds a pointer to the head of a linked list.
When a new key hashes to a slot that is already occupied, the key is added to that slot's list, typically at the head for O(1) insertion.
To search, hash the key to find the slot, then walk the linked list comparing keys.
Table size: 9 slots, hash function h(k) = k mod 9.
Insert keys: 5, 28, 19, 15, 20, 33, 12, 17, 10.
5 mod 9 = 5 → slot 5
28 mod 9 = 1 → slot 1
19 mod 9 = 1 → slot 1 (collision with 28, added to slot 1's list)
15 mod 9 = 6 → slot 6
20 mod 9 = 2 → slot 2
33 mod 9 = 6 → slot 6 (collision with 15)
12 mod 9 = 3 → slot 3
17 mod 9 = 8 → slot 8
10 mod 9 = 1 → slot 1 (third key at this slot)
Average search time with chaining: O(1 + α).
When α < 1 (fewer elements than slots), most lists are short and lookups stay close to O(1).
As α grows, chains get longer and search performance degrades toward O(n) in the worst case.
Resizing (rehashing into a larger table) is the standard remedy when α crosses a threshold, often around 0.75 in practice.
Handles dynamic data well; the table does not need to know in advance how many keys will be stored.
Simple to implement: each slot is just a linked list head.
Deletion is straightforward (remove a node from a linked list).
Each pointer in each linked list node costs extra memory.
If the hash function distributes poorly, one slot can accumulate most of the keys, and performance collapses.
Division method hash function
h(key) = key mod m
Average search time (chaining, successful search under simple uniform hashing)
O(1 + α), where α = n / m
Hash tables underpin most of the instant lookups you encounter: Python dictionaries, JavaScript objects, database indexing, in-memory caches, and the DNS system that translates domain names to IP addresses. Whenever software needs to go from a name or identifier to its associated data in constant time, a hash table is almost certainly involved.
Students often assume hash tables guarantee O(1) in all cases. They do not. O(1) is the expected (average) time under reasonable assumptions; worst-case is O(n) if every key collides.
Students sometimes think a collision means the data is lost. It is not lost; it is stored through the collision resolution mechanism (here, a linked list).
Students confuse load factor with table fullness. A load factor of 2 does not mean the table is "200% full" in an impossible sense; it means there are twice as many elements as slots, which is perfectly valid with chaining, just slow.
Students sometimes believe the hash function output can exceed the table size. By definition (mod m), it cannot.
⚠️ You will almost certainly be asked to insert a series of keys into a hash table using a given hash function and identify which slot each key occupies. Practise the mod arithmetic by hand.
⚠️ Know the three properties of a good hash function (deterministic, uniform, efficient). These appear as short-answer or multiple-choice staples.
⚠️ Be ready to calculate the load factor given n and m, and explain what happens to performance as α increases.
⚠️ Understand the difference between direct addressing and hashing, and when each is appropriate.
True or False: A hash table guarantees O(1) search time in the worst case.
Fill in the blank: The load factor α is defined as ______.
True or False: In chaining, a slot can hold more than one key.
Fill in the blank: h(key) = key mod m is called the ______ method.
True or False: Direct addressing is practical when the key space is very large and sparse.
Answers: 1. False (O(1) is expected, not guaranteed). 2. n/m (number of elements divided by number of slots). 3. True (via the linked list). 4. Division. 5. False (it requires the key space to match the address space, which is impractical for large/sparse domains).
Q: Given a hash table of size 7 and h(k) = k mod 7, where does the key 29 go?
A: 29 mod 7 = 1, so it goes into slot 1.
Q: If a hash table has 10 slots and currently holds 8 elements, what is the load factor?
A: α = 8 / 10 = 0.8.
Q: Why is chaining considered simpler to implement than open addressing?
A: Each slot just maintains a linked list. Insertion is an O(1) prepend, and deletion removes a list node, with no need to manage probe sequences or tombstone markers.
Q: What happens to chaining performance if the hash function maps every key to the same slot?
A: All keys end up in a single linked list, and search degrades to O(n), the same as an unsorted list.
Q: Name two properties a good hash function must have.
A: It must be deterministic (same key always produces the same hash) and distribute keys uniformly across the available slots.
This material connects directly to the open addressing collision resolution techniques (linear probing, quadratic probing, double hashing) covered in the companion notes. Understanding chaining first makes it easier to see why open addressing trades pointer overhead for probe sequences. Hash tables also reappear in graph algorithms (adjacency lists), compiler symbol tables, and caching strategies later in the course.
hash table, hash map, hash set, hashing, hash function, dictionary, associative array, key-value store, separate chaining, collision, collision resolution, load factor, division method, mod operator, direct addressing, dynamic collection, linked list, Big-O, constant time lookup, rehashing, table ADT, COP 3502, UCF Computer Science I