c++ - 如何为 size_t 以外的返回类型专门化 std::hash 调用运算符？

Question

这是我第一次尝试使用 std::unordered_map，c++17。我正在尝试构建一个快速的 LRU，我将 sha1 摘要映射到数据 block 。我的 sha1 对象是完全可比较的等等，但是当我尝试实例化 map 时，我得到这个错误:

/usr/include/c++/7/bits/hashtable_policy.h:87:34: error: no match for call to ‘(const std::hash<
kbs::crypto::basic_digest<20,kbs::crypto::openssl_sha1_digest_engine_policy> >) (const kbs::crypto::basic_digest<20, kbs::crypto::openssl_sha1_digest_engine_policy>&)’
  noexcept(declval<const _Hash&>()(declval<const _Key&>()))>

所以看起来我可以为我的用户定义类型专门化 std::hash。但是，它总是返回 size_t，这很糟糕，从 20 字节到 8 字节有点违背了将 sha1 用作 hash_key 的目的。

有没有办法解决这个问题？替代容器？不得不编写自己的 hashmap 是一种浪费。我想我可以使用 std:set...

Answer 1

无序映射不假定散列(size_t)是唯一的。它假定键是。如果哈希良好，它会表现良好。

无序映射使用size_t 来确定将数据放入哪个桶。它可以很好地处理 size_t 空间中的碰撞。

根据需要将 sha HashMap 到 size_t，并使用 sha 哈希作为 key 。在不太可能发生的情况下，您会遇到 size_t 散列冲突(当您在无序映射中有大约 40 亿个元素时，假设散列良好，则为 50/50 - 请参阅数学的“生日悖论”，或者更常见的是较小的哈希表；它会动态地增加表)它会依赖于你的 sha 哈希键的相等性来避免“真正的”冲突。

有多种碰撞。

• Sha-hash 冲突:不好，意味着相同的 key 不同的数据。
• size_t 哈希冲突:嗯，意味着两个元素将始终在同一个桶中。
• 内部哈希表冲突:常见，意味着在这个特定大小下，两个元素在同一个桶中。

除非您的大部分数据 maos 具有相同的 size_t，否则该 map 有损是完全没问题的。您只需担心第一种碰撞，并在您的 sha-hashes 上提供 ==。