PHP数据结构（十五） ——哈希表
PHP数据结构（十五）——哈希表
（原创内容，转载请注明来源，谢谢）
一、概述
查找的效率与查找的次数有关，查找的次数越少速度越快。因此，希望能够一次查找出结果，此时键值一一对应，称满足这条件的f(k)为哈希函数。
1、定义
1）冲突
不同的关键字通过哈希函数，得到同一个地址，称为冲突。具有相同函数值的关键字称为同义词。
2）哈希表
根据设定的哈希函数H(key)和处理冲突的方法，将一组关键字映像到一个有限连续的地址集上，以关键字的“像”作为记录的位置，此表称为哈希表，映像过程称为哈希造表或散列，所得存储位置称哈希地址或散列地址。
2、性质
哈希函数是一个映像，设定灵活，任何关键字由此所得的哈希值落在表长允许范围内。
二、构造哈希表
对于关键字集合中的任意一个关键字，经哈希函数映像到地址集合中的任一地址的概率是相等的，称为均匀的哈希表。
1、直接定址法
取关键字或某个线性函数作为哈希地址，即H(key)=key，或(key)=a*key+b（a、b都是常数）。
该方法地址集合和关键字的大小一样，不会有冲突，但是实际上很少用到。
2、数字分析法
此方法适用于能够预先估计到全部的结果。假设关键字是以R为基的数（例如R=10的十进制），且可以知道哈希表的所有值，则可以用关键字的一部分组成哈希地址。
例如，10000-10099，可以用key0-99来表示。
3、平方取中法
取关键字平方和的中间几位作为地址。此方法类似数字分析法，将关键字进行平方的目的是拉大两个关键值之间的差距。该方法较为常用。因为平方之后的中间几位和这个数的每个数字都有关，具体位数由表长决定。
4、折叠法
将关键字分割成几部分，这几部分叠加和（舍去进位）作为哈希地址。当关键字很长，且分布均匀时，可以采用此方法。
5、除留余数法
取关键字被某个不大于哈希表表长m的数p除后所得余数为哈希地址。
即H(key)=keyMOD p(p<=m)，该方法比较简单，而且可以结合折叠、平方取中等方式。但是要注意，选的数不能太小，也最好不要有很多因数，否则有可能取出来的余数相同的太多。最好选择20以上的质数来取余。
6、随机数法
选择一个随机数，取关键字的随机函数值为它的哈希地址，即H(key)=random(key)。通常，当关键字长度不等时采用此法构造哈希函数比较恰当。
三、构造过程需要考虑的因素
1、计算哈希函数所需的时间，包括硬件指令的因素。
2、关键字的长度。
3、哈希表的大小。
4、关键字的分布情况。
5、记录查找的频率。
四、冲突处理方法
使用哈希函数，很有可能会出现冲突，即多个数经过哈希函数得到同一个结果。此时，就需要冲突处理方法，来使得发生冲突的关键字能够得到一个单独的映射结果。冲突处理方法，用符号Hi表示。
1、开放定址法
发生冲突的哈希值，加上一个数，在取余，可以得到另一个结果，可以作为冲突解决的方式，即：
Hi= ( H(key) + di ) MOD m (i=1,2…k)(k<=m-1)。其中，H(key)为哈希函数，m为哈希表表长，di为增量序列，可以有以下三种取法：
1）线性探测再散列，di=1,2,3…m-1
2）二次探测再散列，di=1,-1,4,-4,9,-9…(m/2)2
3）伪随机数序列
以上三种结果各有好坏。
1）使用线性探测再散列，可以理解为取点i作为哈希值，如果发生冲突，就取i+1，如果还冲突，就取i+2。这样可以保证，只要哈希表还有空间，就一定能够取得哈希值。但是，这样速度会比较慢，特别是比较密集的区间，可以要连续做好几次的冲突处理才可以得到一个结果。
2）使用二次探测再散列，速度将比较快，因为其是采用平方的方式，而不是逐一递增，因此在经过i次的查找，其查找的范围达到i2，这样有效跳出一个大范围的区间。但是，因为这个方式不是逐一取结果，因此有可能最终没有找到能使用的哈希值。
3）伪随机数是随机的数，则结果不稳定，有可能特别快，也有可能特别慢。
2、再哈希法
Hi=RH(key)。即发生冲突时，换一种冲突处理方式，来解决冲突。
3、链地址法
该方法取得的哈希值键值不是一一对应的，而是一个哈希值指向一个存储空间，该空间是一个线性链表，由所有哈希结果一致的键组成。该方式可以保证哈希的结果足够快，不需要进行再哈希或者开放地址计算，也能保证每一个键一定可以有哈希值。但是，查找的时候相对速度较慢，因为需要在链表里面逐一判断结果。
4、建立公共溢出区
该方式为补救措施，即建立一个公共的区域，所有无法取得哈希的结果都放在此区域。该方式获取结果效率会比较低，但是作为补救措施，可以保证数据不丢失。
——written by linhxx 2017.07.15