The multiplication method computes a hash-table index in three steps: multiply key k by a constant A, keep the fractional part, then multiply by table size m and take the integer part. The result falls between 0 and m − 1. section 12.16
Use the method with these practical choices in mind:
- Avoid integer values for A because their fractional product is always zero; A = (√5 − 1)/2 is a broadly useful default. section 12.16
- Choose m more freely than with the division method; powers of two can work well and may allow calculation optimizations. section 12.16
- Expect nearby keys to map to widely separated indexes, helping distribute entries across the table. section 12.16
Hashing a key
For a table with m buckets, compute h(k) = floor(m × ((A × k) % 1)). A chained hash table can apply this index to select a bucket, then store the value in that bucket’s linked list. section 12.16 section 12.18
h = lambda k: math.floor(m * ((A * k) % 1))
Inspect the compact lambda implementation of the multiplication hash function. section 12.16
