Hashing Framework

Introduction

Writing hashing functions for keys in hash-based containers is a tedious task. However, often hashing a struct involves hashing all its members and combining those hashes. Hashing iterable containers like std::vector<T> or std::set<T> involves hashing all entries and hash combining the computed hashes.

Cista contains a framework that automatically hashes any composition of scalars, iterable structs (like vector, set, etc.), and standard layout, non-polymorphic aggregate types (Code is here). Char arrays are hashed as string. Additionally, it allows to implement a hash() const -> size_t member function or an overloaded std::hash<T>. Hashing is done recursively.

This hashing function is the default hash of cista::hash_map and cista::hash_set.

Example

Consider the following struct:

struct message {
  int code_{};
  std::string text_;
  std::string type_;
};

Depending on the application, a hashing function would probably often just hash all members. This is what cista::hashing<T> does. And it does it recursively - e.g the std::string members in the message struct are hashed as iterable of char entries.

message k{3, std::string{"4321"}, std::string{"1234"}};
CHECK(cista::hashing<message>{}(k) ==
      // hash message::type_ third
      cista::hash(std::string{"1234"},  // std::string is hashed as iterable!
                  // hash message::text_ second
                  cista::hash(std::string{"4321"},
                              // hash message::code_ first
                              cista::hash_combine(cista::BASE_HASH, 3))));

Strings

It is important to notice, that all string types yield the same hash if they contain the same sequence of characters. This includes:

• Cista string cista::raw::string and cista::offset::string
• Cista string view cista::raw::string_view and cista::offset::string_view
• standard string std::string
• standard string view std::string_view
• char arrays: char[N]

This behaviour is very handy when it comes to lookups in cista::hash_map and cista::hash_set.

Hash Equivalent Types

As mentioned in the point above (Strings), all string types yield the same hash if the contents match. This is integrated into cista::hashing<T>: the create<T1>() function allows to create a hashing<T1> struct iff cista::is_hash_equivalent<T, T1> evaluates to true. This attribute is true for all string types mentioned above. To enable the same behaviour for custom types, the following struct can be used:

template <typename A, typename B>
struct is_hash_equivalent_helper : std::true_type {};

Hash equivalence is very handy when it comes to lookups in cista::hash_map and cista::hash_set because it prevents creation of intermediate values.