hlist 哈希链表介绍

哈希表

哈希表又称散列表，是为了加快元素查询而设计的一种数据结构。基本原理是：把需要查询的关键字通过映射函数(散列函数)映射到相应的存储地址，然后直接访问元素。需要存储或者查询的元素一般称为关键字(Key value),而这个映射函数一般称为散列函数，映射到的存储地址一般称为散列表。

用散列表数据结构和其他数据结构的优劣区别

与数组相比较：数组通过数组名和数组下标可以很快的查询、插入和修改。但删除时，要把删除元素后面的元素都往前移动一个单元。

与列表相比较：列表则和数组相反，删除操作时非常容易。但插入，查询和修改都要从列表头开始遍历、比较，然后才能做操作。

而散列表则既有两种数据结构的优点，不管是查询、插入、修改还是删除，都可以由关键字通过散列函数直接找到要操作的元素，然后就可以直接操作了。当然了以上散列表的分析是基于没有冲突碰撞，或者是冲突碰撞处理的比较好的情况。

散列函数

散列函数：不确定长度的元素(数据，信息等)通过散列函数压缩成信息摘要，形成固定格式的信息。关键字key，则hash = f(key)，则f(key)是散列函数，存放hash值的地址集为哈希表。不同的关键字key，可以映射到同一个哈希值；但不可以是一个关键字映射到多个哈希值。即：函数可以一对一，也可以多对一，但不能一对多。当多对一(多个关键字散列到一个地址上)时，称为冲突碰撞现象。

构造散列函数的几种方法

一个好的散列函数可以减少散列表中的冲突碰撞现象。下面介绍几种散列函数的构造方法：

直接寻址法：把散列函数构造成线性函数，这种方法可以彻底杜绝冲突碰撞现象。一般表达为：hash = kx + b;其实要杜绝哈希表的冲突现象只要散列函数为单调性函数就可以了，或者更确切的说只要在关键字的区域内，散列函数是严格单调的函数，那么就可以杜绝冲突现象了。其本质是单调函数x和y是一一对应的。

从这种方法思考延伸下去：因为一个好的散列表其元素分布要尽量均匀。

例：关键字为： 3、12、21、33、54、78、93 散列函数为：hash = hash(x) = x 则生成的哈希表将会有很多的空间浪费，而且分布很不均匀。若散列函数为：hash = hash(x) = 1/x 则生成的hash值分别为：1、4、7、11、18、26、31 这个散列表的区域明显比前个散列表要分布更均匀些。所以用这种方法构造散列函数设计散列表时，可以考虑下函数的斜率。尽量让散列表分布均匀。

第二种就是利用高数的微积分知识。 例：hash = hash(x) = x^2 - 6x + 8 若关键字的域为大于3，则是一对一的散列表。若关键字域在大于0的范围内，那么这是个多对一的散列表。即：会发送散列表冲突碰撞现象。这个方法的本质是函数的单调性，可以把哈希函数求导，求出hash极值时，关键字为3。所以若所有关键字域》3或者所有关键字《3都不会出现散列表冲突现象。这是个检测散列表是否有冲突现象的很好的方法，也可以验证哈希函数设计的是否合理。

数字分析法：使用这种方法是在已知所有关键字的前提下，可以过滤掉易引起散列表冲突现象的关键字部分，只取关键字中的某个部分来运算后作为关键字的存储地址。

例：关键字为一个32位学生的班级全体学生的出生年月日信息。这个可以用数字分析法来过滤掉易引起散列表冲突现象的某部分。分析：一个班的同学，年龄都相仿，所以出生年号大部分是一样的。若选用年号运算后来做存储地址，则容易引起散列表冲突，故剔除掉年号。若用出生信息中某日运算后作为存储地址，则32个同学中一定会有同学产生的哈希值相同，有散列表冲突。所以最后分析得：用月和日号一起作为关键字运算后当做存储的地址。这样出现哈希冲突的现象就会大大减少。

平方取中法：取关键字平方运算后的中间若干位为存储地址，这个方法可以在不知道所有关键字的前提下使用。一个数的平方后会扩大，取其中间的几位数，一定和原来的数有关系。

例：关键字为：120、110、150、210、330、230

关键字的平方：14400、12100、22500、44100、108900、52900

