c++ - unordered_map 的哈希函数是确定性的吗？

Question

我正在尝试调试我们代码库中的缓存问题，我们使用 std::unordered_map 来散列下面定义的结构 custom_key，但我相信它应该只是 POD 数据类型，所以我认为无论为散列函数实现的 C++ 库都将被使用。我想知道这个函数是否是确定性的？

struct custom_key {
  // bunch of uint8_t variables
  // some int8_t variables
  // some boolean variables
  another_struct params;
}

struct another_struct {
  // an enum variable
  // some int variables
  int dimensions[5];
}

我们的缓存算法是

// some_input_key is coming in from a stream
std::unordered_map<custom_key, some_output_type, custom_hasher<custom_key>, custom_equal<custom_key>> ht;
if (ht.find(some_input_key) != ht.end()) {
  // do something
} else {
  ht[some_input_key] = ....
}

在我们的输入流中，我们有一组 custom_keys，其中可能有相同的值，但我们无法在哈希表中找到 一些 后续相同的键.

例如，我们的流是 key1, key2, key3, key4, .... 并假设 key1 和 key4 相同，有时它无法在哈希表中找到 key4。我很确定散列函数是确定性的，所以我很困惑是什么导致了这个问题。我已经打印了两个 key 的内容，它们看起来完全相同。

编辑:看来我们确实有一个自定义哈希函数

template <typename T>
// based on Fowler–Noll–Vo hash function
struct custom_hasher {
  static_assert(std::is_pod<T>::value, "T is not POD");

  size_t operator()(const T& input) const {
    auto ptr = reinterpret_cast<const uint8_t*>(&input);
    uint32_t value = 0x811C9DC5;
    // we have an implementation for irange that does something similar to the one in python
    for (const auto i : irange((int)sizeof(T))) {
      value ^= ptr[i];
      value *= 0x01000193;
    }
    return (size_t)value;
  }
};

template <typename T>
struct custom_equal {
  static_assert(std::is_pod<T>::value, "T is not POD");

  bool operator()(const T& lhs, const T& rhs) const {
    auto ptr1 = reinterpret_cast<const uint8_t*>(&lhs);
    auto ptr2 = reinterpret_cast<const uint8_t*>(&rhs);
    return memcmp(ptr1, ptr2, sizeof(T)) == 0;
  }
};

Answer 1

cppreference.com:

For two parameters k1 and k2 that are equal, std::hash()(k1) == std::hash()(k2). For two different parameters k1 and k2 that are not equal, the probability that std::hash()(k1) == std::hash()(k2) should be very small, approaching 1.0/std::numeric_limitsstd::size_t::max().

std::unordered_map 将在其键上使用散列。具有相同 HASH 的对象进入相同的桶。但是，如果两个事物具有相同的 VALUE，则第二对将被忽略。如果 key1 和 key4 相同，则 key4 及其值将被丢弃。

您要使用的是 std::unordered_multimap(参见 here): cppreference.com:

Unordered multimap is an unordered associative container that supports equivalent keys (an unordered_multimap may contain multiple copies of each key value) (emphasis added).

编辑: 正如其他人所说，填充可能会扰乱您的哈希结果。另一种方法是单独散列结构的每个成员，然后组合散列。