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

Question

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

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

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

Answer 1

yrp*_*yrp 33

Murmur Hash非常好.

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

Answer 2

Nic*_*son 29

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

@Steven:MurmurHash哈希只被其作者诋毁.我在几个不同的场景中使用过它,而新版本的FNV似乎做得更好. (7认同)
@Steven Sudit:正如我所说,它仅由作者"而非"分析.因此,"分析"的结果并不是真正客观的. (7认同)
@sonicoder:我会直言不讳地说:不,你错了.它被许多第三方分析,包括学术第三方.访问维基百科以获取链接.更重要的是,它不仅在一般情况下表现良好,而且通过创建MurmurHash3解决了发现的具体缺陷. (5认同)

Answer 3

Nil*_*nck 17

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

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

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

Answer 4

Chr*_*oph 17

还有一个很好的文章在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;
}

Run Code Online (Sandbox Code Playgroud)

Answer 5

Car*_*org 8

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

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

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

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

干杯,

卡尔

Answer 6

Ant*_*les 7

对于一个好的主题来说，永远不晚，我相信人们会对我的发现感兴趣。

我需要一个哈希函数，在阅读了这篇文章并对此处给出的链接进行了一些研究后，我想出了 Daniel J Bernstein 算法的这种变体，我用它做了一个有趣的测试：



unsigned long djb_hashl(const char *clave)
{
    unsigned long c,i,h;

    for(i=h=0;clave[i];i++)
    {
        c = toupper(clave[i]);
        h = ((h << 5) + h) ^ c;
    }
    return h;
}
Run Code Online (Sandbox Code Playgroud)



这种变体对字符串进行哈希处理，忽略大小写，这满足了我对用户登录凭据进行哈希处理的需要。“clave”在西班牙语中是“钥匙”。我对西班牙语感到抱歉，但它是我的母语，程序是用它写的。

好吧，我编写了一个程序，它将生成从“test_aaaa”到“test_zzzz”的用户名，并且为了使字符串更长，我在这个列表中添加了一个随机域：“cloud-nueve.com”、“yahoo.com” '、'gmail.com' 和 'hotmail.com'。因此它们每个看起来都是这样的：

test_aaaa@cloud-nueve.com，test_aaab@yahoo.com，
test_aaac@gmail.com、test_aaad@hotmail.com 等。



这是测试的输出 -“Colision entre XXX y XXX”表示“XXX 和 XXX 的碰撞”。“palabras”的意思是“单词”，“总计”在两种语言中都是相同的。

    布斯坎多科利西内斯...
    “test_phiz@hotmail.com”和“test_juxg@cloud-nueve.com”之间的冲突 (1DB903B7)
    “test_rfhh@hotmail.com”和“test_fpgo@yahoo.com”之间的冲突 (2F5BC088)
    “test_wxuj@hotmail.com”和“test_pugy@cloud-nueve.com”之间的冲突 (51FD09CC)
    “test_sctb@gmail.com”和“test_iohw@cloud-nueve.com”之间的冲突 (52F5480E)
    “test_wpgu@cloud-nueve.com”与“test_seik@yahoo.com”之间的冲突 (74FF72E2)
    “test_rfll@hotmail.com”和“test_btgo@yahoo.com”之间的冲突 (7FD70008)
    “test_wcho@cloud-nueve.com”与“test_scfz@gmail.com”之间的冲突 (9BD351C4)
    “test_swky@cloud-nueve.com”与“test_fqpn@gmail.com”之间的冲突 (A86953E1)
    “test_rftd@hotmail.com”和“test_jlgo@yahoo.com”之间的冲突 (BA6B0718)
    “test_rfpp@hotmail.com”和“test_nxgo@yahoo.com”之间的冲突 (D0523F88)
    “test_zlgo@yahoo.com”和“test_rfdd@hotmail.com”之间的冲突 (DEE08108)
    碰撞总数：11
    帕拉布拉斯总数：456976



这还不错，456,976 次碰撞中有 11 次（当然使用完整的 32 位作为表长度）。

使用 5 个字符（即从“test_aaaaa”到“test_zzzzz”）运行程序，实际上会耗尽构建表的内存。下面是输出。“No hay memoria para insertar XXXX (insertadas XXX)”的意思是“没有剩余内存可插入 XXX (XXX已插入)”。基本上 malloc() 在那一点上失败了。

    没有插入“test_epjcv”的干草记忆（插入 2097701）。

    布斯坎多科利西内斯...

    ...451'碰撞'字符串...

    碰撞总数： 451
    帕拉布拉斯总数：2097701

 

这意味着 2,097,701 个字符串上仅发生 451 次碰撞。请注意，在任何情况下，每个代码的冲突次数都不会超过 2 次。我确认这对我来说是一个很好的哈希，因为我需要将登录 ID 转换为 40 位唯一 ID 以进行索引。因此，我使用它将登录凭据转换为 32 位哈希，并使用额外的 8 位来处理每个代码最多 255 次冲突，从测试结果来看，几乎不可能生成这些冲突。

希望这对某人有用。

编辑：

就像测试盒是 AIX 一样，我使用 LDR_CNTRL=MAXDATA=0x20000000 来运行它，以给它更多的内存，并且运行时间更长，结果如下：

Buscando Colisiones... 碰撞总数： 2908 帕拉布拉斯总数： 5366384

经过 5,366,384 次尝试后，即为 2908！

非常重要：使用 -maix64 编译程序（因此无符号长整型为 64 位），所有情况下冲突次数均为 0！

归档时间：	16 年，11 月前
查看次数：	81417 次
最近记录：	10 年，4 月前