-1

Suppose we are building a hash table of size $m = F_{k}$ using the hash function $$h(x) = (F_{k−1} · x) \bmod {F_{k}} $$ Prove that if the consecutive integers $0, 1, 2, . . . , F_{k−1}$ are inserted in order into an initially empty table, each integer is hashed into one of the largest contiguous empty intervals in the table.

I found this problem as graduate algorithm's homework at UIUC in 2007. I think a lot on it, but i have no progress.

Do you have any idea?

After edit: $F_{k}$ is the $k^{th}$ Fibonacci number.

P.S. $\textit{It works for any pair of relatively prime integer}$

flag
How about showing that the table always has some pattern - I think it has intervals of length $F_l$, $F_{l−1}$, and $F_{l-2}$ for some $l$ and they are distributed in some nice way. – Colin McQuillan Dec 16 2010 at 13:37
But I think this observation is not correct, consider m = 13: 0 - - 2 - - 4 - 1 - - 3 - 2 This is the hash table after inserting 0,1,2,3,4. But maybe we can improve your idea? – Nasooh Alavi Dec 16 2010 at 13:38
Yes sorry, I've tried again. – Colin McQuillan Dec 16 2010 at 13:38
3 
 math.stackexchange.com might be helpful here. – S. Sra Dec 16 2010 at 13:45
I asked this question in cstheory.stackexchange.com, and I received helpful hints. Actually, this property holds for any pair of relatively prime integers. – Nasooh Alavi Dec 17 2010 at 9:53

closed as off topic by Andrew Stacey, Will Jagy, Gjergji Zaimi, Andreas Thom, Franz Lemmermeyer Dec 17 2010 at 15:04

Browse other questions tagged or ask your own question.