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
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_set (or an
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
For more information about Swiss tables, see the
container library documentation.
absl::Hash hashing framework
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::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
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
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.