I think it was a reasonable discussion, it just had some faulty conclusions. Using binary trees for overflow buckets is silly. They may be O(N), but the O can

I think it was a reasonable discussion, it just had some faulty conclusions. Using binary trees for overflow buckets is silly. They may be O(N), but the O can be much larger if you keep them balanced. A much better strategy for dealing with pathological cases is to keep some simple statistics such as the maximum bucket size or the average size of occupied buckets. If you see a pathological case change the hash function and rehash. No need for seeds, or trees or all that. The discussion of the cost of reallocation seems somewhat overblown. Everyone here knows that if you are going to have a million or billion entries, you dont start with the default allocation or give a fixed increment. Anyway, a good implementation should keep track of the allocation pattern and make adjustments along the way. He does make a good point that you need to pay attention to your hash function. A good function should try to smear the bits out so that the beginning and end of (say) a string make similar contributions to the hash.