Practice question · Multiple choice
A hash function reduces a key modulo the table size. Why do implementations favour a prime table size?
Hints
- Take keys that are all multiples of 10 and a table of size 100. Which buckets get used?
- Ask what a shared factor between key pattern and table size does to the remainders.
Show the answer
A. Because a composite size shares factors with patterned keys
Why
Keys are rarely random, they are IDs, addresses, timestamps, often sharing a factor. With size 100 every multiple of 10 lands in ten buckets and ninety sit empty; a prime shares no factor with the pattern, so the remainders spread. Number theory earning its keep in a data structure.
Practise Divisibility and the Division Algorithm
The app has 6 more questions on this lesson, and keeps your place in the course. Mathematics I is free to start.
More questions on Divisibility and the Division Algorithm
- Select every integer below that divides 84.
- Order the steps of the proof that if a divides b and a divides c, then a divides b + c.
- Since 47 = 6 x 6 + 11 is a true equation, it gives the quotient and remainder of 47 divided by 6.
- The division algorithm insists the remainder satisfies 0 ≤ r < a. Both 17 = 5·3 + 2 and 17 = 5·2 + 7 are…