4 ms·

I don't see a compelling reason to use tombstones in linear probing except in a concurrent context (where you can't move entries around). The tombstone-free del

I don't see a compelling reason to use tombstones in linear probing except in a concurrent context (where you can't move entries around). The tombstone-free deletion algorithm is quite simple: https://github.com/senderista/hashtable-benchmarks/blob/master/src/main/java/set/int64/LPLongHashSet.java#L184 https://github.com/senderista/hashtable-benchmarks/blob/mast.... No rehashing is necessary.

celeritascelery 3y ago
This is a really cool approach! But if it so obvious, why doesn't every hashmap use it? It seems like there are some trade-offs here that I must be missing.
- Leszek 3y ago
  If you do any kind of probing other than linear probing (e.g. quadratic probing) this approach doesn't work anymore, because your collisions are no longer densely grouped together.
- senderista 3y ago
  The main tradeoff is concurrency: it's difficult to safely read a hash table while its entries are being concurrently relocated. Another tradeoff is (probably) higher average latency (but worst-case latency is much better since there's no global rehashing required).
adgjlsfhk1 3y ago
imo a pretty good approach is tombstones where you delete trailing tombstones. that way the tombstones can't overly clog the dictionary but never have to move live objects
- senderista 3y ago
  Here is a simple heuristic for avoiding most tombstones when the load factor isn't too high: https://arxiv.org/pdf/1808.04602.pdf https://arxiv.org/pdf/1808.04602.pdf
JacksonAllan 3y ago
findPreferredBucket rehashes. The problem with this deletion algorithm is that every element that is a candidate for back-shifting must be rehashed to ensure that we don't shift it back beyond its home bucket (unlike in Robin Hood probing, where probe lengths already give us this information). Hence, it is pretty unsuitable when the hash function is expensive, unless we're storing hash codes or keeping the load factor very low. This image - https://ibb.co/xSytxHF https://ibb.co/xSytxHF - shows a benchmark of a few hash tables with string keys and a maximum load factor of 0.95. Guess which one is using linear probing with back-shift deletion.
- senderista 3y ago
  Recalculating the hash codes is indeed potentially expensive. In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible), so the hash function never needs to be recalculated (just the preferred bucket based on the hash, which is extremely cheap). With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate.
  - JacksonAllan 3y ago
    In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible) Oh, I see, right. If determining the home bucket is trivial, then the back-shifting method is great. The issue is just that it’s not as much of a general-purpose solution as it may initially seem. In the bad cases, it's really bad. With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate. I’ve seen the 90% claim made several times in literature on Robin Hood hash tables. In my experience, the claim is a bit exaggerated, although I suppose it depends on what our idea of “good performance” is. See these benchmarks, which again go up to a maximum load factor of 0.95 (although boost and Absl forcibly grow/rehash at 0.85-0.9): https://strong-starlight-4ea0ed.netlify.app/ https://strong-starlight-4ea0ed.netlify.app/ Tsl, Martinus, and CC are all Robin Hood tables (https://github.com/Tessil/robin-map https://github.com/Tessil/robin-map, https://github.com/martinus/robin-hood-hashing https://github.com/martinus/robin-hood-hashing, and https://github.com/JacksonAllan/CC https://github.com/JacksonAllan/CC, respectively). Absl (from Google) and Boost are well-known C++ SIMD-based hash tables. Khash (https://github.com/attractivechaos/klib/blob/master/khash.h https://github.com/attractivechaos/klib/blob/master/khash.h) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell (https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ) but also incorporates some aspects of the aforementioned SIMD maps (in particular, it stores a 4-bit fragment of the hash code to avoid most false key comparisons). As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high, becoming as much as 5-6 times slower at 0.95 vs 0.5 in one of the benchmarks (uint64_t key, 256-bit struct value: Total time to erase 1000 existing elements with N elements in map). Only the SIMD maps (with Boost being the clear better performer of the two) and Fastmap appear mostly immune to load factor in all benchmarks, although the SIMD maps do - I believe - use tombstones for deletion in at least some cases. I’ve only read briefly about bi-directional linear probing – never experimented with it.
teo_zero 3y ago
May I ask why you decided to store the hash instead of the element?
- senderista 3y ago
  Two reasons: 1. I never need to recalculate the hash in order to find the preferred bucket. 2. The BLP invariant is that entries are strictly ordered by hash code (Robin Hood can actually be reformulated in terms of the same invariant, but it's less efficient because entries with the same preferred bucket can only reside at or after that bucket rather than before, at, or after it). This allows you to view a hash table as just a sorted array with gaps, and hash table lookup as interpolation search.
  - teo_zero 3y ago
    I assume you do a lot of deletions for 1. to be significant. On the other hand, you restrict yourself to a specific class of hashes: reversible and bijective (and never producing a zero for a valid input, although I think this is just how this particular table is built and can be easily changed). This a severe limitation to ever store any data other than integers, e.g. strings. I'm not criticizing. I've never implemented a hash table myself and want to learn. I'm just trying to understand what's the trade off you considered that I don't see.
    - senderista 3y ago
      Using a reversible hash function to store encoded keys is certainly a domain-specific optimization, but integer keys are so common that I don't understand why I don't see this optimization more often. For non-integer keys, you can just store truncated hash codes to eliminate hash function calls in most cases (note that the hash value is needed both to calculate the preferred bucket and to determine the order of entries in that bucket). The smaller the table, the smaller the truncated hash codes can be. When you resize the table, you can increase the truncated hash code size if necessary (one bit for each doubling, which you can amortize by adding a byte every 8 doublings). This of course requires rehashing all keys, but conventional hash tables already rehash all keys on resizing.

celeritascelery 3y ago

This is a really cool approach! But if it so obvious, why doesn't every hashmap use it? It seems like there are some trade-offs here that I must be missing.

Leszek 3y ago
If you do any kind of probing other than linear probing (e.g. quadratic probing) this approach doesn't work anymore, because your collisions are no longer densely grouped together.
senderista 3y ago
The main tradeoff is concurrency: it's difficult to safely read a hash table while its entries are being concurrently relocated. Another tradeoff is (probably) higher average latency (but worst-case latency is much better since there's no global rehashing required).

