<div class="gmail_quote">On Sat, Dec 31, 2011 at 7:03 AM, Stephen J. Turnbull <span dir="ltr"><<a href="mailto:stephen@xemacs.org">stephen@xemacs.org</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">
<div class="im">While the dictionary probe has to start with a hash for backward</div>
compatibility reasons, is there a reason the overflow strategy for<br>
insertion has to be buckets containing lists? How about<br>
double-hashing, etc?<br></blockquote><div><br></div><div>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.</div>
<div><br></div><div>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.</div>
<div><br></div><div>(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.)</div>
</div><br>