英文原文：Hashing - The Greatest Idea In Programming

尽管这个观点仁者见仁智者见智，虽然你不能够对其提供帮助，但你应该钦佩hash函数这一思想。它不仅仅能够解决基本的计算问题——查找存储数据，也可以帮助检测文件篡改，密码安全等诸多问题。

一个基本的计算问题是查找所存储的数据。

例如，如果让你维护一个名字和电话号码的表，你该怎么组织这个表，以便你可以能够根据指定名字查找电话号码？

最显而易见的解决方案就是按照字母顺序保持列表的顺序，并使用某种形式的搜索，通常是二进制，来定位名字。这非常有效，但这只对保持严格顺序的列表有用。

如果添加名字和电话号码的频率很少，那么你可以使用一个不保持顺序的溢出表（overflow table）。然后你可以在排序表上进行字节搜索来检索名字，如果你没有找到该名字，在溢出表上进行线性搜索可以找到该名字或者确认该名字是否为未知。

以这种方式使用溢出表只需要保持溢出表的简短。如果你添加了大量名字，那么溢出表的线性查找的时间中将会迅猛增长。在这种情况下，是时候该考虑使用哈希了。

哈希是一种伟大的计算思想，每个程序员都应该对其有所了解。哈希的基本思路非常简单，事实上，它是如此的简单，你可以花时间来考虑它的魔力是从哪里来的。

假设你有这样一个函数: 
hash(name)

该函数根据输入的名字，通过一些计算法则返回区间[1,N]中的某个数值，那么为什么不将名字和电话号码存储在表的第 hash(name)位置呢。

注意哈希函数有点小奇特，它必须是完全确定性的。按理说就是对于你输入的同一名字，哈希函数始终返回相同的数值，而每个不同的名字则应返回不同的固定值。正如你所料这种特性并不总是能满足的。

使用这种方案，在表中查找名字，实际仅就是计算 hash(name)的值，然后在这个值标识的 表中的那个位置 去看看你要查的名字是不是存储在那了。

是的，这就是关于hash的全部，尽管还有一些其他的实用细节，但其核心思想就是 用 hash(name)来确定名字在表中的存储地址

一个例子

为了消除对‘哈希到底有多简单’的疑惑， 让我们看一个小小的例子。
 
如果哈希函数是：名字前两个字母的asc码值之和 减去128，也就是：

hash(ABCDE)=ASC(A)+ASC(B)-128 

其中ASC返回字母的asc编码值,那么名字"JAMES"将被存储在：

hash("JAMES") =  ASC("J")+ASC("A")-128

这个地址，说白了就是表中的第11个地址处。

现在如果你想知道你是否有JAMES的电话，那简单了，计算hash("JAMES")然后就去表中的第11个地址处看看有没有电话号码就行了。

不必排序，不必搜索，只要计算一下这个hash函数，你就知道在哪里存储和找到数据。

核心思想就是哈希函数接收文本或任何类型的数据然后输出基于这些数据的一组数值。



这是大部分编程语言实现高级数据结构的方式，或与哈希类似的方式，像字典结构就是用哈希实现的。

例如Python中的字典对象就是用哈希表实现的。所以即使你没有显示的构造一个哈希表，你也有可能就在用着它了。

冲突

现在有一个具体的例子来看看我们一开始会遇到的一些问题。尤其是我们的哈希函数将JAMESON的电话号码存在哪里了？

是的，你已想到我们将JAMES也存储在同一个地方了。所以很清楚，怎样设计哈希函数是很重要的。事实上，很难给你演示不管你如何努力去解决冲突问题，诸如JAMES和JAMESON的问题依然会出现。

一个好的哈希函数是尽可能的通过存储表将数据分散开来--因此一个叫分散存储技术出现了--但冲突任然会发生。

有两种方式来解决冲突问题--链接地址和开放地址。

链接地址是早期提出的可以适应溢出方法的方式。如果你用哈希函数计算的地址已经被占用，那么一个存储关键字的溢出表将产生，然后在主哈希表的占位地址指向这个溢出表。如果有更多的冲突发生，这些关键字项将存储于溢出表，并用指针指向这个新添的数据项，所有这些溢出表链将共有一个哈希值。

现在当你要查找或存储时，你需要线性的操作溢出表链接，但这样，更多的冲突就不会发生了。链接地址法的问题就是需要额外的空间和指向这控件的指针。

开放地址也是一种选择。开放地址最简单的方法命名很有趣，叫做“线性探针”。如果你要存储一个元素但发现哈希函数计算的地址已经被占用，那么就继续找到下一个没有被占用的地址，然后将元素存储到这个地址。这样的结果保证了所有元素都是在哈希表中是线性存储的。

当你要查找用这种方式存储数据方式的元素时，通过哈希函数计算并在表中线性查找直到找到或者找到了空项即可停止。哈希表认为是环形表。比如，最后一个地址的下一个地址是第一个地址。

显然如果表快装满时，使用线性探查的hashing看起来很像一个简单的无序表的线性搜索！实际上，只要表不超过75%，线性探查的效果比较好。

另一个线性探针的选择是双hashing。在线性探查中，搜索的位置通过hash(name)+n，n为0,1,2,3...来确定。线性探查的问题是初始的hashing函数把数据“分散”到表中，但之后数据间的线性步进把数据集合在一起。这更像是把数据“弄成一团”而不是分散的放入表中。

一个好的方法是用两个哈希函数--一个是计算哈希表位置，另一个是用于分散冲突。hash(名称)+n*hash2(名称),n取值0，1，2，3...，其中hash2是第二个哈希函数。慎重考虑第二个函数可以节省查找时间。

现在我来描述一下怎样才能将第二个函数设计好，但我不得不承认除非内存短缺，通常用线性探针的方法会比用双哈希函数让哈希表更容易变大。关键的有效方法是把哈希表填满，如果哈希表只用了50%，即使是用复杂的双哈希函数也不会有更好的效果。

什么才是好的哈希函数

大多数哈希函数都是通过和哈希表大小N取余运算的方式。

这种方式得到的结果就是在0和N-1之间，这种结果比较合适，但如果N是一个素数，它可以更好的在表中分散数据。当然，如果你想哈希一个字串，首先你得将其转换为一个适当的数字，一个如例子中的简单方案是不行的。

你需要给每一可能的字串产生一个不同的数字，如果将字串前两个ASCII字符的值相加显然是不行的。一个更好的方法是将每一个字母的ASCII码值和不同数字相乘，第一个字母乘1，第二个乘10.第三个乘100，依次类推，然后将这些结果相加得到一个数值。
通常构建一个好的哈希函数是比较困难的。大部分情况下你需要找一个既有一个好的性能同时又易于测试的方法。

本文中的所有译文仅用于学习和交流目的，转载请务必注明文章译者、出处、和本文链接。 2KB翻译工作遵照 CC 协议，如果我们的工作有侵犯到您的权益，请及时联系我们。

2KB项目（www.2kb.com，源码交易平台）,提供担保交易、源码交易、虚拟商品、在家创业、在线创业、任务交易、网站设计、软件设计、网络兼职、站长交易、域名交易、链接买卖、网站交易、广告买卖、站长培训、建站美工等服务