hashing

The most important techniques behind Yahoo! are: hashing, hashing and hashing!

——前雅虎首席科学家Udi Manber

 

计算机科学中的一类基本问题是如何在内存中找到一段指定的信息（a “key”），这类问题常常被称为字典问题（dictionary  problem）。对这类问题可以提出很多解决方案，但考虑的关键因素之一就是：如何在数据量快速增长的同时仍然保证查找的速度。Hashing就是满足这个条件的一种高效解决方案。

 

在解释hashing之前先来看一看key这个概念。根据NIST的定义，key是一组数据中的一部分，通过这部分信息来存储、索引整组信息。比如如果要给一组客户记录排序，就可以将客户姓名选作key，从而根据姓名按照字典序排列。这里要注意的一点是，key的选择不是绝对的，在不同的应用场合下，对同一组信息可能选择不同的key。例如，如果要将上面提到的客户记录作成财务汇报，那么key就可以选作客户的交易金额，从而根据交易金额进行排序。

 

Key的取值范围通常很大并且分布不均，哈希函数的目的就是将key映射到分布相对均匀且较小的整数集合。从很大的集合到较小的集合，从分布不均到分布均匀，这是哈希函数的两个基本特点。对于哈希函数的使用者来说，哈希函数既有随机性，又有确定性。随机性是指给定一个key，哈希函数的使用者完全不能预测这个key到底会被映射到哪个整数；确定性是指给定一个key，同一个哈希函数总会将它映射到同一个整数。

 

哈希函数的随机性保证了其对输入key的加密特性。通常情况下，哈希函数的输出值能够唯一标识输入的key，因此就像现实世界中的“指纹”能够唯一标识一个人一样，哈希函数的输出值也被叫做“数字指纹”（digital fingerprint）。当然，这只是哈希函数期望达到的境界，理论上由于哈希函数将大集合映射到了小集合，碰撞的可能一定存在。最近，山东大学的王小云教授（已经被挖到了清华）就破解了国际上流行的MD5和SHA-1两大哈希算法，在密码界引起了轩然大波。实际上，破解的过程就是进行碰撞攻击（collision attack），从而找到两个key映射到同一输出值的情况，这样就可以伪造数字指纹。

 

哈希函数的输出值能够唯一标识一个key，这本身就反映了哈希函数的确定性。在哈希表中，哈希函数被用来生成key的存储地址，正是由于确定性的存在，使得存储后的查找成为可能。哈希表最大的特点，就是它不随数据量的增大而速度变慢，因为记忆数据存储位置的任务交给了哈希函数。每一次查找数据的时间都是恒定的，即哈希函数的计算时间（不考虑碰撞的情况下）。这里我们可以看到哈希函数另一大作用：作为存储信息的载体。

 

如果我们想记录某个集合的哈希表地址，一般情况下我们会考虑将这个集合的哈希表地址存储在内存中，这无疑要消耗大量的空间，而且常常不可实现。在计算机科学中，时间换空间的情况经常发生，这里再一次印证了这个观点。为了不占用内存，我们设计合适的哈希函数来存储地址信息，在需要新的地址时，通过占用一定的CPU时间算出新地址。如同不同的情况下存储模式不同一样，在不同的应用场合中，也需要设计满足特定要求的哈希函数。例如，密码学中的哈希算法更多地考虑如何躲避恶意的攻击和伪造，而用在检错和纠错领域的哈希算法则更多地考虑如何将改动过的数据区分开来。具体的哈希算法会在后面介绍，这里就不多讲了。