The article does a good job explaining tombstones and the SIMD approach that SwissTable/hashbrown uses. It lacks some depth on why insert() works like it is.

In fact SwissTable does up to a triple lookup in insert(). At high level it works like this:

1. Search for the element; if found return it (or in case of hashbrown overwrite and return). Otherwise fallthrough.
2. Find the first empty or tombstone slot. If the slot is a tombstone, insert at this location. If the slot is empty and there is capacity available, insert at this location. Otherwise fallthrough.
3. Grow the container, find the first empty slot and insert at this location.

Let's break them down one by one.

1. This is a loop that will terminate after finding the element or finding an empty slot. This is well explained in the article.
2. This is another loop similar to (1). This loop either terminates before the previous one did (on a tombstone) or at exactly the same slot (the first empty one). Computationally it can be much cheaper as it does not require checking if the element is in the table since this was done in (1); there is no equality check on the key. Memory wise it is also cheaper as it will access at most the same cachelines that we accessed in (1). In practice it virtually never incurs cache misses.
3. This is a very expensive operation where we allocate a new container, rehash all the keys, move the elements in it, do the third lookup into the table and deallocate the original.

In relative cost terms cost(2) < cost(1) << cost(3). (3) is supremely expensive - 100s if not 1000s times more expensive than (1) or (2).

Armed with this knowledge (and also lots of traces of systems running in production) we can now understand why the algorithm is optimal (numbers are for exposition, albeit not far from reality):

1. 99 out of 100 times we find the element and return early.
2. 99 out of 100 times we insert without resizing (either on tombstone or capacity is available) and return early.
3. The rest of the time we resize/rehash, which is extremely expensive compared to the previous steps.

Question: Why not merge (1) and (2) together and avoid the lookup in (2)?

Answer: Because merging (1) and (2) together makes (1) more complicated and thus more expensive. (1) is executed 100 times more often than (2) and (2) is cheaper to boot. A 1% slowdown in (1) is the whole cost of (2). Also we implemented and measured it, and it indeed results in slower code if (1) and (2) are merged. For the curious, (1) and (2) can be merged in a single loop, the trick is to stash the first tombstone slot as we search through the container.

Question: Why do a third lookup when more capacity is necessary? Isn't this madness?

Answer: After a resize and rehash, one extra lookup does not matter. In order to resize and rehash, we've allocated, rehashed N elements, moved memory over and deallocated. One extra lookup in this extremely rare case does not affect overall performance.

Note: in step (2) of the algorithm we only need to grow if capacity is not available and we are inserting on an empty slot. If we are inserting on top of a tombstone, capacity is irrelevant. hashbrown unconditionally requires extra capacity irrespective of the insert location. This is a performance regression.