This is not my experience. Frequently, hash tables will have a size that is a power of 2, and the address into the table will be all of the low order bits. A table with 1 million slots will use 20 bits of hash.
> Second, against DDOS only uhash, or using no linked lists or arrays with O(n/2) lookup costs help.
uhash is just one example of hash function designs based on almost-universal hashing. There are many others, including VHASH and Poly1305. Is HighwayHash almost universal?
It looked like that was what rurban was arguing? Pull out the low 5-8 bits, get a table of size 32-256?
And on top of that I guess nobody ever heard of "Cache-Conscious Collision Resolution in String Hash Tables" by Nikolas Askitis and Justin Zobel, who measured that a linear search in an array for collisions outperforms a linked lists by 2-4x, even if that can do move-to-front much easier.
People still do worry about the hash function, where they do should worry about their hash tables instead, which can easily be made 4x faster and not 2x slower.
Hash "functions" like UHASH, Poly1305, and SipHash are actually families of hash functions, parameterized by seed.
> And on top of that I guess nobody ever heard of "Cache-Conscious Collision Resolution in String Hash Tables" by Nikolas Askitis and Justin Zobel, who measured that a linear search in an array for collisions outperforms a linked lists by 2-4x, even if that can do move-to-front much easier.
If an implementation is vulnerable to hash-flooding attacks because it doesn't have a randomly-seeded almost-universal hash function, then changing the collision mechanism from linked lists to arrays isn't going to fix the problem.
Good collision resolution and good hash functions are both issues worth addressing.
and from the linked smasher page:
> You can attack every single hash function, even the best, if you detect the seed, ...
But the most efficient known way to recover the SipHash key is still bruit force.[0] Good luck making an average of 2^127 guesses.
[0] http://link.springer.com/chapter/10.1007/978-3-319-13051-4_1...
First, from any hash only a few bits are use for a hash table lookup, typically between 5-8. It depends on the size of the table. You can make your hash function long and strong, but only the last few bits count, and this does not help you at all against DDOS.
Second, against DDOS only uhash, or using no linked lists or arrays with O(n/2) lookup costs help. A random seed is good, but can be detected. E.g. a timeout as used by djb in his nameserver does help better than a stronger hash function. Or using a hash table as in glibc, gcc or the linux kernel. siphash or HighwayHash does not help at all. python and perl both fell into this trap.
But I appreciate the effort to create a fast metro like hash function, without resorting to the internal crc32 builtin. Will be included in smhasher soon.
Summary: https://github.com/rurban/smhasher#summary