adgjlsfhk1 3y ago

imo a pretty good approach is tombstones where you delete trailing tombstones. that way the tombstones can't overly clog the dictionary but never have to move live objects

senderista 3y ago
Here is a simple heuristic for avoiding most tombstones when the load factor isn't too high: https://arxiv.org/pdf/1808.04602.pdf https://arxiv.org/pdf/1808.04602.pdf

JacksonAllan 3y ago

findPreferredBucket rehashes. The problem with this deletion algorithm is that every element that is a candidate for back-shifting must be rehashed to ensure that we don't shift it back beyond its home bucket (unlike in Robin Hood probing, where probe lengths already give us this information). Hence, it is pretty unsuitable when the hash function is expensive, unless we're storing hash codes or keeping the load factor very low. This image - https://ibb.co/xSytxHF https://ibb.co/xSytxHF - shows a benchmark of a few hash tables with string keys and a maximum load factor of 0.95. Guess which one is using linear probing with back-shift deletion.

senderista 3y ago
Recalculating the hash codes is indeed potentially expensive. In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible), so the hash function never needs to be recalculated (just the preferred bucket based on the hash, which is extremely cheap). With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate.
- JacksonAllan 3y ago
  In my example the table stores the hash codes themselves instead of the keys (because the hash function is invertible) Oh, I see, right. If determining the home bucket is trivial, then the back-shifting method is great. The issue is just that it’s not as much of a general-purpose solution as it may initially seem. In the bad cases, it's really bad. With a different algorithm (Robin Hood or bidirectional linear probing), the load factor can be kept well over 90% with good performance, as the benchmarks in the same repo demonstrate. I’ve seen the 90% claim made several times in literature on Robin Hood hash tables. In my experience, the claim is a bit exaggerated, although I suppose it depends on what our idea of “good performance” is. See these benchmarks, which again go up to a maximum load factor of 0.95 (although boost and Absl forcibly grow/rehash at 0.85-0.9): https://strong-starlight-4ea0ed.netlify.app/ https://strong-starlight-4ea0ed.netlify.app/ Tsl, Martinus, and CC are all Robin Hood tables (https://github.com/Tessil/robin-map https://github.com/Tessil/robin-map, https://github.com/martinus/robin-hood-hashing https://github.com/martinus/robin-hood-hashing, and https://github.com/JacksonAllan/CC https://github.com/JacksonAllan/CC, respectively). Absl (from Google) and Boost are well-known C++ SIMD-based hash tables. Khash (https://github.com/attractivechaos/klib/blob/master/khash.h https://github.com/attractivechaos/klib/blob/master/khash.h) is, I think, an ordinary open-addressing table using quadratic probing. Fastmap is a new, yet-to-be-published design that is fundamentally similar to bytell (https://www.youtube.com/watch?v=M2fKMP47slQ https://www.youtube.com/watch?v=M2fKMP47slQ) but also incorporates some aspects of the aforementioned SIMD maps (in particular, it stores a 4-bit fragment of the hash code to avoid most false key comparisons). As you can see, all the Robin Hood maps spike upwards dramatically as the load factor gets high, becoming as much as 5-6 times slower at 0.95 vs 0.5 in one of the benchmarks (uint64_t key, 256-bit struct value: Total time to erase 1000 existing elements with N elements in map). Only the SIMD maps (with Boost being the clear better performer of the two) and Fastmap appear mostly immune to load factor in all benchmarks, although the SIMD maps do - I believe - use tombstones for deletion in at least some cases. I’ve only read briefly about bi-directional linear probing – never experimented with it.

teo_zero 3y ago

May I ask why you decided to store the hash instead of the element?

senderista 3y ago
Two reasons: 1. I never need to recalculate the hash in order to find the preferred bucket. 2. The BLP invariant is that entries are strictly ordered by hash code (Robin Hood can actually be reformulated in terms of the same invariant, but it's less efficient because entries with the same preferred bucket can only reside at or after that bucket rather than before, at, or after it). This allows you to view a hash table as just a sorted array with gaps, and hash table lookup as interpolation search.
- teo_zero 3y ago
  I assume you do a lot of deletions for 1. to be significant. On the other hand, you restrict yourself to a specific class of hashes: reversible and bijective (and never producing a zero for a valid input, although I think this is just how this particular table is built and can be easily changed). This a severe limitation to ever store any data other than integers, e.g. strings. I'm not criticizing. I've never implemented a hash table myself and want to learn. I'm just trying to understand what's the trade off you considered that I don't see.
  - senderista 3y ago
    Using a reversible hash function to store encoded keys is certainly a domain-specific optimization, but integer keys are so common that I don't understand why I don't see this optimization more often. For non-integer keys, you can just store truncated hash codes to eliminate hash function calls in most cases (note that the hash value is needed both to calculate the preferred bucket and to determine the order of entries in that bucket). The smaller the table, the smaller the truncated hash codes can be. When you resize the table, you can increase the truncated hash code size if necessary (one bit for each doubling, which you can amortize by adding a byte every 8 doublings). This of course requires rehashing all keys, but conventional hash tables already rehash all keys on resizing.