算法第三讲哈希（hashing)

首先明白哈希表[1]，在wiki(en)中定义为：根据键值（key）而直接访问的数据结构。哈希表通过一个hash function把key映射到表中一个位置来加快查询的速度。

举一个简单的例子：现在有0-10这11个位置或者slots。有54、26、93、17、77、33这6个数。定义一个哈希函数为(h(item) = item % 11)。这6个数会被映射到10、4、5、6、0、9这6个位置。当问item这个数是否在集合中时，只需要计算h(item)，找到位置，比较位置上数。复杂度O(1)。[2]

在哈希中会提到的一个概念：冲突。映射后，不同的item有相同的h(item)，那对于有冲突的key，就不能做到直接访问[3]。

解决冲突的方法之一[4]：每个slot中不是存放一个item，而是存放一个item的集合。

目录

哈希算法 - md5、sha-1

在密码学中或者在做web开发中，经常提到的md5、sha1其实也都是哈希算法。经常用它们生成等长的字符串作为校验值，验证消息的完整性。

注[1]: hash table叫哈希表、散列表

注[2]: 除了例子中取余数的方式外，还有folding method、mid-square method等。

  • folding method方法将item划分为等大的块，将各个块加一起后经过映射到不同的slots上。如电话:436-555-4601 -> (43,65,55,46,01) -> 43+65+55+46+01 = 120 -> 210 % 11 = 1。
  • mid-square method方法先求平方，在取结果的中间部分，最后映射到不同的slots上。如：44 -> 44平方 = 1936 -> 中间数字 1(93)6 = 93 -> 93 % 11 = 5。

注[3]: 随着item数量的增多，想要不产生冲突或者说碰撞，我们就需要增加slot的个数。但是，当item的数量很大时，这种提升搜索性能的方式就不太可行。所以，我们不需要刻意的避免冲突。在尽量减少冲突的情况下，尽量均匀的将item分布在不同的slot中，依旧可以提高搜索速度。

注[4]: 除了这种存放item集合的方式，还有开放寻址方式、扩展线性探测方式。

  • 开放寻址方式：如果h(item)的位置已经有其他item，就依次移动，直到找到一个为None的slot来存放item。在搜索、查找时，也是先找到h(item)位置，然后依次往后check，如果直到发现了新None也没有匹配上，说明item不在。

  • 扩展线性探测方式：思路就是如果h(item)的位置被占用，就rehash(item+skip)。