3 ms·
The main case that I know of where you really don't want to use open addressing (using tombstones) is when you have both of the following requirements: a) need
by usefulcat 8y ago
The main case that I know of where you really don't want to use open addressing (using tombstones) is when you have both of the following requirements: a) need to repeatedly insert and delete items, and b) can't tolerate (relatively) really bad worst case insertion performance.
I can't speak directly to the performance of non-tombstone based open addressing implementations, but it definitely seems like the need to move things around after deletions would be significantly more work than the fastest chaining implementation I've come up with.
- ngbronson 8y agoIf there is metadata available at every slot then you can track overflows rather than tombstones. These let you terminate the search earlier (you don't need to find an empty) and can be cleaned up on erase, because they are a property of the keys in the map rather than the keys that are no longer in the map. folly's F14 maps use this strategy, and handle erase + insert workloads fine with no rehashing needed. https://github.com/facebook/folly/blob/master/folly/container/F14.md#chunk-overflow-counts-reference-counted-tombstones https://github.com/facebook/folly/blob/master/folly/containe...