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, 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 (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: 50 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