6 ms·

If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting. (Theoretically, it has a worst-case constant lookup

by cbhl 8y ago

If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting. (Theoretically, it has a worst-case constant lookup time. Learned about it in one of my university algorithms classes, but have yet to see an implementation in practice.) https://en.wikipedia.org/wiki/Cuckoo_hashing https://en.wikipedia.org/wiki/Cuckoo_hashing

posnet 8y ago
https://blog.acolyer.org/2016/11/03/algorithmic-improvements-for-fast-concurrent-cuckoo-hashing/ https://blog.acolyer.org/2016/11/03/algorithmic-improvements... https://github.com/efficient/libcuckoo https://github.com/efficient/libcuckoo
blattimwind 8y ago
https://github.com/efficient/libcuckoo https://github.com/efficient/libcuckoo There's the related cuckoo filter as well: https://github.com/efficient/cuckoofilter https://github.com/efficient/cuckoofilter
mikeash 8y ago
I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.
- 19870213 8y ago
  The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?
  - mikeash 8y ago
    You could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions. This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.
  - rurban 8y ago
    My limit is 128. 5 is very common with a high load factor and fast hash function.
- cbhl 8y ago
  It's constant-time lookup (only two possible places to check). But if you give it the "return 4" hash function, it will fail to insert after the second or third entry. The result is the same, you have to fall back to something (changing the hash function; making the table larger; open addressing with chaining; etc.)
  - mikeash 8y ago
    That’s boring. Any algorithm can be constant time if you’re allowed to fail after a constant amount of work.
    - jolux 8y ago
      It will rebuild the hashtable when that happens. As long as the load factor remains below 50%, (for the most basic implementation) insertions will remain constant anyways. You don't need to allocate new tables.
      - mikeash 8y ago
        How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.
        jolux 8y ago
        Have you read about how the algorithm works?
        mikeash 8y ago
        A bit. When you collide in both tables, you switch to a different hash function and try again. With real-world data, that should work great. But with pathological data (i.e. the worst case behavior) that will never succeed.
    - 8y ago
jacobolus 8y ago
Here’s a practical implementation in Twitter’s cache backend, https://github.com/twitter/pelikan/tree/master/src/storage/cuckoo https://github.com/twitter/pelikan/tree/master/src/storage/c...
Diggsey 8y ago
This seems to assume that all information needed to determine if two keys are equal is incorporated into the resulting hash value. It's premised on the idea that you can dynamically change the hash function such that eventually you will find one with fewer than some fixed number of items sharing the same hash value. There are two problems: 1) It completely undermines the "worst-case constant lookup", because there is no upper bound on the number of times you might have to change the hash function and rebuild the table before you find one with sufficiently few collisions. 2) It is a much stronger requirement on the keys than other hash tables have. With other hash tables I can simply omit "difficult to hash" data from my hash function, on the basis that enough other data is hashed to avoid a significant performance penalty. With this implementation, the entire hash table will simply fail. This additional failure mode is also a security concern - if an untrusted user can affect what data is added to the table, it could cause a severe DoS where the table will either enter an infinite loop trying to find a non-conflicting hash function, or have an unexpected failure mode (most people don't expect their hash tables to randomly fail). Even if it is somehow designed such that a hash function can always be found, the attacker could spend time up-front finding values that take a long time for that hash function to be reached, causing numerous re-hashes of the table.
- lixtra 8y ago
  > a security concern - if an untrusted user can affect what data is added to the table, it could cause a severe DoS Isn’t that a general problem [1] that is addressed with randomization of the input data before hashing? [1] https://www.purehacking.com/blog/josh-zlatin/introduction-to-hash-dos-attacks https://www.purehacking.com/blog/josh-zlatin/introduction-to...
- jorangreef 8y ago
  Those are really questions and issues of implementation than of theory. 1. Tabulation hashing provides guarantees against chosen key attacks. 2. In addition, bucketized cuckoo hashing provides guarantees on the probability of resize (low compared to linear probing), and multiple resizes (very low compared to linear probing). 3. Further, most hash table implementations that I know of have layers of defense, including limiting the number of sequential resizes for a given key. Putting everything together, if anything, I would be more concerned with the failure mode for linear probing (scanning the whole table before resizing) than for Cuckoo hashing (scanning two fixed-size buckets before resizing).
