4 ms·
Following the link to the cuckoo hasing algorithm on Wikipedia, I don't quite understand what it's doing. I looked up another couple articles but still find my
by maxk42 3y ago
Following the link to the cuckoo hasing algorithm on Wikipedia, I don't quite understand what it's doing. I looked up another couple articles but still find myself confused. Does anyone have a link to a resource with an easy-to-follow writeup of how cuckoo hashing works?
- bhawks 3y agoI found this pretty clear and it includes an interactive visualization: https://www.lkozma.net/cuckoo_hashing_visualization/ https://www.lkozma.net/cuckoo_hashing_visualization/
- CBLT 3y agoI understood it from this HN comment: https://news.ycombinator.com/item?id=8491456 https://news.ycombinator.com/item?id=8491456
- lelandfe 3y agoRecommendation: once you do grok it, see if you can update the intro on the Wikipedia article to help others out :)
- Groxx 3y agoHash collisions happen. What do you do with them? Chained (aka open hashing) hashtables store pointers rather than values in the "main" array, and just put collisions in a linked list on that hash cell. Easy, but indirections have a cost. Closed hashing (aka open addressing, yes it's confusing) hashtables take hash(input) and just do it again to get a second location, and put it there. Repeat N times for N hash(hash(hash(...))) collisions. Dense, but needs more complex logic to figure out when to stop looking / what to do when deleting because anything could be at location X due to a collision with something else. Cuckoo hashtables use two (or more) hash algorithms rather than one, and dedicate a portion of the memory to each algorithm. If something's already in the first algorithm's location, put the thing it's colliding with in that thing's second location. On read, check both locations. Dense, relatively simple for both insert and deletion, and tolerant of a few collisions with low cost. (cuckoo hashtables are a form of closed hashing / open addressing, because they keep all the data within the data-sized arrays, not storing extra info. and all of these are over-generalizing / there are fairly different-looking strategies available, e.g. it's not necessarily pointers or strictly repeated hashing) And you could just reject the existence of collisions entirely and move to a new, larger array immediately. That tends to perform so poorly in both cpu and memory that nothing really does it in practice, but it is technically an option.
- thomasahle 3y ago> Closed hashing (aka open addressing, yes it's confusing) hashtables take hash(input) and just do it again to get a second location, and put it there. Repeat N times for N hash(hash(hash(...))) collisions. Dense, but needs more complex logic to figure out when to stop looking / what to do when deleting because anything could be at location X due to a collision with something else. That's not really the common way to do open addressing [1]. Normally you either use (1) linear probing, where you look at `h(input)`, then `h(input)+1`, ... and so on. This is nice because of data locality. Though you need a good hash function for it to work well. Or (2) Double hashing, where you first look at `h_1(input)` then `h_1(input) + h_2(input)` then `h_1(input) + 2*h_2(input)` and so on. I'm not saying repeatedly hashing `hash(hash(hash(...)))` doesn't work, but it's more expensive to call the hash function so many times. [1]: https://en.wikipedia.org/wiki/Open_addressing https://en.wikipedia.org/wiki/Open_addressing
- Groxx 3y agoyea, I should probably use the "you just take the value and push it over there (idx+1)!" as an intro, it's a simpler concept too. thanks!