logo标签列表

具有低碰撞率的快速字符串哈希算法（使用32位整数）

c++algorithmstringhash
70

我有很多不相关的命名事物，想要进行快速搜索。 "土豚" 在任何地方都是 "土豚"，因此对字符串进行哈希处理并重复使用整数可用于加快比较速度。整个名称集合未知（而且随时间变化）。有什么快速的字符串哈希算法可以生成小的（32或16位）值并具有低碰撞率？

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

请添加关键字：哈希算法、唯一、低碰撞。 - slashmais
24
以下页面提供了几种通用哈希函数的实现，这些函数具有高性能和低碰撞率: http://partow.net/programming/hashfunctions/index.html - Matthieu N.
14个回答
35
3
是的，这是当前用于哈希表的主流通用哈希函数。它当然不是加密级别，有一对明显的差异。 - obecalp
1
注意：MurmurHash3的新网址是https://code.google.com/p/smhasher/。 - Emil Styrke
30

其中的FNV变体应该能够满足你的需求。它们速度快，输出结果相对均匀。

7
@Steven说：MurmurHash哈希算法只有作者进行了分析。我在几种不同的场景中使用过它，但新版本的FNV似乎做得更好一些。 - Matthieu N.
8
正如我所说，这份报告只有作者自己进行了分析，没有其他人参与。因此，“分析”的结果并不是十分客观。 - Matthieu N.
6
@sonicoder：我说话直白一些：不，你错了。它已经被多个第三方，包括学术机构进行了分析。请访问维基百科获取链接。更重要的是，它不仅整体表现良好，而且发现的具体缺陷已通过创建MurmurHash3得到解决。 - Steven Sudit
@DarthGizka，这个“在速度和质量上击败FNV的许多简单哈希函数”的例子是什么？我非常感兴趣。 - user5125586
@Richard：根据您选择的应用程序，您可以尝试使用自我异或旋转累加器（旋转与字长互质）或Xorshift，在哈希结束时跟随扩展乘法。如果您可以使用内部函数，CRC具有出色的质量并且速度非常快。当事情变得棘手时，我确信Bob Jenkins对哈希的广泛和深入研究已经涵盖了您需要的内容。如果您使用逆乘法而不是除法，则素数模数可以很快。 - DarthGizka
显示剩余5条评论
20

在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;
}
17
一个完美哈希是一种非常优雅的解决方案，当可用时。 - Steven Sudit
9
另一种解决方案，根据您的用例可能会更好，就是内部化字符串。这就是符号在Lisp中的工作方式。
内部化字符串是一个字符串对象，其值是实际字符串字节的地址。因此，通过在全局表中检查来创建内部化字符串对象：如果字符串在其中，则将内部化字符串初始化为该字符串的地址。如果没有，则插入它，然后初始化您的内部化字符串。
这意味着从同一字符串构建的两个内部化字符串将具有相同的值，即地址。因此，如果N是系统中内部化字符串的数量，则其特征为：
- 构造缓慢（需要查找和可能的内存分配） - 在并发线程的情况下需要全局数据和同步 - 比较为O（1），因为您正在比较地址，而不是实际字符串字节（这意味着排序效果很好，但它不会是按字母顺序排序）。
干杯，
卡尔
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;
}

这个变种哈希字符串时不考虑大小写的，适用于我的需求，即对用户的登录凭据进行哈希处理。 'clave' 在西班牙语中是 'key' 的意思。很抱歉使用了西班牙语，但那是我的母语，程序也是用它编写的。

我编写了一个程序，可以从'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' 的意思是 'words'，而'Total'在两种语言中都是一样的-。

    Buscando Colisiones...
    Colision entre 'test_phiz@hotmail.com' y 'test_juxg@cloud-nueve.com' (1DB903B7)
    Colision entre 'test_rfhh@hotmail.com' y 'test_fpgo@yahoo.com' (2F5BC088)
    Colision entre 'test_wxuj@hotmail.com' y 'test_pugy@cloud-nueve.com' (51FD09CC)
    Colision entre 'test_sctb@gmail.com' y 'test_iohw@cloud-nueve.com' (52F5480E)
    Colision entre 'test_wpgu@cloud-nueve.com' y 'test_seik@yahoo.com' (74FF72E2)
    Colision entre 'test_rfll@hotmail.com' y 'test_btgo@yahoo.com' (7FD70008)
    Colision entre 'test_wcho@cloud-nueve.com' y 'test_scfz@gmail.com' (9BD351C4)
    Colision entre 'test_swky@cloud-nueve.com' y 'test_fqpn@gmail.com' (A86953E1)
    Colision entre 'test_rftd@hotmail.com' y 'test_jlgo@yahoo.com' (BA6B0718)
    Colision entre 'test_rfpp@hotmail.com' y 'test_nxgo@yahoo.com' (D0523F88)
    Colision entre 'test_zlgo@yahoo.com' y 'test_rfdd@hotmail.com' (DEE08108)
    Total de Colisiones: 11
    Total de Palabras  : 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运行它以提供更多内存，并且运行时间更长，结果在此处：

正在查找冲突... 冲突总数：2908 单词总数：5366384

这是在5,366,384次尝试后的2908次冲突！

非常重要：使用-maix64编译程序（因此unsigned long为64位），所有情况下的冲突数都为0！！

你的代码似乎有一个 bug：你的 h 需要初始化为零，否则你可能会从未初始化的内存开始，并得到不可重现的变化哈希值，这将是相当糟糕的。 - E. T.
3
2
哈希函数非常稳定且技术上很有趣，但不一定快速。请考虑一次一个字节地处理输入的One-at-a-Time哈希，而其他哈希则每次处理4甚至8个字节。速度差异是相当大的！ - Steven Sudit
Bob的哈希非常快：http://www.azillionmonkeys.com/qed/hash.html - user7116
3

Hsieh哈希函数非常不错，作为C语言中的通用哈希函数，有一些基准测试/比较。根据您的需求（并不完全明显），您可能需要考虑使用cdb之类的东西。

3

为什么不直接使用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。
5
STL和Boost TR1都对字符串的哈希函数非常弱。 - obecalp
2

在这个之前的问题中有一些很好的讨论。

以及如何选择哈希函数的良好概述，以及有关几种常见哈希函数分布的统计数据在这里。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接