哪种哈希算法最适合唯一性和速度？

#1 楼

我测试了一些不同的算法，测量了速度和碰撞次数。

我使用了三种不同的键集：



216,553个英语单词列表arch存档（小写）
数字"1"至"216553"（请考虑邮政编码，以及不良哈希如何使msn.com com存档）
216,553“随机”（即4型uuid）GUID

记录每个语料库的碰撞次数和平均散列时间。

我测试了：


DJB2

DJB2a（使用xor而非+的变体）

FNV-1（32位）

SDBM
CRC32
Murmur2（32位）
SuperFastHash

结果

每个结果均包含平均哈希时间和碰撞次数

Hash           Lowercase      Random UUID  Numbers
=============  =============  ===========  ==============
Murmur            145 ns      259 ns          92 ns
                    6 collis    5 collis       0 collis
FNV-1a            152 ns      504 ns          86 ns
                    4 collis    4 collis       0 collis
FNV-1             184 ns      730 ns          92 ns
                    1 collis    5 collis       0 collis▪
DBJ2a             158 ns      443 ns          91 ns
                    5 collis    6 collis       0 collis▪▪▪
DJB2              156 ns      437 ns          93 ns
                    7 collis    6 collis       0 collis▪▪▪
SDBM              148 ns      484 ns          90 ns
                    4 collis    6 collis       0 collis**
SuperFastHash     164 ns      344 ns         118 ns
                   85 collis    4 collis   18742 collis
CRC32             250 ns      946 ns         130 ns
                    2 collis    0 collis       0 collis
LoseLose          338 ns        -             -
               215178 collis

注意：


LoseLose算法（其中hash = hash + character）为真可怕。一切都碰撞到相同的1,375个存储桶中
SuperFastHash速度很快，东西看起来很分散。我的天哪，数字冲突。我希望移植它的人出了点问题；很糟糕

CRC32很好。速度较慢，并有1k的查找表

是否真的发生冲突？

是的。我开始编写测试程序，以查看是否确实发生了哈希冲突-不仅仅是理论上的构造。它们确实确实发生了：

FNV-1碰撞



creamwove与quists碰撞


FNV -1a碰撞



costarring与liquid碰撞


declinate与macallums碰撞



altarage与zinke碰撞


altarages与zinkes碰撞



Murmur2碰撞





cataract与periti碰撞


roquette与skivie碰撞



shawl与stormbound碰撞


dowlases与tramontane碰撞


cricketings与twanger碰撞



longans与whigs碰撞



DJB2碰撞



hetairas碰撞mentioner


heliotropes碰撞neurospora


depravement碰撞与serafins


stylist碰撞与subgenera


joyful与synaphea碰撞


redescribed与urites碰撞


dram与vivency碰撞


DJB2a碰撞




haggadot与loathsomenesses碰撞


adorablenesses与rentability碰撞


playwright与snush碰撞


playwrighting与snushing碰撞
/>

treponematoses与waterbeds碰撞


CRC32冲突




codding与gnu碰撞


q 4312079q与exhibiters碰撞


SuperFastHash碰撞



schlager与dahabiah碰撞


drapability与encharm发生碰撞


enclave与grahams发生碰撞

... snip 79碰撞...

gramary与night发生碰撞


vigil与nights碰撞


vigils与finks碰撞



随机性

/>另一个主观衡量指标是散列的随机分布情况。映射生成的HashTables将显示数据分配的均匀程度。当线性映射表时，所有哈希函数都显示出良好的分布：



或作为希尔伯特映射（XKCD始终相关）：



除了对数字字符串（vinic，"1"，...，"2"）进行哈希处理（例如，邮政编码）时，在大多数哈希算法中，模式都开始出现：



DJB2a：



FNV-1：



除FNV-1a以外，所有这些对我来说仍然非常随机： br />



当我看"216553"“数字”图时，我认为我看到了微妙的垂直图案。有了Murmur，我根本看不到任何模式。您如何看待？




表中额外的Numbers表示随机性有多糟糕。 FNV-1a是最好的，而FNV-1a是最坏的： />
然后变成确保哈希函数具有足够的随机性。

