我想对许多无关的命名事物进行快速搜索。 " aardvark"在任何地方都始终是" aardvark"，因此对字符串进行散列并重新使用整数可以很好地加快比较速度。整个名称集是未知的(并且会随时间变化)。什么是快速字符串哈希算法，它将生成较小的(32或者16)位值并且具有较低的冲突率？

我希望看到针对C / C ++的优化实现。

解决方案

看看GNU gperf。

CRC-32. 谷歌上有大约一万亿个链接。

FNV变体之一应符合要求。它们速度很快，并产生相当均匀的分布式输出。

对于固定的字符串集，请使用gperf。

如果更改了字符串集，则必须选择一个哈希函数。之前已经讨论了该主题：

使用hash_map时，在stl字符串上使用的最佳哈希算法是什么？

Murmur Hash非常好。

根据用例，另一种可能更好的解决方案是内联字符串。这就是符号的工作方式，例如在Lisp中。

插入字符串是一个字符串对象，其值是实际字符串字节的地址。因此，我们可以通过检入一个全局表来创建一个嵌入的字符串对象：如果该字符串在其中，则可以将嵌入的字符串初始化为该字符串的地址。如果不是，则将其插入，然后初始化实习字符串。

这意味着从同一字符串构建的两个内联字符串将具有相同的值，即地址。因此，如果N是系统中实习字符串的数量，则特征为：

• 慢速构建(需要查找，可能还需要分配内存)
• 在并发线程的情况下需要全局数据和同步
• Compare为O(1)，因为我们正在比较地址，而不是实际的字符串字节(这意味着排序效果很好，但不会是字母排序)。

干杯，

卡尔

Hsieh哈希函数非常不错，并且作为C语言中的常规哈希函数具有一些基准/比较。根据我们想要的(并不完全明显)，我们可能需要考虑使用cdb之类的东西。

在上一个问题中有一些很好的讨论

并很好地概述了如何选择哈希函数，以及有关此处几种常见函数的分布的统计信息

我们为什么不只使用Boost库？它们的哈希函数易于使用，Boost中的大多数功能很快都将成为C ++标准的一部分。其中一些已经是。

Boost哈希就像

#include <boost/functional/hash.hpp>

int main()
{
    boost::hash<std::string> string_hash;

    std::size_t h = string_hash("Hash me");
}

我们可以在boost.org上找到boost

鲍勃·詹金斯(Bob Jenkins)有许多可用的哈希函数，所有这些哈希函数都很快速且冲突率很低。

我们可以使用Reflector查看.NET在String.GetHashCode()方法上使用的内容。

我可能会猜测微软会花费大量时间对此进行优化。它们也已在所有MSDN文档中打印，因此随时可能更改。很明显，这是在他们的"性能调整雷达"上；-)

我也想过，移植到C ++会很琐碎。

在eternallyconfuzzled.com上也有一篇不错的文章。

詹金斯(Jenkins)的一次性字符串哈希应如下所示：

#include <stdint.h>

uint32_t hash_string(const char * s)
{
    uint32_t hash = 0;

    for(; *s; ++s)
    {
        hash += *s;
        hash += (hash << 10);
        hash ^= (hash >> 6);
    }

    hash += (hash << 3);
    hash ^= (hash >> 11);
    hash += (hash << 15);

    return hash;
}