jorangreef 8y ago
"If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting." The issue with memory overhead (load factor) is actually something that Cuckoo hashing solves compared to linear probing. Bucketized Cuckoo hashing supports much higher load factors than linear probing. You can have your cake and eat it too. I have implemented hash tables with open addressing and tombstones in the past (linear probing, triangular probing etc.) and I much prefer Cuckoo hashing now. When Cuckoo hashing is combined with a bloom filter in the first position to reduce cache misses to the second position, it's almost perfect in every way: fast (drastically reduced cache misses), constant lookup time in the worst case (not so for linear probing), higher load factors (80% or more for Cuckoo hashing vs at most 50% for linear probing - this also affects amortized resize latency), not to mention elegant simplicity. In case anyone is interested, here are some design details and decisions for an optimized bucketized Cuckoo hash table with bloom filters implemented for Node.js: https://github.com/ronomon/hash-table https://github.com/ronomon/hash-table
- throwaway808080 8y ago
  How does cuckoo hashing work for 80% load factor. It may be possible that you fill out both the positions and your eviction algorithm is then no longer constant time for worst case. AFAIK, cuckoo works best when load factor is less than 50%. Wikipedia seems to also agree with me.
  - laughinghan 8y ago
    Did you read the link? > Each bucket contains up to 8 elements to support a hash table load factor of 80% or higher, unlike linear or chained hash tables which support a load factor (elements / capacity) of at most 50% and which waste the other 50% of memory.

by cbhl 8y ago

posnet 8y ago

https://blog.acolyer.org/2016/11/03/algorithmic-improvements-for-fast-concurrent-cuckoo-hashing/ https://blog.acolyer.org/2016/11/03/algorithmic-improvements... https://github.com/efficient/libcuckoo https://github.com/efficient/libcuckoo

blattimwind 8y ago

https://github.com/efficient/libcuckoo https://github.com/efficient/libcuckoo There's the related cuckoo filter as well: https://github.com/efficient/cuckoofilter https://github.com/efficient/cuckoofilter

mikeash 8y ago

I assume that’s constant lookup time assuming well distributed hash values? The absolute worst case for a hash table is when every key has the same hash, and then you must fall back to something that’s at best log-n time.

19870213 8y ago
The standard Java java.util.HashMap currently falls back to a Tree(Map) if a bucket gets too full (more than 5? Not sure, a LinkedList if not too full). But I wonder, couldn't you not use a different hash and have use a HashMap as a bucket?
- mikeash 8y ago
  You could, but it’s theoretically possible to have keys whose hashes always collide, even with different hash functions. This is not a purely theoretical concern, I should note. There are practical DoS attacks that can be carried out by deliberately crafting colliding keys. The current state of the art seems to be to make it impractical for attackers to accomplish this by incorporating secret data into the hash function, rather than by ensuring the theoretical worst case is acceptable. Which is probably the right approach.
- rurban 8y ago
  My limit is 128. 5 is very common with a high load factor and fast hash function.
cbhl 8y ago
It's constant-time lookup (only two possible places to check). But if you give it the "return 4" hash function, it will fail to insert after the second or third entry. The result is the same, you have to fall back to something (changing the hash function; making the table larger; open addressing with chaining; etc.)
- mikeash 8y ago
  That’s boring. Any algorithm can be constant time if you’re allowed to fail after a constant amount of work.
  - jolux 8y ago
    It will rebuild the hashtable when that happens. As long as the load factor remains below 50%, (for the most basic implementation) insertions will remain constant anyways. You don't need to allocate new tables.
    - mikeash 8y ago
      How is that possible? I insert three pathological keys. The third one collides with both, so it rebuilds the table. The third one still collides with both, so it rebuilds the table again. Repeat. Eventually either we fail or we end up in something that’s worse than constant time.
      - jolux 8y ago
        Have you read about how the algorithm works?
        mikeash 8y ago
        A bit. When you collide in both tables, you switch to a different hash function and try again. With real-world data, that should work great. But with pathological data (i.e. the worst case behavior) that will never succeed.
  - 8y ago

