快速串散列算法与32位整数低碰撞率[关闭](Fast String Hashing Algorith

我有很多的，我想做快速搜索针对无关命名的东西。一个“土豚”始终是一个“土豚”无处不在，因此散列字符串和重用整数将工作做好，加快比较。名整组是未知的（和随时间变化）。什么是一个快速的字符串哈希算法，将产生小（32或16）位价值和具有较低的碰撞率？

我想看到专门针对C / C ++优化的实现。

Answer 1:

其中的FNV变种应该满足你的要求。他们速度快，并产生相当均匀地分布输出。

Answer 2:

杂音哈希是相当不错的。

Answer 3:

对于一个固定的字符串设定使用的gperf。

如果字符串设定的改变，你必须选择一个哈希函数。在这之前的话题已经讨论：

什么是使用的hash_map当一个STL字符串，用最好的哈希算法？

Answer 4:

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

詹金斯的一在一次一个散列字符串应该是这个样子：

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

Answer 5:

另一种解决方案可能是更好的根据您的用例是实习字符串 。这是符号是如何工作的，例如在Lisp中。

一个实习串是一个字符串对象，其值是实际的串的字节的地址。所以，你在全局表检查创建一个实习的字符串对象：如果字符串就在那里，你初始化字符串实习该字符串的地址。如果没有，你将它插入，然后初始化字符串实习。

这意味着，从相同的字符串建立了两个实习字符串将具有相同的价值，这是一个地址。所以，如果N是在系统实习串的数量，特点是：

慢施工（需要查找和可能的存储器分配）
需要并发线程的情况下，全球数据和同步
比较是O（1），因为你比较地址，而不是实际的字符串字节（这意味着排序的作品很好，但它不会是一个字母排序）。

干杯，

卡尔

Answer 6:

你为什么不只是使用Boost库？他们的哈希函数是使用简单，大部分在促进东西很快就会成为C ++标准的一部分。其中一些已经是。

升压哈希值是一样简单

#include <boost/functional/hash.hpp>

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

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

你可以找到提升boost.org

Answer 7:

这是从来没有一个好题材晚，我相信人们会感兴趣我的发现。

我需要一个散列函数，并阅读这篇文章，并做了一些对这里给出的链接研究，我想出了丹尼尔·J·伯恩斯坦的算法，这是我用来做了一个有趣的试验的这种变化：

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

这种变化哈希字符串忽略大小写，这符合我的需要散列用户的登录凭据。 “釜”是西班牙的“关键”。我很遗憾的西班牙语，但它的我的母语和编写程序就可以了。

好吧，我写了一个程序，将产生从“test_aaaa”到“test_zzzz”的用户名，并 - 使longer-我加入到他们随机域在此列表中的字符串：“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 and so on.

下面是测试-'Colision恩特雷里奥斯XXX XXXÝ”装置‘碰撞XXX XXX和的’的输出。 “PALABRAS”装置“单词”和“总计”是在两种语言 - 是相同的。


    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

这是不坏，11个碰撞出的456976（关闭当然使用完整的32位作为表lenght）。

运行使用5个字符的程序，也就是从“test_aaaaa”到“test_zzzzz”，实际上运行的内存建表。下面是输出。 “否干草MEMORIA第insertar XXXX（insertadas XXX）”是指“没有存储器左插入XXX（XXX插入）”。基本上的malloc（）失败，在这一点上。


    No hay memoria para insertar 'test_epjcv' (insertadas 2097701).

    Buscando Colisiones...

    ...451 'colision' strings...

    Total de Colisiones: 451
    Total de Palabras  : 2097701

这意味着在2097701串只是451的碰撞。请注意，在没有任何场合，有每个代码2间以上的碰撞。我确认这对我来说是一个伟大的哈希值，因为我需要的是到登录ID转换为索引的40位唯一ID。所以，我用它来登录凭据转换为32位散列，并使用额外的8位处理高达每码255次碰撞，这在lookign测试结果将是几乎不可能产生。

希望这是有用的人。

编辑：

像测试盒是AIX，我运行它使用LDR_CNTRL = MAXDATA = 0x20000000给它更多的内存，它运行的时间更长，结果在这里：

碰撞寻找...共冲突：2908个总字数：5366384

这是2908以后5366384次尝试！

非常重要 ：与-maix64编译程序（因此无符号长为64位），冲突的数目为0，所有的情况下!!!

Answer 8:

看看GNU 的gperf 。

Answer 9:

在谢哈希函数是相当不错的，并且具有一定的基准测试/对比，因为根据你想要什么C.一般散列函数（它不是完全明显），你可能要考虑像国开行代替。

Answer 10:

鲍勃·詹金斯有许多可用的散列函数，所有这一切都是速度快，低碰撞率。

Answer 11:

你可以看到.NET使用上使用反射的String.GetHashCode（）方法。

我会大胆地猜测，微软花了大量时间优化这一点。他们印制所有MSDN文档中太，这是如有变更，所有的时间。所以很明显这是他们的“表演扭捏雷达” ;-)

将变得非常简单地移植到C ++太我还以为。

Answer 12:

有这一些很好的讨论前一个问题

以及如何选择散列函数，以及统计信息的几种常见的分布很好的概述这里

Answer 13:

这里介绍的是自己实现它的一个简单的方法： http://www.devcodenote.com/2015/04/collision-free-string-hashing.html

从后一个片段：

如果说，我们有一个字符集的大写英文字母，则该字符集的长度为26，其中A可以由数字0来表示，B由数字1，C由2号等等，直到由数Z 25.现在，每当我们要映射这个人物设定为一个唯一的数字串，我们执行相同的转换，因为我们没有在二进制格式的情况下，

Answer 14:

CRC-32 。有对谷歌大约一万亿链接它。

文章来源: Fast String Hashing Algorithm with low collision rates with 32 bit integer [closed]