3 ms·
The post mentions using tombstones for deletion, but I was under the impression that the variance benefits of Robin Hood hashing weren't realized unless you per
by Bognar 10y ago
The post mentions using tombstones for deletion, but I was under the impression that the variance benefits of Robin Hood hashing weren't realized unless you performed a backwards shift on the remaining elements instead of using a tombstone.
See these posts for more information:
http://codecapsule.com/2013/11/11/robin-hood-hashing/ http://codecapsule.com/2013/11/11/robin-hood-hashing/
http://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ http://codecapsule.com/2013/11/17/robin-hood-hashing-backwar...
Unfortunately there's not great information around the overall CPU performance impact of using a shift vs. tombstone.
- mcguire 10y agoI don't know the actual performance impact, but using backwards shifts and removing tombstones leaves the code much simpler. https://github.com/tmmcguire/rust-toys/blob/master/pony/anagrams/robinhood.pony https://github.com/tmmcguire/rust-toys/blob/master/pony/anag...
- scythe 10y agoI think you can obtain the same variance benefits if you delay the backwards shift until you insert into a tombstone bucket. In that case you backwards shift until the "new" element has a higher DIB than all of the "promoted" ones, or an empty bucket is reached, or a DIB zero bucket is reached. Of course you're not really saving much actual computation this way (you do save a little, since you avoid situations where an element is back-shifted and immediately front-shifted), just moving it around. (I'm not sure why fast deletions are necessary in the first place?)