Can You Hash This Out?
A puzzle from The Ohio State University
Consider a data structure that uses
hashing to efficiently store and
retrieve integers. Prove that for any
hash table size greater than 2, even
the usually-reliable prime numbers,
“hash(x) = x^ 2” is a poor hash func-
tion. More specifically, prove that
there will always be an empty bucket.
—Dr. Bruce W. Weide and colleagues at
The Ohio State University
Find the solution at: http://xrds.acm.org
A Great Time for PhDs in the Job Market
PhD Comics © Jorge Chan, used with permission
Can you can do better? Bemusements would like your puzzles and mathematical games (but not Sudoku).
email@example.com to submit yours!