Unit 5 · Lesson 218 minAcademic review pending

Four formulas, one job

Division, multiplication, mid-square, and folding all compute an index from a key. They differ only in how carefully they avoid clustering keys into the same few slots.

Choose explanation

After this lesson

You should be able to

Compute a hash value using each of the four named methods.
Explain why the division method should avoid table sizes that are powers of two.
Explain what folding is useful for that the other three methods are not.

Division method: the one you already used

index = key % table_size — Lesson 1's hostel formula. Its one real pitfall: choosing a table size that is a power of two throws away information, because the remainder then depends only on the key's lowest bits, ignoring the rest entirely. A prime table size, like the 11 used in the widget below, avoids this and spreads keys far more evenly.

Prime versus power-of-two table sizes

int h1 = key % 11;   /* prime table size: spreads keys well   */
int h2 = key % 16;   /* power of two: only the low 4 bits of key
                         actually influence the result */

Multiplication method: spread using a fraction

Multiply the key by a carefully chosen constant between 0 and 1 (commonly related to the golden ratio), keep only the fractional part of the result, then scale that fraction up to the table size. Unlike the division method, this does not depend on the table size being prime to spread keys well — the constant does the spreading work instead.

The constant does the spreading, not the table size

double A = 0.6180339887; /* related to the golden ratio */
double fractional = (key * A) - floor(key * A);
int index = (int) (table_size * fractional);

Mid-square method: square it, keep the middle

Square the key, then extract a few digits from the middle of the result as the index. The middle digits of a squared number tend to depend on every digit of the original key — unlike the division method's remainder, which can be dominated by just the last few digits — so keys that differ only slightly still tend to produce noticeably different indices.

64 squared is 4096; the middle digits become the index

int key = 64;
int squared = key * key;          /* 4096 */
/* take the middle two digits: */
int index = (squared / 10) % 100; /* 409 % 100 = 9 */

Folding method: for keys too big to square comfortably

Split the key into equal-sized chunks, add the chunks together, and use the sum — modulo the table size — as the index. This is the natural choice when a key is long, such as a ten-digit phone number or a lengthy account number, where squaring the whole thing would overflow ordinary integer storage.

Break a long key into pieces, then add

long key = 9876543210L;
int chunk1 = 987, chunk2 = 654, chunk3 = 321, chunk4 = 0;
int sum    = chunk1 + chunk2 + chunk3 + chunk4;  /* 1962 */
int index  = sum % table_size;

Try it yourself

Compute the division-method hash (table size 11), the mid-square hash (keep two middle digits), and describe when folding would suit a phone number 9876501234, versus the other three methods.

Need a hint?

A ten-digit number squared has around twenty digits — far beyond what a normal int can hold without special handling.

Check the worked solution

9876501234 % 11 leaves a remainder computable directly, no overflow concern. Mid-square would require squaring a ten-digit number into a roughly twenty-digit result, which overflows a standard 32-bit int entirely — this is exactly the case folding was built for: split the phone number into chunks (987, 650, 123, 4), add them, and hash the manageable sum instead.

Quick check

Why does the division method spread keys poorly when the table size is a power of two?

Select an answer to check your thinking.

Why this lesson exists

Syllabus mapping

Hash Functions · Division Method · Multiplication Method · Mid-square Method · Folding Method

Maps to course outcomes CO1, CO2.