具有32位整数的低冲突率的快速字符串哈希算法

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

我想看一个特定于C/C++的优化实现.

1> yrp..：

---

Murmur Hash非常好.

---

是的,这是哈希表当前领先的通用哈希函数.当然,它是非加密的,有一对明显的差别.

2> Nick Johnson..：

---

其中一种FNV变体应满足您的要求.它们很快,并且产生相当均匀的分布式输出.

---

@Steven:MurmurHash哈希只被其作者诋毁.我在几个不同的场景中使用过它,而新版本的FNV似乎做得更好.

---

@Steven Sudit:正如我所说,它仅由作者"而非"分析.因此,"分析"的结果并不是真正客观的.

---

@sonicoder:我会直言不讳地说:不,你错了.它被许多第三方分析,包括学术第三方.访问维基百科以获取链接.更重要的是,它不仅在一般情况下表现良好,而且通过创建MurmurHash3解决了发现的具体缺陷.

3> Nils Pipenbr..：

---

对于固定的字符串集,请使用gperf.

如果您的字符串集更改,您必须选择一个哈希函数.之前讨论过这个话题:

使用hash_map时,在stl字符串上使用的最佳散列算法是什么？

4> Christoph..：

---

还有一个很好的文章在eternallyconfuzzled.com.

Jenkins对字符串的一次性哈希应该如下所示:

#include 

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;
}

5> Carl Selebor..：

---

根据您的用例,可能更好的另一种解决方案是实习字符串.这就是符号在Lisp中的工作方式.

实习字符串是一个字符串对象,其值是实际字符串字节的地址.因此,您通过检入全局表来创建一个实习字符串对象:如果字符串在那里,则将实习字符串初始化为该字符串的地址.如果没有,则插入它,然后初始化您的实习字符串.

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

构造缓慢(需要查找和可能的内存分配)

在并发线程的情况下需要全局数据和同步

比较是O(1),因为你比较的是地址,而不是实际的字符串字节(这意味着排序效果很好,但不会是字母排序).

干杯,

卡尔