4 ms·

Interesting. AFAICT, Cuckoo hashing: 0) Cuckoo hashing is much simpler to implement (correctly). 1) look up and delete is also O(1), but Cuckoo is faster (esp

Interesting. AFAICT, Cuckoo hashing: 0) Cuckoo hashing is much simpler to implement (correctly). 1) look up and delete is also O(1), but Cuckoo is faster (especially if you can exploit the inherent parallelism in the two table probes). 2) insert for Cuckoo is O(1) amortized. It's unclear how this compares. 3) Cuckoo can mix and match insert, delete, lookup ops. 4) Cuckoo uses more memory (as the OP is per definition minimal). Someone please correct me if I'm wrong, but I think Cuckoo looks pretty favorable to this for most usage. EDIT: formatting.

mtdewcmu 11y ago
This is an offline algorithm. Take a look at GNU gperf[1]. [1]https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/
beagle3 11y ago
Cuckoo's insert is, in fact, hard to implement correctly. Every implementation I looked at was vulnerable to "chosen key" attack which made it either O(n) or worse -- run into an infinite loop or fail to insert.
- FullyFunctional 11y ago
  Good point. Isn't this a problem with the hash functions exclusively? Can't you avoid this by picking the two hashing functions at random every time you rehash? (I acknowledge that my original comment was misplaced given the off-/on-line difference).
  - beagle3 11y ago
    You can if you're just avoiding bad luck; You often cannot if you're avoiding an active opponent - in which case, your random would need to be cryptographically secure AND not leak any data through timing or other ways. Here's an observation: Quicksort is similarly vulnerable to an active attacker[0], and can similarly be "protected" with random pivot selection. How many quicksort implementations have you seen in production quality libraries that actually have a random pivot selection? I have seen none. As a result, I avoid quicksort (and cuckoo, and any other basic algorithm which depends on good crypto to perform well). [0] I'm not referring to McIlroy's "antiquicksort" here, which makes quicksort O(n^2) even in the presence of completely unpredictable pivot selection -- I'm assuming the data to be sorted is laid out before the sorting starts.

mtdewcmu 11y ago

This is an offline algorithm. Take a look at GNU gperf[1]. [1]https://www.gnu.org/software/gperf/ https://www.gnu.org/software/gperf/

beagle3 11y ago

Cuckoo's insert is, in fact, hard to implement correctly. Every implementation I looked at was vulnerable to "chosen key" attack which made it either O(n) or worse -- run into an infinite loop or fail to insert.

FullyFunctional 11y ago
Good point. Isn't this a problem with the hash functions exclusively? Can't you avoid this by picking the two hashing functions at random every time you rehash? (I acknowledge that my original comment was misplaced given the off-/on-line difference).
- beagle3 11y ago
  You can if you're just avoiding bad luck; You often cannot if you're avoiding an active opponent - in which case, your random would need to be cryptographically secure AND not leak any data through timing or other ways. Here's an observation: Quicksort is similarly vulnerable to an active attacker[0], and can similarly be "protected" with random pivot selection. How many quicksort implementations have you seen in production quality libraries that actually have a random pivot selection? I have seen none. As a result, I avoid quicksort (and cuckoo, and any other basic algorithm which depends on good crypto to perform well). [0] I'm not referring to McIlroy's "antiquicksort" here, which makes quicksort O(n^2) even in the presence of completely unpredictable pivot selection -- I'm assuming the data to be sorted is laid out before the sorting starts.