Separate Chaining: Implementation
What you'll learn: How to implement the core hash table operations—insert, search, and delete—when using linked lists to handle collisions at each bucket.
The Core Idea
In separate chaining, each slot (bucket) in your hash table array stores a linked list instead of a single value. When a collision occurs (two keys hash to the same index), you simply add the new item to that bucket's list. This means implementing hash table operations now combines array access with linked list operations.
Insert Operation
- Compute the hash:
index = hashFunction(key) % tableSize - Access the bucket (linked list) at
table[index] - Insert the key-value pair at the head of that list (or tail, if you maintain a tail pointer)
This is just inserting at the head of a linked list—something you already know!
Search Operation
- Compute the hash to find the bucket
- Traverse the linked list at that bucket
- Compare each node's key with the search key
- Return the value if found, or indicate "not found"
You're combining array indexing with linked list traversal.
Delete Operation
- Compute the hash to locate the bucket
- Search through that bucket's linked list for the target key
- Delete the specific node using standard linked list deletion (adjusting pointers)
Why This Works
Think of it like a filing cabinet (the array) where each drawer (bucket) contains a folder of papers (linked list). When you need to file a document, you open the correct drawer and add it to the folder inside. Multiple documents can share the same drawer without conflict.
Key Takeaway: Separate chaining implements hash table operations by using the hash function to select an array bucket, then performing standard linked list operations (insert, search, delete) on the list stored at that location.