5 ms·
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 reaso
by bjourne 5y ago
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.
- vlovich123 5y agoYou can always use a cryptographic hash of the key instead of an untrusted key. Linked list buckets are terrible for cache locality anyway.
- bjourne 5y agoCan you show me an implementation of a high-performance hash table with a cryptographic key that is not vulnerable to hash-flooding?
- goldenkey 5y agoAll 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.
- bjourne 5y agoIs 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.
- vlovich123 5y agoIn Java? No. Rust is safe out of the box while retaining O(1) properties at all times
- dhosek 5y agoBut 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.
- vlmutolo 5y agoRust's standard library HashMap is a good example.
- rurban 5y agoThe 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.
- q-big 5y ago> 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.
- nomemory 5y agoYou 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.
- Woberto 5y agoThis being universal hashing right? Is there an implementation of this?