Comments on research!rsc: Rotating Hashes

Err, I meant Russ. How embarrassing, sorry! :)

2008-03-22T04:01:00.000-04:00

Err, I meant Russ. How embarrassing, sorry! :)

Hi Ross,Generating and trying multiple hash values...

2008-03-22T03:54:00.000-04:00

Hi Ross,

Generating and trying multiple hash values has found a more recent application in Cuckoo hashing, which offers worst-case O(1) lookup. And it works very well -- I've used an implementation in production that keeps over 2 million elements with a 0.99 load factor. See http://www.it-c.dk/people/pagh/papers/cuckoo-undergrad.pdf, but to achieve these high load factors, you have to generalize the number of hash functions partitions to 5 or so.

@rsc: I think your point about computing several h...

2008-03-12T15:21:00.000-04:00

@rsc: I think your point about computing several hashes applies to non-linear scanning, not to linear scanning, which is what the random scanning is being compared to in the article. -- Btw, it occurs to me that an advantage that random does have over linear is that each collision group's scan sequence is unique. With linear scanning, when a clump starts to form, it affects the performance of all nearby collision groups. This may explain the performance improvement gained with random scan.

@nasorenga: It performs better because you compute...

2008-03-12T15:08:00.000-04:00

@nasorenga: It performs better because you compute more bits than you need for a single hash, but not necessarily as many as you need for n different hashes. You might compute a 36-bit hash and then use different 16-bit windows as the scanning sequence.

Seems to me that with the simple bit-rotation meth...

2008-03-12T14:25:00.000-04:00

Seems to me that with the simple bit-rotation method, all members of a collision group will have the same sequence of addresses, making it equivalent to linear scanning. So why does it perform better?