← Back to context

Comment by jbreckmckye

1 day ago

I'm lazy. What's a Swiss table in a couple of sentences? Assume I am _moderately_ competent with C++ but not some Level 800 cyberbrain

6 comments

jbreckmckye

Reply
procaryote  1 day ago

Caveat that this is new to me and I might get it wrong

It seems to be a way to arrange a hashtable so you use most of the hashed value (H1) to identify a range of cells in your table, and the rest of the hashed value (H2) as metadata. In the metadata for a cell it's tagged as empty/full/deleted and a full cell is also tagged with its H2 value

So when looking up things you find the range with H1, then you check H2 against the metadata for that range, to see which of the cells might contain the right value.

I imagine the benefit is that checking H2 against warm metadata is cache friendly and can use vector instructions, whereas with regular double hashing you'd need to lookup cold memory to check the key, and then perhaps do it again a couple of times

Do correct me if I am wrong

tialaramex  1 day ago

It's an open addressed hash table using SIMD to get faster probing? If all that makes sense but you feel unsatisfied I can't help you and you need to ask somebody who knows exactly what you do or don't know.

If those phrases don't make sense, Wikipedia has entries on Open Addressing and on SIMD which can help you.

  • jbreckmckye  1 day ago

    Thanks, I don't fully understand but I know enough about each idea to Google it further

    • froh  1 day ago

      especially it doesn't "degrade" when nearly full (text book disadvantage of linear probing), by cleverly rearranging existing items on hash table insert (and also on delete).

      so there is a kinda sorta "balancing" of the linear probing lengths.