FNV-1a算法

FNV1哈希包含返回32的变体，64、128、256、512和1024位哈希。FNV-1a算法为：

      Murmur2: .
       FNV-1a: .
        FNV-1: ▪
         DJB2: ▪▪
        DJB2a: ▪▪
         SDBM: ▪▪▪
SuperFastHash: .
          CRC: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
     Loselose: ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
                                        ▪
                                 ▪▪▪▪▪▪▪▪▪▪▪▪▪
                        ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪
          ▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪▪

其中常数*和FNV-1a取决于您想要的返回哈希大小：

hash = FNV_offset_basis
for each octetOfData to be hashed
    hash = hash xor octetOfData
    hash = hash * FNV_prime
return hash

有关详细信息，请参见FNV主页。

我所有的结果都是32位位变体。

FNV-1比FNV-1a好吗？

否。 FNV-1a的状况更好。使用英文单词corpus时，与FNV-1a的冲突更多：

Hash Size  
===========
32-bit
    prime: 2^24 + 2^8 + 0x93 = 16777619
    offset: 2166136261
64-bit
    prime: 2^40 + 2^8 + 0xb3 = 1099511628211
    offset: 14695981039346656037
128-bit
    prime: 2^88 + 2^8 + 0x3b = 309485009821345068724781371
    offset: 144066263297769815596495629667062367629
256-bit
    prime: 2^168 + 2^8 + 0x63 = 374144419156711147060143317175368453031918731002211
    offset: 100029257958052580907070968620625704837092796014241193945225284501741471925557
512-bit
    prime: 2^344 + 2^8 + 0x57 = 35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759
    offset: 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785
1024-bit
    prime: 2^680 + 2^8 + 0x8d = 5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573
    offset: 1419779506494762106872207064140321832088062279544193396087847491461758272325229673230371772250864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915

现在比较小写和大写：

Hash    Word Collisions
======  ===============
FNV-1   1
FNV-1a  4

在这种情况下，FNV-1a不会比FN-1差“ 400％”，而仅比FN-1差20％。

我认为更重要的一点是，有两类关于碰撞的算法：




罕见的碰撞：FNV-1，FNV-1a，DJB2，DJB2a，SDBM

常见的碰撞：SuperFastHash，Loselose

然后是散列的均匀分布方式： SuperFastHas

优秀的发行版：FNV-1

良好的发行版：SDBM，DJB2，DJB2a



可怕的发行版：Loselose

>
更新

杂音？当然，为什么不呢？


更新

@whatshisname想知道CRC32的性能如何，在表中添加数字。

CRC32是非常好。很少有冲突，但是比较慢，并且有一个1k查找表的开销。将使用FNV-1a作为我的事实上的哈希表哈希算法。但是现在我切换到Murmur2了：用我发现的DJB2x算法；

更新：在Google的MurmurHash3主页上：


（1）-SuperFastHash的碰撞特性非常差


所以我想不只是我。

更新：我意识到为什么FNV_offset_basis比其他的更快。 MurmurHash2一次操作四个字节。大多数算法都是逐字节的：

Hash    lowercase word Collisions  UPPERCASE word collisions
======  =========================  =========================
FNV-1   1                          9
FNV-1a  4                          11

这意味着随着键的变长，Murmur会闪耀。更新

GUID被设计为唯一的，而不是随机的

Raymond Chen的及时帖子重申了一个事实，即“随机” GUID并非旨在用于其随机性。它们或它们的子集不适合作为哈希键：


即使第4版GUID算法也不保证是不可预测的，因为该算法未指定随机数生成器的质量。 Wikipedia上有关GUID的文章包含初步研究，该研究表明可以基于对随机数生成器状态的了解来预测将来和以前的GUID，因为生成器的密码学能力不强。


Randomess是与避免碰撞不同；这就是为什么通过采用“随机” guid的一些子集来尝试发明自己的“哈希”算法将是一个错误的原因：

for each octet in Key
   AddTheOctetToTheHash