jacobolus 8y ago

Here’s a practical implementation in Twitter’s cache backend, https://github.com/twitter/pelikan/tree/master/src/storage/cuckoo https://github.com/twitter/pelikan/tree/master/src/storage/c...

Diggsey 8y ago

This seems to assume that all information needed to determine if two keys are equal is incorporated into the resulting hash value. It's premised on the idea that you can dynamically change the hash function such that eventually you will find one with fewer than some fixed number of items sharing the same hash value. There are two problems: 1) It completely undermines the "worst-case constant lookup", because there is no upper bound on the number of times you might have to change the hash function and rebuild the table before you find one with sufficiently few collisions. 2) It is a much stronger requirement on the keys than other hash tables have. With other hash tables I can simply omit "difficult to hash" data from my hash function, on the basis that enough other data is hashed to avoid a significant performance penalty. With this implementation, the entire hash table will simply fail. This additional failure mode is also a security concern - if an untrusted user can affect what data is added to the table, it could cause a severe DoS where the table will either enter an infinite loop trying to find a non-conflicting hash function, or have an unexpected failure mode (most people don't expect their hash tables to randomly fail). Even if it is somehow designed such that a hash function can always be found, the attacker could spend time up-front finding values that take a long time for that hash function to be reached, causing numerous re-hashes of the table.

lixtra 8y ago
> a security concern - if an untrusted user can affect what data is added to the table, it could cause a severe DoS Isn’t that a general problem [1] that is addressed with randomization of the input data before hashing? [1] https://www.purehacking.com/blog/josh-zlatin/introduction-to-hash-dos-attacks https://www.purehacking.com/blog/josh-zlatin/introduction-to...
jorangreef 8y ago
Those are really questions and issues of implementation than of theory. 1. Tabulation hashing provides guarantees against chosen key attacks. 2. In addition, bucketized cuckoo hashing provides guarantees on the probability of resize (low compared to linear probing), and multiple resizes (very low compared to linear probing). 3. Further, most hash table implementations that I know of have layers of defense, including limiting the number of sequential resizes for a given key. Putting everything together, if anything, I would be more concerned with the failure mode for linear probing (scanning the whole table before resizing) than for Cuckoo hashing (scanning two fixed-size buckets before resizing).

jorangreef 8y ago

"If memory overhead (load factor) isn't a big issue, readers may also find cuckoo hashing rather interesting." The issue with memory overhead (load factor) is actually something that Cuckoo hashing solves compared to linear probing. Bucketized Cuckoo hashing supports much higher load factors than linear probing. You can have your cake and eat it too. I have implemented hash tables with open addressing and tombstones in the past (linear probing, triangular probing etc.) and I much prefer Cuckoo hashing now. When Cuckoo hashing is combined with a bloom filter in the first position to reduce cache misses to the second position, it's almost perfect in every way: fast (drastically reduced cache misses), constant lookup time in the worst case (not so for linear probing), higher load factors (80% or more for Cuckoo hashing vs at most 50% for linear probing - this also affects amortized resize latency), not to mention elegant simplicity. In case anyone is interested, here are some design details and decisions for an optimized bucketized Cuckoo hash table with bloom filters implemented for Node.js: https://github.com/ronomon/hash-table https://github.com/ronomon/hash-table

throwaway808080 8y ago
How does cuckoo hashing work for 80% load factor. It may be possible that you fill out both the positions and your eviction algorithm is then no longer constant time for worst case. AFAIK, cuckoo works best when load factor is less than 50%. Wikipedia seems to also agree with me.
- laughinghan 8y ago
  Did you read the link? > Each bucket contains up to 8 elements to support a hash table load factor of 80% or higher, unlike linear or chained hash tables which support a load factor (elements / capacity) of at most 50% and which waste the other 50% of memory.