4 ms·

Is this probing scheme better than cuckoo hash? Also, Java hashmaps also used to use separate chaining but switched to using redblack tree for each bucket[1].

by rawnlq 10y ago

Is this probing scheme better than cuckoo hash? Also, Java hashmaps also used to use separate chaining but switched to using redblack tree for each bucket[1]. The main reason was to prevent attackers from choosing worst case inputs where everything gets hashed into one place and degenerate to O(N) search. It seems like with the new change Ruby is still vulnerable to these hash dos attacks. [1]http://grepcode.com/file/repository.grepcode.com/java/root/jdk/openjdk/8u40-b25/java/util/HashMap.java#165 http://grepcode.com/file/repository.grepcode.com/java/root/j...

jay-anderson 10y ago
Java still uses a linked list chaining until a threshold is met (8 currently) which it then switches the bucket to a tree. I wish java could switch to open address hashing, but without value types it wouldn't help much (there's work on adding them: http://cr.openjdk.java.net/~jrose/values/values-0.html http://cr.openjdk.java.net/~jrose/values/values-0.html). Linear probing would likely be better than cuckoo hashing from a cpu cache perspective (all locations closer in memory). There are probing schemes which result in low number of checks and allow for higher loading factors similar to cuckoo hashing (e.g. robin hood hashing. See http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar...)
- dom0 10y ago
  Strategy performance seems to be a rather mixed bag. In some testing we've done RH (completely implemented) performed somewhat worse across the board, but allowed higher load factors, compared to simple linear-probing. However, it would seem that RH doesn't (directly) suffer from tombstoning, which is rather problematic with LP for long-lived tables.
foota 10y ago
I don't know if it was merged, but according to the thread Vlad was working on a patch that would switch to a cryptographically secure hash function when it detected an attempt to create a hash dos attack.

by rawnlq 10y ago

jay-anderson 10y ago

Java still uses a linked list chaining until a threshold is met (8 currently) which it then switches the bucket to a tree. I wish java could switch to open address hashing, but without value types it wouldn't help much (there's work on adding them: http://cr.openjdk.java.net/~jrose/values/values-0.html http://cr.openjdk.java.net/~jrose/values/values-0.html). Linear probing would likely be better than cuckoo hashing from a cpu cache perspective (all locations closer in memory). There are probing schemes which result in low number of checks and allow for higher loading factors similar to cuckoo hashing (e.g. robin hood hashing. See http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar...)

dom0 10y ago
Strategy performance seems to be a rather mixed bag. In some testing we've done RH (completely implemented) performed somewhat worse across the board, but allowed higher load factors, compared to simple linear-probing. However, it would seem that RH doesn't (directly) suffer from tombstoning, which is rather problematic with LP for long-lived tables.

foota 10y ago

I don't know if it was merged, but according to the thread Vlad was working on a patch that would switch to a cryptographically secure hash function when it detected an attempt to create a hash dos attack.