算法导论瞎抄一点-散列表HashTable的Recap

前言：

任何一个应用都要用到至少一种数据结构

比如说我们的程序用到数据库，底层多半是优化后的b-tree.

我们做一个最简单的Android程序,甚至不用到数据库，比方说用到SharedPreferences，那就是xml表单。

甚至我们自己发明一个表单也是可以的，只要写好对应的解析器和编码器，然后给文件取一个没被占用的后缀名即可。

这样的做法用到文件系统，文件系统也有底层的数据结构，可以说VFS也可以具体到磁盘，比如大家熟知的NTFS啥的。

它至少要支持Insert, Search和Delete操作。

比方说数据挖掘作用的non-sql data cube是通常没有update，这和数据集合的功能有关，不清楚的可以看看数据挖掘相关书籍，或者看看我的文章（这个系列没看书看起来确实有点...呵呵）

今天我们来看一下散列表(Hashtable),他用到了(Hash)的处理方式，使得算法平均时间是 ,虽然理论最坏的情况是 .

1.直接寻址表(direct-address table)

实际上这就是一个数组的高大上别名，其中数组的每一个存元素的位置被称为槽(slot)。

它适用于全域U较小的情况

提到数组的具体数据结构，我们毫无疑问要提到一个概念叫做卫星数据(satellite data)。

卫星数据，可以形象的思考地球和卫星的关系，逻辑上它围绕地球，距离上它并不靠近地球。

因此卫星数据在磁盘中是地址任意而被当前数据结构使用的数据，连接当前数据结构和卫星数据的方法是记录卫星数据的地址（指针）

如果了解C/C++的朋友肯定觉得这个概念小儿科了，不再赘述。

//TODO insert graph 11-1

2.散列表(hash table)

直接寻址技术的缺点很明显，如果全域U较大，即数据规模较大，要存储大小为|U|的一张表不太实际（连续内存分配问题），也会造成很大内存浪费。

当存在字典中的关键字集合(keyword set)比全域U小许多时，散列表所需的存储空间要比直接寻址表少很多。

直接寻址方式下，具有关键字k的元素被放在槽k中(见上图11-1)。而在散列方式下，该元素存放在槽中。即利用散列函数计算出槽的位置。

散列函数是全域U向散列表T的映射。

映射这个东西就是高一数学，我们知道，函数是单射的，也就是说每个关键字k只会映射到1个槽。

但同样我们学习过高阶函数，这种程度，同一个因变量y就会有多个自变量x对应了。

更不要提三角函数/脉冲函数等情况了...

因此我们需要考虑同一个槽被多个关键字k映射到的情况，即冲突问题。

//TODO insert 11-2

解决冲突问题也有办法：

使h产生的结果更加没有规律性可言，当然，是固定的函数。

散列的意义就是“杂乱拼凑”，这毫无疑问会减少冲突，使数据尽可能均等的存在于槽(slot)中。

但不要忘了，U是远大于T的，即入射集合远大于出射集合。

我们一定是会遇到冲突的，因此还要考虑解决冲突的办法：

第1种方法.链接法(chaining)

把所有槽的所有元素都放在一个双向链表中。

如果不存在这样的元素，槽中存NIL.

这很好理解，就是数组套链表。

//TODO insert graph 11-3

性能分析：

依照我们的定义，每个slot中的元素个数可以大于1，等于1和小于1.

所以最坏的情况，是所有U映射而出的元素都到了1个slot，即这个slot是一个元素个数为#U的双向链表，设这个长度为n。

这时，查询时间为,再加上散列函数的时间，他就和用一个链表来链接所有元素差不多了（建立链表所花的时间n，对于如果是n->C的函数，也可以视为总体时间n）

链接法的性能毫无疑问取决于链表的长度均匀程度，假设每个k被等可能的散列到所有槽中，我们成这个假设为简单均匀散列（Simple Uniform Hashing）

对于

                                    

并且nj的期望值,其中m为slot的个数，n为所有链表的总长度。

定理 在简单均匀散列的假设下，对于用连接尅发解决冲突的散列表，一次查找的平均时间为

不成功即查找到链表末尾，成功最坏的情况也是查询到链表末尾。

另一种解决冲突的方法叫开放寻址法，之后会的第4节讲到。

3.散列函数

好的散列函数的特点：独立均匀分布

将关键字转换为自然数：如果关键字k不是自然数，就要转化为自然数，以适用于函数，这种转换即字符表，ASCII码表是主流操作。

3.1除法散列法

 = k mode m 可以将U中的所有k通过余数的不同映射到m个槽中。

3.2乘法散列法

即kA的小数部分乘以m向下取整。

其中A是常数，0<A<1。

这样做的好处是，m的选择不是特别关键，一般选择它为2的幂，这样便于2进制运算。

例如某计算机的字长有位，就取A为形如的一个分数，当然A的范围还是(0, 1)

尽管如此，Knuth认为黄金分割比是最好的取值

3.3全域散列法

如果一个恶意的对手来针对某个特定的散列函数选择要散列的关键字，他就可以把n个关键字散列到同一个槽中，使得散列的平均检索时间最坏。

如果需要应付这种攻击，我们只有建立一个散列函数组，并选定随机函数，对散列函数进行随机抽取。

4.开放寻址法(open addressing)

在开放寻址法中，所有的元素都存放在散列表中。也就是说，每个表象或包含动态集合的一个元素，或包含NIL.

在查找一个元素时，要系统的检查所有的表项。这和链接法的最大区别是，开放寻址法中，没有任何元素存放在散列表外，也不会有链表。

因此在开放寻址法中，散列表可能会被填满，以至于不能插入新的元素。该方法导致的一个结果是装载因子绝对不会超过1.（即每个slot最多装一个）

当然，也可以将链表放入槽中，但开放寻址法的好处就在于它不用指针，而是计算出要存取的槽序列。

这就省了指针那点内存，使得同样的内存空间可以容纳更多的槽，客观上减少了冲突出现的概率。

为了使用开放寻址法插入一个元素，需要连续的检查散列表，这个操作称之为探查(probe).

To be Continued.