Imagine five pigeons arriving at four holes: two must share one. Hash tables face the same problem when different keys map to one array index. Chaining resolves the conflict by making each table cell reference a linked list or grouped collection of values. section 12.17 section 12.22
A chained hash table handles its main operations as follows:
- Insert: hash the value's key, find the bucket, and add the value to the front of that bucket's linked list. section 12.18
- Search: inspect the bucket's list with a key-matching predicate; average time is O(1 + n/m), where n is the number of elements and m the number of buckets. section 12.18
- Delete: hash the key and remove the matching value from the corresponding list. section 12.18
Chaining keeps growing beyond the initial bucket count, but long chains reduce performance. With a poor key distribution, search and deletion can take O(n); average insertion, search, and deletion remain constant-time when chains stay short. section 12.18 section 12.22
A small Python implementation
A HashTable can store one SinglyLinkedList per bucket, compute an index with a multiplication-method hash, and delegate insertion, searching, and deletion to the selected list. A customizable key extractor allows values to be indexed by a chosen key. section 12.18
class HashTable:
__A__ = Decimal((sqrt(5) - 1) / 2) #1
def __init__(self, buckets, extract_key=hash):
self._m = buckets
self._data = [SinglyLinkedList() for _ in range(buckets)]
self._extract_key = extract_key
def _hash(self, key):
return floor(self._m*((Decimal(key) * HashTable.__A__)%1))
#1 The constant for the multiplication method, defined as a class property
View the compact HashTable definition that creates one singly linked list per bucket and computes bucket indexes. section 12.18
