当你要查找用这种方式存储数据方式的元素时，通过哈希函数计算并在表中线性查找直到找到或者找到了空项即可停止。哈希表认为是环形表。比如，最后一个地址的下一个地址是第一个地址。 显然如果表快装满时，使用线性探查的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，依次类推，然后将这些结果相加得到一个数值。 通常构建一个好的哈希函数是比较困难的。大部分情况下你需要找一个既有一个好的性能同时又易于测试的方法。 这给我们提出一个问题，什么才是一个好的哈希函数呢？
一般而言，你想应用哈希函数的集合是庞大的，非常庞大的，但你想通过哈希函数得到结果集合是非常小的。也就是说，在hash(x)=y中，x的范围一般都非常大，y的范围非常小。比如，x可能是一个包含所有可能的10个字符的单词的集合，y在0到1023的范围内。想法是并不是所有的10个字符的单词都会真的出现——一般不会多于你可能留出的1024个存储位置。你想使用哈希函数，把输入的单词尽可能均匀的映射到1024个可能的值上——这可以最小化冲突概率。
所以一个好的哈希函数把输入尽可能无法预测的映射到输出中，也就是说，简言之它是一个可重复的随机查找函数。 哈希指纹
最初计算哈希值的目的，是为了找到某种存储与检索数据的方法，但是哈希有许多其他的用途。用哈希值来做标签就好像一个数据项的地址。
比如，假设我发给你一个重要数据文件，同时我告诉你 hash(data)
为1234，这里1234代表着实际情形中一个非常大的数字。现在假设你收到这个文件并将其保存为 data'。那么如果你计算同样的哈希函数： hash(data')
而且发现它等于2342，那么你就知道了，这个数据在它发送出去以后被修改了。
所以一个哈希值可以用来检测数据的变化。现在考虑一下，如果这个数据的哈希值计算等于1234，那么你能得出什么结论呢？
你只能得到的结论是，数据有很大的可能性没有变化。原因是哈希值是数据的指纹，而不止一批数据可以给出同样的指纹——也就是说，会有冲突。所以得到同样的指纹只是说明，如果不考虑变化可以带来相同的指纹数值，这个数据是好的。这里的关键问题在于，数据的改变得到同样的指纹这件事有多大的可能性，通常答案是这个可能性非常小。 用别的话来说，你非常有可能检测到数据的变化。
这就是为什么会经常会看到下载有MD5校验值。MD5是一种加密算法，即，高质量的哈希函数，它被用来计算指纹，而你可以用这个指纹来校验错误。
有趣的是MD5不是一个好的加密哈希函数。有些办法可以迅速的找到冲突，这些冲突可以被用来在保持指纹不变的情况下，对数据实施修改。
只需做一点点修改，哈希指纹的思想就可以变得安全，这样数据和指纹都可以安全的传送给某个人，而那个人接下来可以用这个指纹验证数据，校验数据是谁发出的。这就是数字签名的基本原理。 密码机制
哈希可用于标签数据，这个事实也是大多数在用密码系统的基础。其基本思想是，用户创建一个密码，系统存储该密码的哈希值。当用户登录系统的时候，对用户提供的密码应用哈希函数，如果它与存储的哈希值匹配一致，那么用户将被允许继续操作。
注意我们还是有常见的冲突问题——如果用户给出了错误的密码，又恰好能得到同样的哈希值，那么无论如何他们就登录了。 这个方案的一个很大的优势在于，即使攻击者获得了哈希值，他们也不能登录。他们需要的是生成这个哈希值的密码，而这是很难找到的。其原因是，虽然从一串密码生成这个哈希值很容易，但是从这个哈希值生成这串密码却很难。用其他话来说，hash(password)很容易计算，但是hash-1(value)很困难。
仅仅因为它很困难，并不意味着它是不可能的，所谓的密码破解者会使用大型计算机和GPU来进行反向计算。 |
