The basic idea is open addressing, but without any redirections (thus making Swiss tables very memory efficient). Also, Swiss tables store a densely packed array of metadata with each entry consisting of 1 byte (which makes the metadata table easier to fit into CPU cache, as opposed to, say, a metadata of pointers of 8 bytes), sort of like UNIX file system inodes and bit maps (see OSTEP: Chapter 40 File System Implementation). Thus, we can use the metadata to tell if an entry in the table is present or not (by using the single control bit and the 7-bit H2 hash, see the details at https://abseil.io/about/design/swisstables).
And there’s an excellent video about it on youtube.
Finally, let’s see the performance differences on the counting words benchmark.
Recently I found an excellent hashing technique called Robin Hood hashing at https://programming.guide/robin-hood-hashing.html. Their site has also posted a few other amazing hashing techniques in an incredibly accessible way.
Leave a comment