Dav*_*idD 27 hash crc32 sse intel
鉴于SSE 4.2(Intel Core i7和i5部分)包含CRC32指令,研究是否可以构建更快的通用散列函数似乎是合理的.根据这个,只有16位CRC32均匀分布.那么还有什么其他转变才能克服这个问题呢？
更新 怎么样？只有16位适合散列值.精细.如果你的桌子是65535或更低,那么很棒.如果不是,则通过Nehalem POPCNT(填充计数)指令运行CRC值以获得设置的位数.然后,将其用作表数组的索引.如果您的表位于1mm条目以南,则此方法有效.我敢打赌,性能最好的哈希函数更便宜/更快.现在GCC 4.5有一个CRC32内在它应该很容易测试...如果我有丰富的业余时间来处理它.
大卫
mjv*_*mjv 17
重访,2014年8月Arnaud Bouchez在最近的评论中
提示,鉴于其他答案和评论,我承认原来的答案需要改变或者最不合格.我最后离开原来的,作为参考.
首先,也许是最重要的,问题的公平答案取决于哈希码的预期用途:"好"[哈希函数...]的含义是什么？哈希在哪里/如何使用？(例如,它是否用于散列相对较短的输入键？它是用于索引/查找目的,产生消息摘要还是其他用途？所需的哈希码本身有多长,所有32位[CRC32或其衍生词],更多位,少...等？
的OP问题,呼吁" 一个更快的 通用散列函数 ",所以重点是速度(东西少CPU密集型和/或一些东西,可以利用各种性质的并行处理).我们在这里可能会注意到,哈希代码本身的计算时间通常只是哈希应用中问题的一部分(例如,如果哈希码的大小或其内在特征导致许多冲突,需要额外的周期来处理对于"通用"的要求也留下了许多关于可能用途的问题.
考虑到这一点,一个简短而好的答案可能是:
是的,CRC32C在较新的英特尔处理器上的硬件实现可用于构建更快的哈希码; 但要注意,取决于散列的具体实现及其应用,由于冲突的频率,总体结果可能是次优的,需要使用更长的代码.此外,当然,应仔细审查散列的加密用法,因为CRC32算法本身在这方面非常弱.
最初的答案引用了Bret Mulvey关于评估Hash函数的文章,并且正如Mdlg的回答所指出的那样,本文的结论在CRC32方面是错误的,因为CRC32的实现基于错误/缺陷.尽管有关CRC32的这一重大错误,但本文一般为哈希算法的属性提供了有用的指导.这篇文章的URL现已不存在了; 我在archive.today上发现了它,但我不知道作者是否在其他地方有它,以及他是否更新了它.
这里的其他答案引用CityHash 1.0作为使用CRC32C的哈希库的示例.显然,这在一些较长(超过32位)的哈希码的上下文中使用,但不用于CityHash32()函数本身.此外,与为生成哈希码而执行的所有移位和混洗以及其他操作相比,City Hash函数对CRC32的使用相对较小.(这不是对CityHash的批评,因为我没有实际操作经验.我会粗略地回顾一下CityHash功能产生良好的源代码,例如分布式代码,但速度并不快比其他各种哈希函数.)
最后,您还可以在关于SO的准重复问题中找到关于此问题的见解.
原始答案和编辑(2010年4月)
先验,这听起来像个坏主意!.
CRC32 不是为散列目的而设计的,它的分布可能不均匀,因此使其成为相对较差的哈希码.此外,它的"加扰"功率相对较弱,导致非常差的单向散列,如加密应用中所使用的那样.
[BRB:我正在寻找这种效果的在线参考...]
谷歌的第一个[keywords = CRC32发行版]似乎证实了这一点:
评估CRC32的哈希表
编辑:上面引用的页面,实际上完整的文章提供了在Hash函数中查找内容的良好基础.
阅读[快速]本文,确认了一般性的说法,即一般来说 CRC32不应该用作哈希值,并且根据哈希的具体目的,可能至少部分地使用CRC32作为哈希值哈希码.
例如,CRC32代码的较低(或更高,取决于实现)16位具有相对均匀的分布,并且假设一个人不关心散列码的加密属性(即,例如类似的密钥的事实)如果产生非常相似的代码,则有可能构建一个哈希码,该哈希码使用例如对于用原始密钥的两半(或任何除法)产生的两个CRC32码的较低[或更高] 16位的串联.
需要运行测试以查看相对于替代散列函数的内置CRC32指令的效率是否会使得调用指令两次并将代码拼接在一起等的开销不会导致整体功能较慢.
Mdl*_*dlg 14
其他答案中提到的文章根据错误的crc32代码得出了错误的结论.Google的排名算法尚未根据科学准确性进行排名.
与所提到的文章"为哈希表评估CRC32"结论相反,CRC32和CRC32C对于哈希表的使用是可接受的.作者的示例代码在crc32表生成中有一个错误.修复crc32表,使用相同的方法得到令人满意的结果.此外,CRC32指令的速度使其成为许多环境中的最佳选择.使用CRC32指令的代码在峰值时比最佳软件实现快16倍.(注意CRC32与intel指令实现的CRC32C不完全相同.)
CRC32显然不适合加密使用.(32位是蛮力的笑话).