注意：同样，我将“ random GUID”用引号引起来，因为它是GUID的“ random”变体。更准确的描述是FNV_prime。但没人知道类型4或类型1、3和5是什么。因此，将它们称为“随机” GUID会更容易。

所有英语单词的镜像


https://web.archive.org/web/20070221060514/ http://www.sitopreferito.it/html/all_english_words.html
https://drive.google.com/file/d/0B3BLwu7Vb2U-dEw1VkUxc3U4SG8/view?usp=sharing

#2 楼

如果您希望通过不变的字典创建哈希映射，则可以考虑使用完美的哈希https://en.wikipedia.org/wiki/Perfect_hash_function-在构造哈希函数和哈希表期间，您可以保证，对于给定的数据集，将不会发生冲突。

#3 楼

这是哈希函数的列表，但简短的版本是：如果您只是想拥有一个好的哈希函数，并且迫不及待，djb2是最好的字符串哈希函数之一我知道。它在许多不同的键和表大小集上具有出色的分布和速度

unsigned long
hash(unsigned char *str)
{
    unsigned long hash = 5381;
    int c;

    while (c = *str++)
        hash = ((hash << 5) + hash) + c; /* hash * 33 + c */

    return hash;
}

#4 楼

Google的CityHash是您要寻找的算法。它不利于加密，但有利于生成唯一的哈希。
阅读博客以获取更多详细信息，并且代码可在此处获取。还有一个普通的C端口。
关于32位支持：

所有CityHash函数都针对64位处理器进行了调整。也就是说，它们将以32位代码运行（使用SSE4.2的新版本除外）。他们不会很快。您可能想在32位代码中使用Murmur或其他内容。

#5 楼

在对文件进行哈希处理时，我已经绘制了不同哈希算法的简短速度比较。

由于所有文件都存储在tmpfs中，因此各个图仅在读取方法上略有不同，在此处可以忽略。因此，如果您想知道，基准测试就不受IO限制。


线性标度

对数标度

算法包括：SpookyHash, CityHash, Murmur3, MD5, SHA{1,256,512}。

结论：


像Murmur3，Cityhash和Spooky这样的非加密哈希函数非常接近。应该注意的是，在具有SSE 4.2s CRC指令的CPU上，Cityhash可能更快，而我的CPU没有。在我的情况下，SpookyHash总是比CityHash早一点。
虽然使用SHA256可以更安全地抵御MD5和SHA1的冲突漏洞，但在使用加密哈希函数时，MD5似乎是一个不错的选择。
所有算法都是线性的-这真的并不奇怪，因为它们是逐块工作的。 （我想看看读取方法是否有所不同，所以您可以比较最右边的值。）
SHA256比SHA512慢。
我没有研究哈希函数的随机性。但这是Ian Boyds答案中缺少的哈希函数的很好的比较。
这指出CityHash在极端情况下存在一些问题。

用于绘图的源：



https://github.com/sahib/rmlint/tree/gh-pages/plots（不好意思的代码）

#6 楼

我知道有类似SHA-256之类的东西，但是这些算法的设计是安全的，通常意味着它们比不那么独特的算法要慢。


密码散列函数更独特的假设是错误的，实际上，在实践中可以证明它经常倒退。实际上：


加密散列函数在理想情况下应该与随机变量没有区别；
但是对于非加密散列函数，希望它们与可能的输入进行良好交互。
/>
这意味着，非加密哈希函数的冲突可能要比针对“良好”数据集（针对其设计的数据集）的加密冲突少。

我们可以用伊恩·博伊德（Ian Boyd）的答案中的数据和一些数学运算来证明这一点：生日问题。如果从集合n中随机选择[1, d]个整数，则碰撞对的预期数目的公式是（摘自Wikipedia）： n = 2 ^ 32我们得到约5.5个预期的碰撞。伊恩（Ian）的测试大多显示该邻域周围的结果，但有一个戏剧性的例外：大多数函数在连续数字测试中的碰撞次数为零。随机选择216,553个32位数字并获得零冲突的可能性约为0.43％。那只是一个函数，这里有五个零碰撞的不同哈希函数系列！

