A hash chain is a linked list attached to one hash-table bucket. When multiple values map to the same bucket, the list stores them instead of forcing several values into one array cell. section 12.18
A chained hash table handles values in three practical steps:
- Hash a value’s key to select a bucket. section 12.18
- Insert new values at the front of that bucket’s singly linked list; append instead when duplicate checking is required. section 12.18
- Search or delete by selecting the bucket and delegating traversal to the linked list. section 12.18
A bucket with several values
If several keys hash to bucket i, that array cell points to a chain containing all of them. Average insertion takes O(1), while search and deletion take O(1 + n/m), where n is the number of stored elements and m is the number of buckets; the worst case is O(n). 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
The implementation listing shows buckets backed by singly linked lists, a configurable key extractor, and the multiplication method for hashing. section 12.18
