[Scaevolus]

Having per-table random seeds and properly designed hash function prevents remotely forced collisions. This is the typical defense against hashtable DOS.

It has to be done properly, of course -- for example, a poorly designed hash function could have characteristic collisions for many different seeds.

[haberman]

Please be aware that many common hash functions are easy to generate collisions for independent of the seed. This includes both MurmurHash and CityHash. These aren't poorly-designed hash functions: they have excellent distribution characteristics. But the way they use their seed wasn't designed to resist this kind of attack.

[Scaevolus]

Rather than "poorly-designed", I should have said "cryptographically insecure".

Most hash functions are engineered for speed and collision resistance, in that order. Trading collision resistance for speed is worthwhile for many workloads, since it barely affects the average case.

[haberman]

> Most hash functions are engineered for speed and collision resistance, in that order.

I disagree with that assessment. I think most hash functions are designed for speed and good distribution of outputs given normal inputs. But designing to resist collisions against someone trying to deliberately create them is a different thing entirely.

> Trading collision resistance for speed is worthwhile for many workloads, since it barely affects the average case.

I think that is far from established. SipHash is marketed under this premise, but from what I have heard it is significantly slower, particularly for short inputs.

[Scaevolus]

Yes, speed for normal inputs is what's generally desired.

A faster hash function can yield better overall performance than having fewer collisions. Here's some empirical evidence for this: https://www.strchr.com/hash_functions

The speed is correlated only weakly with the number of collisions-- and using the modern x86 CRC32 instruction yields the best results.

[nickpsecurity]

I suggest somebody test SpookyHash-128 similarly to those to see how it performs. Designed to be collision resistant and fast.

http://www.burtleburtle.net/bob/hash/spooky.html

[CiPHPerCoder]

Why not SipHash? https://www.131002.net/siphash/