Hashing with Separate Chaining

CSC-211 · Semester III · Data Structures and Algorithms

intermediate25 minAvailable

HashingDirect access · O(1) avg

slot 0

slot 1

slot 2

slot 3

slot 4

slot 5

slot 6

slot 7•

h(k) = k mod 8 · amber slots were placed there by linear probing after a collision · • = home slot of target

Target

Step

0/ 9

Result

…

Lab brief

Objective

Map keys to slots with a hash function and resolve collisions by storing colliding keys in per-slot linked chains.

Theory & concepts

Separate chaining gives every hash-table slot its own linked list. The hash function decides which chain a key belongs to; collisions just append to the chain. Search hashes to the slot and walks the chain, so the cost depends on the average chain length — the load factor α = n/m.

Rendering diagram…

Hashing with separate chaining

Table size 5, h(k) = k mod 5:
    insert 10 → slot 0 → chain: [10]
    insert 25 → slot 0 → chain: [10, 25]   (collision, appended)
    insert 6  → slot 1 → chain: [6]
Search 25 → hash to 0, walk chain → found after 2 nodes
Average chain length = α; search stays near O(1) even
at high load because chains stay short.

Chaining tolerates high load

Unlike open addressing, separate chaining keeps working near α = 1 and beyond — the table degrades gracefully as chains lengthen. This robustness is why many standard library hash maps use chaining.

Prerequisites

Lab: Hashing with Linear Probing
Linked list basics

Instructions

1Insert keys one at a time and watch each hash index compute.
2When a slot is already occupied, watch the new key append to its chain.
3Search for an inserted key and follow the chain walk.
4Compare chain lengths across slots and identify the load factor.
5Insert several keys that share a slot and observe the longest chain.

Tasks

Build the table
Insert the sample keys and verify each chain contents.
Longest chain
State which slot has the longest chain and its length.
Load factor
Compute α after the sample insertions and estimate average chain length.

Self-check

Every key lands in the chain for its hash index.
Collisions append without evicting earlier keys.
The student relates chain length to the load factor.

Environment

hash gridper-slot chainsmod computationinsert/searchchain length display