因此，我们在这里看到的是，Ian测试的哈希与连续数字数据集交互良好，即，与理想的密码哈希函数相比，它们将最小的不同输入散布得更广泛。 （旁注：这意味着Ian可以从他自己的数据中驳斥Ian的图形评估，即FNV-1a和MurmurHash2在number数据集中对他“看起来是随机的”。对于该大小的数据集，对于两个哈希函数，零冲突，绝对是非随机的！）

这不足为奇，因为这对于哈希函数的许多使用而言是理想的行为。例如，哈希表键通常非常相似。伊恩（Ian）的答案提到了邮递区号哈希表曾经存在的MSN问题。这是在避免可能的输入上的冲突胜过类似随机行为的情况下使用的。

这里的另一个有启发性的比较是CRC和加密哈希函数在设计目标上的对比：


CRC旨在捕获由嘈杂的通信通道引起的错误，这些错误可能是少量的位翻转；
加密散列旨在捕获由恶意攻击者进行的修改，这些攻击者被分配有限的计算

因此，对于CRC来说，在最小限度不同的输入中具有比随机产生的冲突少的冲突还是很好的。使用加密哈希，这是一个禁忌！

#7 楼

SHA算法（包括SHA-256）的设计速度很快。

实际上，它们的速度有时会成为问题。特别是，存储密码派生令牌的常用技术是运行标准快速哈希算法10,000次（将哈希值的哈希值存储在...密码的哈希值中）。

#!/usr/bin/env ruby
require 'securerandom'
require 'digest'
require 'benchmark'

def run_random_digest(digest, count)
  v = SecureRandom.random_bytes(digest.block_length)
  count.times { v = digest.digest(v) }
  v
end

Benchmark.bmbm do |x|
  x.report { run_random_digest(Digest::SHA256.new, 1_000_000) }
end

输出：

Rehearsal ------------------------------------
   1.480000   0.000000   1.480000 (  1.391229)
--------------------------- total: 1.480000sec

       user     system      total        real
   1.400000   0.000000   1.400000 (  1.382016)

#8 楼

使用SipHash。它具有许多理想的属性：


快速。一个优化的实现每个字节大约需要1个周期。

安全。 SipHash是强大的PRF（伪随机函数）。这意味着它与随机函数是没有区别的（除非您知道128位密钥）。因此：


不必担心哈希表探针由于冲突而变成线性时间。借助SipHash，您知道无论输入什么，都将获得平均情况下的平均性能。
不受基于散列的拒绝服务攻击的影响。
您可以使用SipHash（尤其是具有128-位输出）作为MAC（消息验证码）。如果您收到一条消息和一个SipHash标记，并且该标记与使用您的密钥运行SipHash的标记相同，则您知道创建哈希的人也都拥有您的密钥，并且消息和密钥此后，哈希值已更改。

#9 楼

这取决于您要散列的数据。一些散列可以更好地处理特定数据，例如文本。专门设计了一些哈希算法以适合特定数据。

Paul Hsieh曾经进行了快速哈希。他列出了源代码和说明。但是它已经被击败了。 :)

#10 楼

Java使用以下简单的乘法和加法算法：


String对象的哈希码计算为

 s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1]

使用int算术，其中s[i]是字符串的第i个字符，n是字符串的长度，而^表示取幂。 （空字符串的哈希值是零。）


那里可能有更好的方法，但这是相当普遍的，并且似乎在速度和唯一性之间进行了很好的权衡。 。

#11 楼

首先，为什么需要实现自己的哈希？对于大多数任务，假设有可用的实现，您应该使用标准库中的数据结构获得良好的结果（除非您只是为了自己的学习而这样做）。

就实际的哈希算法而言，我个人最喜欢的是FNV。 1

这是C语言中32位版本的示例实现：

unsigned long int FNV_hash(void* dataToHash, unsigned long int length)
{
  unsigned char* p = (unsigned char *) dataToHash;
  unsigned long int h = 2166136261UL;
  unsigned long int i;

  for(i = 0; i < length; i++)
    h = (h * 16777619) ^ p[i] ;

  return h;
}