在非性能关键情况下对的合理哈希

Question

我遇到这样的情况：容器不会很大（最多两三百个条目？）并且查询不会特别频繁（最多每秒数百个？）

这并不过分，但我也不想做任何愚蠢的事情。像这样的哈希函数“合理”吗？

unordered_map<std::pair<T, U>>

假设 hT 和 hU 是良好的哈希函数。例如，

class my_hasher
{
    std::size_t operator()(auto const& k) const noexcept
    {
       std::hash<T> hT;
       std::hash<U> hU;
       return hT(k.first) ^ hT(k.second); 
    }
};

呢？ （那么

std::pair<std::string, std::string>

默认哈希函数是身份呢？）对于非性能关键情况，组合哈希函数的合理方法是什么？

我当然可以“复制”

std::pair<int, int>

并做类似的事情

boost::hash_combine

但我不想用位技巧过度做简单的事情，除非确实有必要，但我也不想创建愚蠢的哈希函数。

Answer 1

std::size_t ret = hT(k.first); 
return ret ^ hU(k.second) + 0x9e3779b9 + (ret << 6) + (ret >> 2);

，则可以在使用

std::numeric_limits<T>::digits + std::numeric_limits<U>::digits < std::numeric_limits<long long>::digits

进行散列之前将它们组合成一个更大的整数。这类似于

另一个答案

，尽管不是通过硬编码值进行移位，而是可以这样做： std::hash

字符串需要更多的工作，但这里有一些可能是合理的选项。请注意，如果在某些情况下，配对的分离是唯一性的一部分（例如，配对“apple”、“orange”和配对“appleorange”、“”），这些可能会给您带来问题：

而是存储

std::size_t operator()(std::pair<T,U> k) const noexcept
{
   static_assert(std::numeric_limits<T>::digits + std::numeric_limits<U>::digits < std::numeric_limits<long long>::digits, "integer overflow possible in hash function");
   static constexpr long long mult = 1ll << std::numeric_limits<U>::digits;
   return std::hash(k.first * mult + k.second);
}

1. 作为您的密钥，并且为了进行哈希处理，只需转发到

   std::pair<std::string, std::string::size_type>

   。该字符串只需将一个字符串附加到另一个字符串即可创建，第一个字符串的长度存储为该对的第二个成员，这样您就可以在恒定时间内以

   std::hash<std::string>

   的形式“返回”原始字符串。如果

   std::string_view

   对于您的用例来说太尴尬，这不是一个很好的选择，但确实允许您坚持使用

   std::string_view

   ，而不需要采取进一步的欺骗手段。FNV-1a 哈希
有一个公共域 C 实现
2. ，适用于字符序列。您的哈希函子可以使用推荐的偏移量通过 fnv 运行第一个字符串，并使用第一个字符串的结果作为偏移量通过它运行第二个字符串。还有其他已建立的哈希函数（可能比 FNV-1a 更快），但除了公共域参考实现之外，FNV-1a 的一个好处是可以使其成为 constexpr，所以如果你发现自己对于您想要在编译时预先计算字符串文字的哈希值的用例，它也可以用于此目的。