Awesome Swiss Tables

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 the CPU cache, as opposed to, say, 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 this compact metadata to determine if an entry in the table is present, empty, or deleted 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.

Join the Conversation

1 Comment

Leave a comment

Your email address will not be published.

The maximum upload file size: 10 MB. You can upload: image, audio, video, document, spreadsheet, interactive, text, archive, code, other. Links to YouTube, Facebook, Twitter and other services inserted in the comment text will be automatically embedded. Drop file here