The oldest collision fix: each bucket holds a list, and colliding keys just append. Lookup hashes to a bucket and walks its chain. Simple, tolerant of high load, and the chain length is the collision count. Here five keys mostly hash to bucket 5 (mod 7), giving a chain of 4 while bucket 0 holds 1 — the collisions made visible.
THE TECHNIQUE bucket(k) = k mod m; append on collision
The demo drops five keys into 7 buckets and counts the longest chain: live demo
HISTORY & CREDIT Luhn / Dumey · 1950s
“Chaining wastes memory on pointers.” — it trades a little memory for graceful behavior past load factor 1, where open addressing collapses. cited
the bucket · k mod m picks the list. the chain · collisions append; lookup walks the list. 1953 · hash tables with chaining are credited to Hans Peter Luhn (IBM memo) and Arnold Dumey (1956).
The default hash table, still. data structure
RECOMMEND FOR I-13 the chains, on the compiler
On i-13, five keys give a longest chain of 4 (bucket 5) and 1 (bucket 0):
$ i13 run hs_chaining.i13
RUN OK · 348 step(s) · peak stack 11
chain5 = 4
chain0 = 1
longest_chain = 4
Recommend as a NULL — a data structure (PS-015 linked lists) + a computed count (B39/B40). The chain length is a pinned function of the keys and modulus; chaining vs open addressing compute the same key→value map, differing only in layout (B44) and probe cost (B40). NULL — a bucket is a list.