Steven Grimm wrote:
I'm much more in favor of making "n" large enough that it's reasonable
to say something like, "Oops, that bucket is taken already; overwrite
it with me if the address of the node it currently points to is
numerically less than mine, else don't insert myself here." Then you
will deterministically end up with exactly the same search tree no
matter what order the nodes are inserted. If you are inserting each
node 10 times in a tree and your search space is a full 32 bits, the
occasional node that's inserted 9 times instead is going to be
basically irrelevant to the health of the system. Not perfectly
balanced, sure, but there will almost never be any collisions to begin
with and it isn't worth optimizing such a rare edge case.
Yeah. We don't care about this case at the moment - our "n" is 2^32, and
the number of times we insert each server is 160 (which is a fairly
arbitrary number we found empirically). So the chances of a collision
are about 1 in 250,000 for us at the moment, which is acceptable. This
is probably an improvement that needs to be made, though.
--
Russ Garrett
Last.fm Ltd.
[EMAIL PROTECTED]
