On Sat, Dec 31, 2011 at 7:03 AM, Stephen J. Turnbull <firstname.lastname@example.org>
While the dictionary probe has to start with a hash for backward
compatibility reasons, is there a reason the overflow strategy for
insertion has to be buckets containing lists? How about
This won't help, because the keys still have the same hash value. ANYTHING you do to them after they're generated will result in them still colliding.
The *only* thing that works is to change the hash function in such a way that the strings end up with different hashes in the first place. Otherwise, you'll still end up with (deliberate) collisions.
(Well, technically, you could use trees or some other O log n data structure as a fallback once you have too many collisions, for some value of "too many". Seems a bit wasteful for the purpose, though.)