hash specializations for std::pair and std::tuple

[odygrd]

Hello, thank you for the library and the benchmarks!

I think it would be useful to provide hash specializations for std::pair and std::tuple.
Those don't exist in the standard but some other hash map implementations like absl provide them.

This would be really convenient as people won't have to rely on implementing their own, especially having to combine the hashes.

This is how I have done it below.
It would be nice to have struct ankerl::unordered_dense::hash<std::pair<T1, T2>> and struct ankerl::unordered_dense::hash<std::tuple<Ts...>> as part of the implementation in unordered_dense.h

I am not sure if my implementation of void hash_combine(size_t& seed, T const& v) is optimal or if you can come up with something better suited for wyhash

#include <iostream>
#include <string>

#include <tuple>
#include <utility>

#include "unordered_dense.h"

template <class T>
void hash_combine(size_t& seed, T const& v)
{
  // from https://stackoverflow.com/questions/5889238/why-is-xor-the-default-way-to-combine-hashes
  if constexpr (sizeof(size_t) >= 8u)
  {
    seed ^= v + 0x517cc1b727220a95 + (seed << 6u) + (seed >> 2u);
  }
  else
  {
    seed ^= v + 0x9e3779b9 + (seed << 6u) + (seed >> 2u);
  }
}

template <typename T1, typename T2>
struct ankerl::unordered_dense::hash<std::pair<T1, T2>>
{
  using is_avalanching = void;

  [[nodiscard]] auto operator()(std::pair<T1, T2> const& x) const noexcept -> uint64_t
  {
    size_t seed = 0;
    hash_combine(seed, ankerl::unordered_dense::hash<std::decay_t<T1>>{}(x.first));
    hash_combine(seed, ankerl::unordered_dense::hash<std::decay_t<T2>>{}(x.second));
    return seed;
  }
};

template <typename... Ts>
struct ankerl::unordered_dense::hash<std::tuple<Ts...>>
{
  using is_avalanching = void;

  [[nodiscard]] auto operator()(std::tuple<Ts...> const& x) const noexcept -> uint64_t
  {
    size_t seed = 0;
    std::apply(
      [&seed](Ts const&... elem) {
        (hash_combine(seed, ankerl::unordered_dense::hash<std::decay_t<decltype(elem)>>{}(elem)), ...);
      },
      x);
    return seed;
  }
};

void hash_pair_example()
{
  ankerl::unordered_dense::map<std::pair<std::string, std::string>, std::string> map{};
  map[std::make_pair(std::string{"123"}, std::string{"123"})] = "hello";
  map[std::make_pair(std::string{"987"}, std::string{"987"})] = "world!";

  for (auto const& [key, val] : map)
  {
    std::cout << "(" << key.first << ":" << key.second << ")"
              << " => " << val << std::endl;
  }
}

void hash_tuple_example()
{
  ankerl::unordered_dense::map<std::tuple<std::string, std::string, uint32_t>, std::string> map{};
  map[std::make_tuple(std::string{"123"}, std::string{"123"}, 123u)] = "hello";
  map[std::make_tuple(std::string{"987"}, std::string{"987"}, 123u)] = "world!";

  for (auto const& [key, val] : map)
  {
    std::cout << "(" << std::get<0>(key) << ":" << std::get<1>(key) << ":" << std::get<2>(key) << ")"
              << " => " << val << std::endl;
  }
}

int main()
{
  hash_pair_example();
  hash_tuple_example();
}

[martinus]

Hi @odygrd, thanks for the code examples! I played a bit with the implementation, and now think it's really worthwhile to have implementations for these available. Creating a high performance & high quality hash for tuple is not trivial. I think I've got a good implementation now though, I'll release it as 4.3.0

[martinus]

Fixed in release v4.3.0