Oct. 22, 2009
6:43 p.m.
Andres Valloud wrote:
I thought I'd point out a subtle potential problem. Assume N = 1000, f(x_j) = j-1, and so k = 1 because 0 <= f(x_j) < N because 0 < j <= 1000. Now, store x_{7i} in a Set, for all i such that 1 <= 7i <= 1000. Clearly, f(x) is a perfect hash function as defined above. However, if the size of the table used by the set is a multiple of 7, performance will be terrible.
Huh? If your hash function produces integers between 0 and 999, your table size must be at least 1000, otherwise you store past the end of your table. Regards, -Martin