The Multiplication Method
What You'll Learn: You'll discover how to hash keys by multiplying them with a special fraction and extracting the "middle" bits—a technique that works independently of your table size.
The Core Idea
Remember the Division Method from the previous lesson? It used k % m to squeeze a key into your hash table. The Multiplication Method takes a completely different approach: it multiplies your key k by a constant decimal number A (where 0 < A < 1), then extracts the fractional part and scales it.
Think of it like this: imagine you have a key k = 123. You multiply it by A = 0.618 (a popular choice). You get 123 * 0.618 = 76.014. Now, ignore the whole number part (76) and keep only the fractional part (0.014). Finally, multiply that fraction by your table size m and take the floor: if m = 100, you get floor(0.014 * 100) = 1. That's your hash index!
Formula: h(k) = floor(m * (k * A mod 1))
The expression (k * A mod 1) means "the fractional part of k * A."
Why Use This?
Unlike the Division Method, the Multiplication Method doesn't care much about what m is—you can use any table size, not just primes. The value of A does all the heavy lifting. A commonly suggested value is A ≈ 0.6180339887 (related to the golden ratio), though many values work well in practice.
Key Takeaway: The Multiplication Method hashes keys by multiplying by a constant fraction A, extracting the fractional part, and scaling to your table size—offering flexibility in choosing m without worrying about prime numbers.