Open addressing has better cache performance, and for most workloads is much faster than chaining implementations. Hashbrown's implementation is based on Google's SwissTable, and they explained the reasoning behind their choices in this CppCon talk: https://www.youtube.com/watch?v=ncHmEUmJZf4

Cliff Click (of JVM fame) did a presentation once on an open addressing hash table implementation that he believed was lock free (it used CAS and possibly some memory barriers). I wouldn't want to argue with Cliff Click on concurrency but everybody makes mistakes. I haven't checked back if anyone found any bugs yet.

I'm also curious if or how that implementation would translate to other languages. What he did might not be declarable in the Rust ownership model.

How does open addressing handle deletions? I never figured this out.

Update: So I just read the article (I didn't have the chance earlier) and I see it explains tombstones, which seem like a pretty clever solution I wasn't thinking about. What I had been confused about, though was the other more-obvious attempt at a solution, which is backshifting. I think I had gotten stuck is what you do with the spot that opens up after the backshift... it might have been part of another probe chain (or multiple, for that matter) that had jumped over it before, so how do you find one of these chains to move back an item into this slot (which you would have to do)?

The article mentions a couple of options, one of which is tombstones. In a chaining implementation, the load factor is straightforward: num_items / table_size. Adding items increases the load factor and deleting items reduces it.

With open addressing, deletions do not decrease the load factor (at least not immediately, in general), because a deleted item becomes a tombstone. So for open addressing, load factor is (num_items + num_tombstones) / table_size.

The upshot is that in a scenario where items are being repeatedly added and removed, over time the load factor will gradually increase until eventually the table has be recreated. This is true even if the average number of items remains relatively constant over time, and is unlike a chaining implementation.

In this scenario, the average insertion time might be lower with open addressing, but the worst case will be much worse than for chaining.

You can eliminate tombstones over time by:

  # any time a tombstone immediately preceeds a empty, it can be marked empty
  [ $ _ ] -> [ _ _ ]
  # any time you lookup a key, it can be swapped with a tombstone immediately preceeding it
  [ $ A ] -> [ A $ ]
  # (moving the tombstone closer to a empty that will destroy it)
  # if you don't have iterators, you can also jump over other keys
  [ $ B A ] -> [ A B $ ]
  [ $ B C A ] -> [ A B C $ ]  # etc
  # (this will cause a iterator at A to yield B again, or at B to skip A)

How well this keeps the load factor down depends on how aggressively you look for tombstone disposal opportunities, but it does keep it down.

Mutating the table on lookup seems pretty gross, though.

I would argue that "the table" is not mutated, only the internal state of its implementation. Every time you access any information, a cache at some layer below you is updated. Is that also gross?

Yes. Normally you can have one thread writing to a data structure OR many threads reading the data structure at any given time and not need to worry about them causing problems. (This situation is common enough that we have things called "reader-writer mutexes" or "shared-exclusive" mutexes.)

As soon as your reads can modify the internal state of the data structure, it might modify the state in a way which trips up another read; so you can no longer have many threads reading the data structure at once.

But you don't need to write every time, only on occasion, so you can actually use a read write lock and in the nominal case many threads can read just fine.

That said, it's probably still better to avoid this unless it's absolutely necessary to modify the underlying structure sometimes, I recently had to do this for an LRU cache.

Right. And in Rust implementing the hash table that way will suddenly make the table no longer flagged as "Sync" by the compiler, so you will be unable to share it between threads.

That's a great point. It's still a possible optimization with a compare-and-swap or if you can determine that you're in a single threaded context.

Eh, it’s the classic amortized approach. Whoever you ca “touch” the data and you’re right there already due to a lookup, it makes sense to amortize your data structure housekeeping IMO.

TBH, the right answer is always due to the users use case (Amortization and housekeeping really help with purely functional data structures), and benchmark data.

Well, it still works (just slower) if you only do fixups during {table[key] = val} operations. But honestly, if you're using a probabilistic data structure like a hash table, the ship has already sailed on gross implementation details.

No, that's the common approach with chained lists: Move found list item to first.

If you want more material, the "Hash Tables" chapter in my book walks through it:

http://www.craftinginterpreters.com/hash-tables.html

Reading the article reveals that you can either use tombstones or move the elements back into the slot they "would have been in" if the deleted element was never added

This is actually described quite well in the OP.

Oh I see, thanks. I'm on my phone about to go to a meeting and haven't had a chance to read the article yet.

The easiest one is tombstones (i.e. "this item is deleted") to keep the chain alive, or backshifting (i.e. moving all items in the chain forward one slot).

For back-shifting, I'd prefer to actually seek for the tail item in the list (just before you prove the key doesn't exist) and move that BACK to the evicted slot, rather than update all of the keys.

