Swiss Tables and absl::Hash

By Sam Benzaquen, Alkis Evlogimenos, Matt Kulukundis, and Roman Perepelitsa

We are extremely pleased to announce the availability of the new “Swiss Table” family of hashtables in Abseil and the absl::Hash hashing framework that allows easy extensibility for user defined types.

Last year at CppCon, We presented a talk on a new hashtable that we were rolling out across Google’s codebase. When asked about its release date, we may have been a touch optimistic. But hopefully it will have been worth the wait. As an added bonus, this release also comes with an entirely new framework for hashing your types. As with all things of this size, this is the work of a great many people.

Swiss Tables boast improvements to efficiency and provide C++11 codebases early access to APIs from C++17 and C++20.

These hash tables live within the Abseil container library.

absl::flat_hash_map and absl::flat_hash_set

The “flat” Swiss tables should be your default choice. They store their value_type inside the container’s main array to avoid memory indirections. Because they move data when they rehash, elements do not get pointer stability. If you require pointer stability or your values are large, consider using an absl::node_hash_map or absl::node_hash_set (or an absl::flat_hash_map<Key, std::unique_ptr<Value>>).

absl::node_hash_map and absl::node_hash_set

The “node” Swiss tables allocate their value_type in nodes outside of the main array (as in std::unordered_map). Because of the separate allocation, they provide pointer stability (the address of objects stored in the map does not change). As well, the stored data and empty slots only require 8 bytes. Additionally, they can store things that are neither moveable nor copyable.

We generally recommend that you use absl::flat_hash_map<K, std::unique_ptr<V>> instead of absl::node_hash_map<K, V>.

For more information about Swiss tables, see the Abseil container library documentation.

The absl::Hash hashing framework

The absl::Hash library consists of two parts:

• absl::Hash<T>, a concrete hash functor object, which you can use out of the box
• A generic hashing framework for specializing hashing behavior and making user-defined types hashable

This library is designed to be used as a replacement for std::hash and the various other hash functors. It provides several advantages over them:

• It can hash objects of almost any standard type, including std::pair, std::tuple, and most standard containers.
• It can be extended to support user-defined types. Our goal is that if it makes sense to hash an object of type Foo, then absl::Hash<Foo> will just work. These extensions are easy to write and efficient to execute.

Importantly, the underlying hash algorithm can be changed without modifying user code, which allows us to improve both it and types which utilize absl::Hash over time. For example, we might wish to change the hashing algorithm within a container to improve performance and to defend against some hash-flooding attacks.

The absl::Hash framework is the default hash implementation for the Swiss tables and does not need to be explicitly specified when working with that library.

For more information, see the Abseil hash library documentation.