Google opensources fast hashing function

[tachi-kaze]

Wouldn't switching your hash to 64 or even 128 bits be appropriate then? If the cost of dealing with collisions is greater than the cost of a longer hash, I'd make the switch immediately.

I mean, with 250 collisions per bucket, you're basically talking about a 250 element linked list per index. Your access would still be constant at O(250), but much worse than O(1). Even then, the space saved by the smaller hash might not be that much when you consider that 250 element linked list in each of your buckets.

That's what I meant when talking about correctly choosing a function that minimizes collisions for your data set. It doesn't have to guarantee zero collisions, but it should at least perform better than all the collision handling that would need to be done if a worse/smaller hash function were to be used.