我需要一个在C++中针对哈希表的高性能哈希函数实现。我已经搜索了一些，但只找到了一些询问“一般情况下什么是好的哈希函数”问题的答案。我考虑过CRC32（但从哪里找到好的实现？）以及一些加密算法。然而，我的表格具有非常特定的要求。
这就是表格的样子：
100,000 items max
200,000 capacity (so the load is 0.5)
hashing a 6-character string which is a part of English sentence
examples: "become" "and he" ", not "
我的哈希表的首要优先事项是快速搜索（检索）。快速插入并不重要，但它会随着快速搜索而来。删除不重要，重新哈希也不是我要考虑的事情。为了处理冲突，我可能会使用分离链接法，如此处所述。我已经查看了这篇文章，但想听听那些曾处理过这种任务的人的意见。
现在假设您想要一个哈希，并且希望得到一些在您的情况下运行“非常快”的东西，因为您的字符串只有6个字符，所以您可以使用以下代码：
size_t precision = 2; //change the precision with this
size_t hash(const char* str)
{
return (*(size_t*)str)>> precision;
}
CRC是慢吞吞的东西 ;)
说明： 这个方法通过将字符串指针的内容强制转换为"看起来像"size_t（基于硬件最佳匹配的int32或int64）。因此，字符串的内容被解释为一个原始数字，不再需要担心字符问题，然后将其按所需的精度进行位移（您可以调整此数字以获得最佳性能，我发现2适用于在几千个字符串中哈希字符串）。
另外一个非常棒的部分是，任何现代硬件上的良好编译器都会使用1条汇编指令对这样的字符串进行哈希，很难超越它;)
std::uint32_t和std::uint16_t，您可以安全地访问数据的所有6个字节（在您的实现中，如果size_t是32位，则最后两个字符不会被哈希，如果是64位，则可能发生内存缓冲区读取溢出，导致崩溃），然后可能对它们进行异或运算，因为速度是优先考虑的。由于哈希函数较弱，在这里使用一个素数数量的桶会有所帮助。 - Tony Delroy这个简单的多项式效果出奇地好。我是从微软研究院的Paul Larson那里学来的，他研究了各种哈希函数和哈希乘数。
unsigned hash(const char* s, unsigned salt)
{
unsigned h = salt;
while (*s)
h = h * 101 + (unsigned) *s++;
return h;
}
salt应该在创建哈希表之前被初始化为一些随机选择的值，以防止哈希表攻击。如果这对您来说不是问题，只需使用0。
表的大小也很重要，可最小化碰撞。听起来你的大小还可以。
(unsigned)。 - George V. ReillyBoost.Functional/Hash 可能对您有用。我没有尝试过，因此无法保证其性能。
Boost 还有一个 CRC 库。
我会首先看一下 Boost.Unordered（即 boost::unordered_map<>）。它使用哈希表而不是二叉树作为容器。
我相信一些 STL 实现在 stdext 命名空间中有一个 hash_map<> 容器。
size_t hash(const std::string &data) {
size_t h(0);
for (int i=0; i<data.length(); i++)
h = (h << 6) ^ (h >> 26) ^ data[i];
}
return h;
}
// Initialize hash lookup so that it maps the characters
// in your string to integers between 0 and 31
int hashLookup[256];
// Hash function for six character strings.
int hash(const char *str)
{
int ret = 0, mult = 1;
for (const char *p = str; *p; *p++, mult *= 32) {
assert(*p >= 0 && *p < 256);
ret += mult * hashLookup[*p];
}
return ret;
}
假设32位整数, 该算法每个字符使用5个比特位，因此哈希值只有30个比特位。也许你可以通过为前1或2个字符生成6个比特位来修复这个问题。如果你的字符集足够小，则可能不需要超过30个比特位。
std::hash< string >( string )。这可能是一种有效的哈希函数，为大多数字符串提供了良好的哈希码分布。std::unordered_map。std::hash<int>(int) 和 std::hash<string>(string) 是不同的函数。 - Raedwald