6 ms·

It wasn't clear to me how Cuckoo hash tables are supposed to work if both locations are full. Here is the relevant explanation from Wikipedia : > The new key

It wasn't clear to me how Cuckoo hash tables are supposed to work if both locations are full. Here is the relevant explanation from Wikipedia : > The new key is inserted in one of its two possible locations, "kicking out", that is, displacing, any key that might already reside in this location. This displaced key is then inserted in its alternative location, again kicking out any key that might reside there. The process continues in the same way until an empty position is found, completing the algorithm. However, it is possible for this insertion process to fail, by entering an infinite loop or by finding a very long chain (longer than a preset threshold that is logarithmic in the table size). In this case, the hash table is rebuilt in-place using new hash functions https://en.wikipedia.org/wiki/Cuckoo_hashing#Operation https://en.wikipedia.org/wiki/Cuckoo_hashing#Operation Sound like with high occupancy the table would need to be rebuilt constantly.

TimonKnigge 5y ago
In the linked article they resolve collisions via chaining: > A typical hash function distributes keys randomly across the slots in a hash table, causing some slots to be empty, while others have collisions, which require some form of chaining of items I.e. each field in the table is a linked list of values that hash to this position, and the new value is inserted in the shortest of the two lists it hashes to.
- eutectic 5y ago
  No, chaining is presented as an alternative to Cuckoo hashing.
toxik 5y ago
Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.
- j-pb 5y ago
  Since you double the table size after failing to insert/displace above a constant threshhold, e.g. 8. You have O(1) insert performance. You don't need to rehash the table either, you can add additional hash functions on each grow, or reuse your existing hash function and use bit masking, (that one does require a copy of the table, albeit no rehashing, and copying chunks is something our CPUs are really good at)
- adrianN 5y ago
  Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.
  - toxik 5y ago
    They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.
    - touisteur 5y ago
      Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.
      - karpierz 5y ago
        Mergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.
        touisteur 5y ago
        Which is where you get problematic tail latencies. Or your data fits on the stack.
      - phkahler 5y ago
        Heapsort is O(n * Log(n)) worst case. It is also O(n * Log(n)) in most cases, including already sorted data. Most implementations also seem to have a slightly larger constant factor than quicksort, but I think that's largely due to implementation details (one should not actually swap values that are likely to be immediately swapped again). Which one is right really does come down to a decision based on how much you care about Typical/Average/WorstCase time complexity and the actual size of your data set.
- nullc 5y ago
  A below transition fullness the insertion process takes N kicks with exponentially decreasing probability (for some constants depending on the fullness level and number of hash functions). E.g. 1/2^n kicks. Not something you can really describe as wildly erratic. If latency is particularly critical in your application, you could couple the hash table with a small "stash" map and perform a constant maximum number of kicks per insert, and when you reach the limit stick the current straggler in the map to be continued on the next insertion. As long as the constant maximum is well above the average the map will stay empty most of the time.
  - toxik 5y ago
    The fact that you're talking about probabilities sort of proves my point. You're instead saying it could be worse, and I'm saying random execution times in your critical paths is generally undesirable. It depends on your application of course, but if you have anything realtime or near realtime, I would definitely take consistent execution times. There is a related e-mail from IdSoft's John Carmack about this at [1] which I found very interesting. [1] http://number-none.com/blow/blog/programming/2014/09/26/carmack-on-inlined-code.html http://number-none.com/blow/blog/programming/2014/09/26/carm...
    - nullc 5y ago
      There are 'random' execution times in the critical paths of essentially everything on a modern general purpose computer, unfortunately. What matters for realtime operation is that the worst case is bounded and that the bound is acceptable.

TimonKnigge 5y ago

In the linked article they resolve collisions via chaining: > A typical hash function distributes keys randomly across the slots in a hash table, causing some slots to be empty, while others have collisions, which require some form of chaining of items I.e. each field in the table is a linked list of values that hash to this position, and the new value is inserted in the shortest of the two lists it hashes to.

eutectic 5y ago
No, chaining is presented as an alternative to Cuckoo hashing.

toxik 5y ago

Ah, O(wildly erratic) insertion. Great for that jittery feel to your programs.

j-pb 5y ago
Since you double the table size after failing to insert/displace above a constant threshhold, e.g. 8. You have O(1) insert performance. You don't need to rehash the table either, you can add additional hash functions on each grow, or reuse your existing hash function and use bit masking, (that one does require a copy of the table, albeit no rehashing, and copying chunks is something our CPUs are really good at)
adrianN 5y ago
Most popular data structures only provide average case guarantees with bad worst-case bounds. Dynamic arrays also have O(wildly erratic) append. I think for most use cases this is perfectly fine and does not result in any perceivable jitter in programs.
- toxik 5y ago
  They do in fact not have erratic behavior, they are quite predictable. The cuckooing process, on the other hand, is not predictable by design.
  - touisteur 5y ago
    Recently went on a deep dive about sorting algorithm actual predictability and for latency-sensitive workloads, most things you'd use because 'simple/standard' (quicksort, mergesort...) don't shine, with their horrid /worst case/ complexity, but also depending a lot on your input data. Quicksort with a badly chosen pivot, for example, has caused me headaches recently.
    - karpierz 5y ago
      Mergesort worst case is O(nlog(n)). If there's a downside to it, it's that you need to allocate memory.
      - touisteur 5y ago
        Which is where you get problematic tail latencies. Or your data fits on the stack.
    - phkahler 5y ago
      Heapsort is O(n * Log(n)) worst case. It is also O(n * Log(n)) in most cases, including already sorted data. Most implementations also seem to have a slightly larger constant factor than quicksort, but I think that's largely due to implementation details (one should not actually swap values that are likely to be immediately swapped again). Which one is right really does come down to a decision based on how much you care about Typical/Average/WorstCase time complexity and the actual size of your data set.
nullc 5y ago
A below transition fullness the insertion process takes N kicks with exponentially decreasing probability (for some constants depending on the fullness level and number of hash functions). E.g. 1/2^n kicks. Not something you can really describe as wildly erratic. If latency is particularly critical in your application, you could couple the hash table with a small "stash" map and perform a constant maximum number of kicks per insert, and when you reach the limit stick the current straggler in the map to be continued on the next insertion. As long as the constant maximum is well above the average the map will stay empty most of the time.
- toxik 5y ago
  The fact that you're talking about probabilities sort of proves my point. You're instead saying it could be worse, and I'm saying random execution times in your critical paths is generally undesirable. It depends on your application of course, but if you have anything realtime or near realtime, I would definitely take consistent execution times. There is a related e-mail from IdSoft's John Carmack about this at [1] which I found very interesting. [1] http://number-none.com/blow/blog/programming/2014/09/26/carmack-on-inlined-code.html http://number-none.com/blow/blog/programming/2014/09/26/carm...
  - nullc 5y ago
    There are 'random' execution times in the critical paths of essentially everything on a modern general purpose computer, unfortunately. What matters for realtime operation is that the worst case is bounded and that the bound is acceptable.