Date: 22 Mar 2015
哈希（Hash）算法在编程中是经常用的到的，我之前对 Hash 的理解是比较简单的，即通过 Hash 函数把一定值转换为另外的值。在看 MIT 的公开课之后发现原来关于 Hash 算法和函数还有许多我不知道的细节。
哈希算法的基本思想就是使用哈希函数在空间 U 里的所有值映射（Map）到大小为 m 的一张表中。
可以想象如果这张表不够大，那么就会出现两个不同的值被映射到这张表的同一个槽（Slot)里的现象，这就叫做碰撞。
当碰撞发生时，可以用两种方法进行处理。
链式（Chaining) 这种处理方法就是把在同一个槽里的值用单向链表的方法把他们组织起来。这样在进行查找的时候，首先找到值所在的槽，然后再在这个槽中的链表里进行查找。
开放寻址（Open Addressing） 链式的碰撞处理需要表以外的空间存储链表，也就是说需要表以外的存储空间。而开发寻址方法则不需要。开放寻址就在发生碰撞时再使用哈希 函数把当前槽的值映射到下一个槽的位置，直到不发生碰撞位置。该方法主要问题是在删除表中的值时比较困难，原因是在删除某个之后可能会存在风险，比如在删除某个之后，在进行查询是查到这个位置发现这个位置为空，就会认为该不存在，而事实上需要查询的值需要再进行几次开放寻址才能得到。
哈希函数函数并不完美，它的最大缺点就是：对于任意的一个哈希函数，都存在着一组值，这组值通过哈希函数处理之后，都将映射到存储表的同一个位置上，如果这样的情况发生就会使搜索表的时间大大地增加。解决这个问题的方法就是：在算法中不再使用单一的一个哈希函数，而是在每一次进行哈希时都是从一组哈希函数中随机地抽取一个来使用。这样就引出了全域哈希的概念:
当我们需要把值映射到一个大小为 m 的表中时，从一组哈希函数 H 中随机抽取一个哈希函数进行映射，如果任意两个值在映射时法生碰撞的概率为 1/m 时，我们把这样一组哈希函数称之为全域的。
构造一组全域哈希函数，首先要使哈希表的大小 m 为质数（Prime），然后把值 k 分解为 r+1 位数，其中每一位都是集合 s = {0, 1, … , m-1}中的元素。然后随机生成 r+1 元向量 a，所谓随机生成就是 a 的每一个元素都是随机从集合 s 中取得。 最后的哈希函数就是向量 k 和 a 做点乘（dot product）然后求 m 的模。由于向量 a 是随机生成的，这就体现了全域哈希的随机性，而且我们还可以知道这组哈希函数的大小为 m 的 r+1 次方。
完全哈希指的是：有一组大小为 n 的值，构建一个静态表，所谓静态就是没有插入、删除操作，只需要查询，这个静态表的大小为 O(n)，而且在最坏情况下查询这个表所需的时间为 O(1)。构建完全哈希的基本思想就是建立一个两级结构的哈希表，在第一级发生碰撞时并不是采用链式处理，而是又用了一次哈希。而且在每一级上的哈希都是全域哈希，因此在第二级上不会发生碰撞，这个是可以证明的，证明的过程我在这里就不写出来了。