尽管这个观点仁者见仁智者见智，虽然你不能够对其提供帮助，但你应该钦佩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中的字典对象就是用哈希表实现的。所以即使你没有显示的构造一个哈希表，你也有可能就在用着它了。
有两种方式来解决冲突问题--链接地址和开放地址。
链接地址是早期提出的可以适应溢出方法的方式。如果你用哈希函数计算的地址已经被占用，那么一个存储关键字的溢出表将产生，然后在主哈希表的占位地址指向这个溢出表。如果有更多的冲突发生，这些关键字项将存储于溢出表，并用指针指向这个新添的数据项，所有这些溢出表链将共有一个哈希值。
现在当你要查找或存储时，你需要线性的操作溢出表链接，但这样，更多的冲突就不会发生了。链接地址法的问题就是需要额外的空间和指向这控件的指针。
开放地址也是一种选择。开放地址最简单的方法命名很有趣，叫做“线性探针”。如果你要存储一个元素但发现哈希函数计算的地址已经被占用，那么就继续找到下一个没有被占用的地址，然后将元素存储到这个地址。这样的结果保证了所有元素都是在哈希表中是线性存储的。
当你要查找用这种方式存储数据方式的元素时，通过哈希函数计算并在表中线性查找直到找到或者找到了空项即可停止。哈希表认为是环形表。比如，最后一个地址的下一个地址是第一个地址。
显然如果表快装满时，使用线性探查的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来进行反向计算。
工作证明
在更不寻常的哈希用法中，有一种思想是比特币的工作证明算法。在这种场景下，有一块数据需要发布，在服务器声称验证该事务之前，它必须找到一个数据项(译注：也称为验证码，该计算生成block过程被称为“挖金矿”，因为计算会得到一定的奖励)，这个数据项加到这个数据块的时候，采用的是其哈希值，且其中含有一个给定数目的零。由于逆向计算哈希函数不容易，唯一的办法就是加上估计数据，并计算哈希值，直到结果具有给定数目的零。这个过程需要时间，这也意味着非常有可能只有一个服务器最先找到这个结果——这样就避免了多个服务器验证这个数据块的问题。
锦上添花的是，这个算法面临着更优异的硬件性能。它包括，通过测量解决哈希问题的平均时间来给出反馈，以及根据需要来增加额外的零。你可以证明，找到一些数据加给这个数据块，然后在哈希算法中得出n个零，其中需要的时间随n呈指数级变化。用其他话来说，这个问题的难度是可以变化的，可以以此来保持需要的时间大致相同。
一旦这个问题被解决，数据块声明有效，结果数据将被附加到这个数据块，如果没有证明这个哈希值（防止事务被篡改的哈希值）是无效的，在此之后，这个数据块中包含的数据将不能被改变。
算法中的哈希函数
哈希函数还有很多种用法可以来加速算法。举个例子，如果你需要剔除大小为N的集合中的重复记录，你可能会疲于比较每一对可能的数据，即大约N2/2次比较，否则你最好对表格进行排序。一个替代的方法是，计算所有记录的哈希值，并将指向每个记录的指针存储于一个哈希表。这样重复的记录就是表中的冲突记录。
你还可以用具有附加属性的哈希函数来实现匹配算法。如果你可以发明一种哈希函数，将你认为相似的数据，映射为相近的哈希值，那么你就可以不仅用哈希来查找副本，即相等的数值，也可以用来查找相近的数值。这个方法在字符串匹配，声音匹配，甚至是模式识别中，都非常重要。
有很多非常聪明的算法使你能用快速和简单的方式检查数据间的不等性。一个基本的原则就是，如果两个对象的哈希值不同，那么他们不可能为同一事物，也就是不相等的。
你可以用 Bloom filter 的例子做检验.
相关文章 Advanced Hashing高级哈希 The Bloom Filter Bloom过滤 The Invertible Bloom Filter 可逆Bloom过滤 Universal Hashing全域散列 Storage Mapping Functions 存储映射函数 Inside Bitcoin - virtual currency深入比特币-虚拟货币
Assemblers and assembly language 编译器和汇编语言 | 
