Hacker News Reader

Comment by bjourne | Hacker News Reader

So the reason HashMap isn't as fast as it could be is because it converts buckets with linked lists to red-black trees when it reaches some threshold. The reason it does that is because in any hashing scheme, specifically crafted input can cause O(n) lookup times. It is reasonably trivial to take advantage of this to launch DOS attacks. Your web server parses HTTP headers with a hash table? Might very well be exploitable. Same thing with parsing JSON objects using hash tables. I posit that in practice there are very few scenarios in which the extra performance of an "optimized" hash table outweighs the benefits of having one that is not vulnerable to hash-flooding attacks.

View on HN

> Your web server parses HTTP headers with a hash table? Might very well be exploitable.

That is why you shouldn't use hash tables in code that might (even potentially) become a target for DoS attacks.

You can have hash tables that cannot be targeted by DoS attacks.

You can use a family of hash functions and seed the hash table instance with a key.

The attacker won't be able to do make assumptions regarding collisions because he doesn't have access to the initial key.

This being universal hashing right? Is there an implementation of this?

The tree conversion does not affect performance at all. It is only done on DOS attacks, which almost never occur. Counting the collisions is almost for free.

The optimizations are cache friendly open-addressing with linear probing, storing the hash, and power of 2 sizes. Another usual optimization would be a sorted array instead of the linked list.

You can always use a cryptographic hash of the key instead of an untrusted key.

Linked list buckets are terrible for cache locality anyway.

Can you show me an implementation of a high-performance hash table with a cryptographic key that is not vulnerable to hash-flooding?

All you have to do is have the hashmap be HashMap<K,V,CryptographicKey> and never reveal the key, or seed it from randomness? One can use an HMAC or some other method to use the key to derive hashes.

Is there as HashMap overload with three type parameters? Yes, you can use a cryptographic hash function like SipHash does but it wouldn't perform has well as HashMap.

In Java? No. Rust is safe out of the box while retaining O(1) properties at all times

But there is a heavy multiplier on that O(1) with the default hasher in Rust. My benchmarking has shown that FNVHasher gave me a 24% decrease in execution time over the default hasher. My use case had a high likelihood of a poll on the hash indicating that there was no match, and I got a near doubling of speed just by setting the initial capacity sufficiently large.

Rust's standard library HashMap is a good example.

Reply on news.ycombinator.com