However the tombstone idea fits better with minimizing mutations and improving the potential for concurrency if the design only cares that inserts/deletes are atomic (not that they're propagated in parallel instantly).

For the 'move back' idea to be that safe I'd still want to use a tombstone value, but it would need to also include a pointer to the moved location. The list of tombstones would need to be submitted (as in, message queue) to a kind of garbage collection thread that sat on the messages for a pre-determined validity time and then did a scrub of the key/value to make sure the compaction still made sense. A shorter interval might also allow for that deferred compaction to be replaced by a new entry instead.

I don't like any of that as a generic solution though, as the trade-offs with each bit of extra effort and code complexity seem likely to be premature optimization and sources of potential bugs when not considered in a specific problem domain.

I'm not sure that backshifting is as easy as "moving all items in the chain forward by one slot". Consider the hashtable [A, B1, B2, _, _], where one element is subsequently added after B2, giving [A, B1, B2, X, _]. Now when we remove B1 and shift B2 forward one slot ([A, B2, _, X, _]), we have to shift X forward if it hashes to the second or the third slot in the table, but not the fourth. So there might be multiple chains involved; if it was one contiguous chain only, we could simply arrange for the "hole" in it to be filled with no need for shifting all the items in it, and it would be quite efficient. However, it seems that it's not so simple.

Yup, the chains can be interleaved. Often it's best to save the hash of each key as well as the key itself. Comparing the full hash (rather than the modulus of the hash) will eliminate many keys faster than doing a full key comparison, and having the full hash available means recreation on expansion is cheap, as all the keys don't need rehashing. The full hashes can then be used to distinguish between different chains if you decide to do backfilling, again cheaper than recalculating key hashes.

Of course, having the hashes available also speeds up recreation, should the tombstone approach be used.

Basically, keep the full hashes around :)

Certainly not with open addressing as it will destroy all the cache-line advantages. with seperate chaining it's very common, esp. for resizing.

The key is usually indirected, which means a pointer, which is usually bigger than the hash code.

(And of course you could use parallel arrays if you're super concerned about cache lines, though the tradeoffs would very much depend on whether hash misses or hits are the expected mode.)

And if it’s not a pointer but a word-size integer, just use an invertible hash function (aka permutation aka block cipher) so you can store the hash code in place of the key :)

Pointer chasing is very expensive if your chains end up in different cache lines. The bottleneck on a lot of application isn't how fast your instructions run, but how fast you can get data to them.

All* high performance hashtables use open addressing, because chaining tends to mean (multiple) indirection to addresses outside the table.

* not sure if that's literally true, but I've never seen anyone do chaining in performance-sensitive applications, and all the papers on fast hash tables use some way of open addressing.

I think it largely depends on whether you're using intrusive data structures or not. Even in open addressing you still must always load the object to verify the correct key, so collisions still result in [wasted] random memory access. If the hash table uses dedicated nodes then you have to indirect twice just to verify the key. But in all the hash tables I've written the hash node is already a part of the object, so there's no additional indirection.

However, Rust is allergic to intrusive data structures. Which is a little ironic as single ownership ostensibly would otherwise make intrusive data structures more practical as you're already effectively precluded from inserting an object into multiple hash tables and so there's no potential for contention over the object's internal node fields.

I suppose linear probing also permits prefetching of successive buckets, though ideally collisions should be the exception so such prefetching might just waste bandwidth.

But surely Rust hashtables just store the objects in the table itself? Rust has value semantics, after all. No indirections unless you opt in and `Box` your objects.

AFAIU it depends on the object and its traits. I'm curious how Rust's hash tables are used in practice, i.e. whether the common use case is copying vs taking ownership of the object itself. Though either way what really matters is whether indirection is required to verify the key (e.g. String).

In C I prefer red-black trees over hash tables because memory management is easier, you get smooth performance characteristics (no resize hiccups), and you're immune from computational complexity attacks without sweating over hashing algorithms. But I use intrusive node fields for my trees, and also tend to keep keys (even string keys) internal to the object as well, which substantially closes the cache performance gap.

Ownership is the usual, at least in the ones I’ve seen. Otherwise you have to start reasoning about lifetimes and that’s trickier.

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.

If 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/containe...

Interesting, both the Qt and Java ones seem to use chaining, but I guess they're not designed with these sorts of extremely demanding applications in mind.

One thing to note is that this performance tradeoff is actually the reverse of what it was ~20 years ago. This is because CPU speeds have improved dramatically more than RAM speeds over a similar period.

Open addressing does do more comparisons than chaining. It used to save time to traverse the linked list rather than to spend CPU cycles on those additional comparisons. Now, because CPU cycles are relatively cheaper, the opposite is true.

The reason the Qt and Java hashtables use chaining is simply that the code in question was initially written back when the tradeoff ran the other way.

If hash codes are stored inline alongside keys, code comparisons can be made without an indirection while key comparison (often strings, seldom anything without an indirection) usually needs an indirection. Hash codes are very cheap to compare.

These indirections have always been costly on any machine with virtual memory. TLB misses aren't free. I'd have put any estimate on the tradeoff being the other way around to more than 25 years.

The java.util.HashMap implementation uses chaining, but for example the google guava libraries that are frequently used are open addressing based.

AFAIK an important factor to get good performance out of a hash table is to dimension the table so that collisions are rare. In this scenario it's not too surprising that the additional cost of sometimes having to iterate through the table beats chasing pointers.

Furthermore as the article explains they can use SIMD to search several buckets at once, something that wouldn't really be possible if they didn't exist in contiguous memory.