舍去后面2位（ (keykey) / 100 ），取3位数（ （ (keykey) / 100 ）%1000）作为存储地址（也可以取4位，不足前面补0。这要看散列表的长度）

：144、121、225、441、089、529

折叠法：将关键字分割成位数相同的几部分，最后一部分的位数可以不同。然后取这几部分的叠加和（舍去进位）作为哈希地址。这个方法可以适用于关键字位数比较多的，并且关键字的位数不一致的情况。

例：关键字：12314、143211、17326、98271、83764

把关键字分割2部分，然后折叠：

12314：12 + 31 + 4 = 47

143211：14 + 32 + 11 = 57

17326：17 + 32 + 6 = 54

98271：98 + 27 + 1 = 26 （舍去进位，保持存储地址的位数一样）

83764：83 + 76 + 4 = 63 （同上舍去进位）

随机法：随机法是把关键字作为随机因子然后通过随机函数来生成的在一定范围内的随机数作为存储地址。

例：srand((int)关键字); //设置随机因子

rand(); //生成随机数

当然具体要生成的随机数范围可以根据需求自己通过整除和求模之类的方法来设定。这个是伪随机数，只要随机因子相同就能得到相同的随机数，所以查找时也可以很方便。

除留余数法：这是个最常用，最有用，和最容易理解的。一般的用法是：关键字 mod 表长（或者小于表长的某个数）。

例：21、33、4、12、49、50、、、、、、、、

假设表长为10。关键字 mod 表长

：1、3、4、2、9、0

这种方法容易产生冲突碰撞，一般对关键字mod 质数（一定要小于表长）。

总结：其实上面的一些构造散列表的方法可以混用，只要根据思路灵活变通就能构造出很好的散列函数。

处理碰撞：

不管散列函数设计的如何的好，当关键字越多时，越容易出现冲突碰撞现象。下面介绍下处理碰撞现象的方法，从大方面讲2种方法。

第一种：开发寻址法。hash = ( hash(key) + d(n) ) mod p, n = 1,2,3,4,,,,p(p <= 表长)；

线性探测：d(n) = 1,2,3,4,5,,,,,当散列出来的存储空间上已经有元素了，那就往该空间的下一个空间上查找是否为空的，依次往下找，直到找到空位置，然后存放起来。

平方探测：d(n) = 1^2、22、3^2、、、、 方法和线性探测一样，只是该方法一次性跳转的空间距离比较大。

伪随机法：跳转随机个位置然后查看是否为空位置，以此类推，直到找到空位置，然后存放起来。

这个方法如果遇到聚集（元素不均匀的存储在同一块区域）那整个算法的性能都会下降。因为，哈希到的地址有元素占用，且元素成块存储，则+1、、、、、、直到+到很大的一个数才能找到空位置。后面插入的元素将很可能更难找到空位置。若这个哈希表很大那查找的次数将会更大。这种情况下，伪随机法 》 平方探测 》 线性探测，线性探测是最差的。

第二种：链表法。把碰撞的元素做成个链表节点，一直往后链接，形成链表。通俗的讲是数组链表。这是个比较常用的方法。思想和哈希桶比较类似。后面会附有链表法的程序。

其他的方法有双散列，再散列之类的方法。

算法性能

哈希算法的时间复杂度一般是O(1)，但如果有处理冲突碰撞的现象则时间复杂度会大些可能达到O(n)。这根据三个方面的原因来考虑：1.散列函数设计的是否合理；2.冲突碰撞处理方法设计的是否合理；3.散列表的装载因子是否过大。

前两种上面已经分析过，现在来看下装载因子。

装载因子 = 全部需要填入表中的元素(所有关键字) / 散列表的长度；

从公式可以看出当装载因子越大时，表明需要装载的关键字越接近散列表的长度（为1时，表明需要装载的关键字和表长度一样大。也所以装载因子不能大于1，最大是等于1），也越容易发生冲突碰撞事件。一般规定装载因子大小在0.7左右，大于这个值时，可以考虑再增加下表的长度，当然这要在散列函数和碰撞处理方法都与表长无关的前提下。这个装载因子在用开放寻址法的时候非常有用，因为这个因子直接影响到处理碰撞方法的优劣。

哈希链表--用户态（C代码实现）

实现代码程序见：hlist哈希链表的实现--C代码实现