Imagine organizing a collection of baseball cards in an array. Giving every possible card ID its own array position would waste enormous space. A hash function lets a smaller array, called a hash table, turn a key into a usable position. If the table has m cells, that position must be an integer from 0 to m − 1. For non-integer objects, first extract an integer key, then compute the position. section 12.13 section 12.14 section 12.18
A good function spreads keys across the cells rather than sending many to the same place. Ideally, each key would be equally likely to land in any cell, but real key patterns make that hard to guarantee or even verify. The practical aim is to choose a function that does not preserve troublesome patterns in the data. section 12.14
Computing an index by multiplication
Choose a constant A and an integer key k. Keep the fractional part of k × A, multiply it by the table size m, and take the integer part: floor(m × ((A × k) % 1)). An integer A would make the fractional part zero every time. One suggested choice is A = (√5 − 1) / 2; the best choice still depends on the keys. section 12.16
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 Python implementation separates key extraction from index calculation: extract_key defaults to the built-in hash function, while _hash maps its integer result to a bucket. section 12.18
Two different keys can still produce the same index: this is a conflict. It cannot be ruled out when there are more possible keys than cells. Chaining keeps a linked list at each cell; open addressing tries other cells when the first is occupied. With chaining, the length of those lists affects search time. Hash tables offer constant-time operations on average, but a poor distribution of keys can make performance linear in the worst case. section 12.17 section 12.18 section 12.22
