Course contentsShow
← Computer Science
Lesson 409 of 2,87210. Hash TablesFree lesson

The Multiplication Method

Hashing by extracting middle bits from k*A where 0 < A < 1, independent of table size.

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.