hash表

Hash表理解

言归正传，哈希表又名散列表，其主要目的是用于解决数据的快速定位问题。考虑如下一个场景。
一列键值对数据，存储在一个table中，如何通过数据的关键字快速查找相应值呢？不要告诉我一个个拿出来比较key啊，呵呵。 （key-value这样的数据，要恰当的选择key，一般情况下key和value是等同的）

大家都知道，在所有的线性数据结构中，数组的定位速度最快，因为它可通过数组下标直接定位到相应的数组空间，就不需要一个个查找。而哈希表就是利用数组这个能够快速定位数据的结构解决以上的问题的。
具体如何做呢？大家是否有注意到前面说的话：“数组可以通过下标直接定位到相应的空间”，对就是这句，哈希表的做法其实很简单，就是把Key通过一个固定的算法函数既所谓的哈希函数转换成一个整型数字，然后就将该数字对数组长度进行取余，取余结果就当作数组的下标，将value存储在以该数字为下标的数组空间里，而当使用哈希表进行查询的时候，就是再次使用哈希函数将key转换为对应的数组下标，并定位到该空间获取value，如此一来，就可以充分利用到数组的定位性能进行数据定位。 （key转换后成为数组的下标，value作为数组的值）

不知道说到这里，一些不了解的朋友是否大概了解了哈希表的原理，其实就是通过空间换取时间的做法。到这里，可能有的朋友就会问，哈希函数对key进行转换，取余的值一定是唯一的吗？这个当然不能保证，主要是由于hashcode会对数组长度进行取余，因此其结果由于数组长度的限制必然会出现重复，所以就会有“冲突”这一问题，至于解决冲突的办法其实有很多种，比如重复散列的方式，大概就是定位的空间已经存在value且key不同的话就重新进行哈希加一并求模数组元素个数，既 (h(k)+i) mod S , i=1,2,3…… ，直到找到空间为止。还有其他的方式大家如果有兴趣的话可以自己找找资料看看。

前面讲的查找方法是基于比较的方法，查找效率依赖比较次数，其实理想的查找是希望不经比较，一次存取便能得到所查记录。这样就必须在记录的存储位置和它的关键字之间建立一个确定的对应关系f，查找k时,只要根据这个对应关系f找到给定值k的像f(k)。这种对应关系f叫哈希（hash）函数。按这种思想建立的表叫哈希表（也叫散列表）。

哈希表存取方便但存储时容易冲突（collision）：即不同的关键字可以对应同一哈希地址。如何确定哈希函数和解决冲突是哈希表查找的关键。

1.哈希函数的构造方法

构造哈希函数的方法有很多，这里介绍几种常用的。

直接定址法:H(k)=k 或H(k)=a*k+b(线形函数)

如:人口数字统计表

地址	1	2	3	...	100
年龄	1	2	3	...	100
人数	67	3533	244	...	4

数字分析法:取关键字的若干数位组成哈希地址

如：关键字如下：若哈希表长为100则可取中间两位10进制数作为哈希地址。

81346532

81372242

81387422

81301367

81322817

81338967

81354157

81368537

平方取中法：关键字平方后取中间几位数组成哈希地址

折叠法：将关键数字分割成位数相同的几部分（最后一部分的位数可以不同）然后取几部分的叠加和（舍去进位）作为哈希地址。

除留余数法：取关键字被某个不大于表长m的数p除后所得的余数为哈希地址。

H(k)=k mod p p<=m

随机数法：H(k)=rondom(k)。

　

2.处理冲突的方法

假设地址集为0..n-1,由关键字得到的哈希地址为j(0<=j<=n-1)的位置已存有记录,处理冲突就是为该关键字的记录找到另一个"空"的哈希地址。在处理中可能得到一个地址序列Hi i=1，2，...k 0<=Hi<=n-1),即在处理冲突时若得到的另一个哈希地址H1仍发生冲突,再求下一地址H2,若仍冲突,再求H3...。怎样得到Hi呢？

开放定址法：Hi=(H(k)+di) mod m （H(k)为哈希函数；m为哈希表长；di为增量序列）

当di=1，2，3，... m-1 时叫线性探测再散列。

当di=1²，-1²，2²，-2²，3²，-3²，...,k²,-k²时叫二次探测再散列。

当di=random（m）时叫伪随机探测序列。

例：长度为11的哈希表关键字分别为17，60，29，哈希函数为H(k)=k mod 11,第四个记录的关键字为38，分别按上述方法添入哈希表的地址为8，4，3（随机数=9）。

再哈希法：Hi=RHi(key) i=1,2,...,k,其中RHi均为不同的哈希函数。

链地址法：这种方法很象基数排序，相同的地址的关键字值均链入对应的链表中。

建立公益区法：另设一个溢出表，不管得到的哈希地址如何，一旦发生冲突，都填入溢出表。

3.哈希表的查找

例:如下一组关键字按哈希函数H(k)=k mod 13和线性探测处理冲突所得的哈希表a[0..15]:

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15
	14	01	68	27	55	19	20	84	79	23	11	10

当给定值k=84,则首先和a[6]比，再依次和a[7],a[8]比，结果a[8]=84查找成功。

当给定值k=38,则首先和a[12]比,再和a[13]比,由于a[13]没有,查找不成功,表中不存在关键字等于38的记录。

哈希(Hash)表