7 ms·
You skipped hs_remove but depending on implementation, hs_remove strategy may change your hs_set, e.g using tombstones. I’ve recently learnt that you don’t need
by tirrex 6y ago
You skipped hs_remove but depending on implementation, hs_remove strategy may change your hs_set, e.g using tombstones. I’ve recently learnt that you don’t need tombstones at all in linear hashmaps, you just do backshift removals, it may be a simple addition to your map. Check out these repos for the example implementation:
(C) https://github.com/tezc/sc/tree/master/map https://github.com/tezc/sc/tree/master/map
(C++) https://github.com/rigtorp/HashMap https://github.com/rigtorp/HashMap
- speps 6y agoA more detailed explanation of "backward shift deletion": https://codecapsule.com/2013/11/17/robin-hood-hashing-backward-shift-deletion/ https://codecapsule.com/2013/11/17/robin-hood-hashing-backwa...
- chrchang523 6y agoWell, he did say "simple hash table". In my experience, many applications have no need for single-element deletion.
- attractivechaos 6y agoI wrote a blog post [1] on this a couple of years ago. This is a quite old technique [2] but was not widely used until recently. I was surprised that I hadn't found this earlier. [1] https://attractivechaos.wordpress.com/2019/12/28/deletion-from-hash-tables-without-tombstones/ https://attractivechaos.wordpress.com/2019/12/28/deletion-fr... [2] https://en.wikipedia.org/wiki/Linear_probing#Deletion https://en.wikipedia.org/wiki/Linear_probing#Deletion
- tirrex 6y agoI can’t find right now but I saw one older version of wiki page, it had C code example how to do deletion with this. This is how I discovered it. I knew your blog but apperantly I didn’t visit recently. > I think the new deletion algorithm without tombstones is overall better than traditional algorithms. It should become the preferred way to implement hash tables I agree with you 100%. Tombstone has no advantage over this.
- annilt 6y agohttps://en.wikipedia.org/wiki/Open_addressing https://en.wikipedia.org/wiki/Open_addressing Maybe it was open addressing page? It has pseudo code for that.
- bjourne 6y agoThe advantage of tombstones is that it is dead simple to implement. Backshift removals can cause a lot of memory shuffling if you are removing an element from a very congested part of the hash table.
- tirrex 6y agoIf you are using load factor around %75, it means you’ll do 3 shifts at most. On average it is less than it as you are ordering your map on each removal and only case you’ll do backshifts when your items are “not ordered according to hash function”. Tombstones are silly, you do add/remove %75 of your map capacity, now you have to rehash your map even your map is empty. I can’t think a single scenario that tombstones can perform better. It causes much more probing and much more cache misses than backshift deletion.
- attractivechaos 6y agoBackshift has two potential disadvantages: 1) copying objects may be slower than testing equality (case dependent); 2) each deletion involves the entire probe chain (with tombstone, you inspect half of the probe chain in average). On the other hand, with tombstone, each probe chain is longer. This slows down searching and insertion as well as deletion. Tombstones also increase the frequency of rehashing. > The advantage of tombstones is that it is dead simple to implement. Backshift is harder to understand but it actually takes fewer LOC to implement at my hand. That is because insertion and searching become simpler (and slightly faster) with backshift. > Backshift removals can cause a lot of memory shuffling Not sure what you mean by memory shuffling. Backshift is applied to linear probing only. You don't jump around except when you wrap around the end of the bucket array, which is rare.
- bjourne 6y ago
- benhoyt 6y agoThanks for this (and parent reply for mentioning it), that's simple and clever! > The basic idea is not complex: when we delete an element, we move the next element to the deleted location if it is pushed away by the deleted element due to hash collision; we repeat this process until we come to an empty bucket. I wonder, is it still amortized constant time? My gut (which is not very good at computer science) tells me that it still may be, as with an average probe length of ~1.4 (which I was seeing), you won't have to walk more than 1 or 2 elements on average.
- hnfong 6y agoIt shouldn't take more operations (asymptotically) to delete than to probe/insert so as long as the original list is still amortized constant time then the delete operation still is.
- deleted 6y ago[deleted]
- nwallin 6y agoSurely this is an older technique? When I took data structures in college I implemented deletions that way, because I wasn't smart enough to invent tombstones. Looking through the wikipedia history, the sketch of it wasn't added yet. I had wanted to use "better" techniques like quadratic probing, but I couldn't figure out how to perform deletions, so I fell back on linear probing.