Hash表

什么是Hash表

　　Hash表又可称哈希表、散列表、或是杂凑表。

　　它是一种十分实用的查找技术，具有极高的查找效率；

Hash表定义：　　

　　　　根据设定的哈希函数H（key）和所选中的处理冲突的方法，将一组关键字映像到一个有限的、地址连续的地址集（区间）上，并以关键字在地址集中的“映像”作为相应的表中的存储位置，如此构造所得的查找表称之为“哈希表”

（简单的说：Hash表是根据内容来制定存储计划的，制定计划的过程归纳到一个函数里边称为Hash函数，数据进行存储的时候要用到Hash函数，同时查找的时候也是根据Hash函数进行的）

冲突：

　　例如：

　　　　对21、30、11三个数，利用k MOD 3的方式，求他们的哈希地址有：

　　　21 MOD 3 = 0；

　　　30 MOD 3 = 0;

　　   11 MOD 3 = 2;

对数字的关键字可有下列构造方法：

　　1、直接定址法 2、数字分析法 3、平方取中法 　　4、折叠法 5、除留余数法 6、随机数法

若是非数字关键字，则需先对其进行数字化处理：

　　1、直接定址法

　　　　取关键字或关键字的某个线性函数值为哈希地址；即：

　　　　H（key）=key 或者H(key)=a*key + b

　　2、除余法(用的很多)

　　　　以关键码除以表元素总数后得到的余数为存储地址；

　　例如：

　　　　对21、30、11三个数，利用k MOD3的方式，求他们的哈希地址有：

　　　　　　21 MOD 3 = 0;

　　　　　　30 MOD 3 = 0;

　　　　　　11 MOD 3 = 2;

　　3、基数转换法

　　　　将关键码看作是某个基数制上的整数，然后将其转换为另一个基数制上的数；

　　　　对21、30、11进行基数转换法求哈希地址：

　　　　　　把这三个数看成8进制；转成10进制：17、24、9；

　　4、平方取中法:

　　　　先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值，又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散　　列地址较为均匀；

　　　　对21、30、11进行平方取中法求哈希地址（取中间的一位）

　　　　　　21×21 = 441 取4

　　　　　　30×30 = 900 取0

　　　　　　11×11 = 121 取2

　　5、折叠法

　　　　将关键码分成多段，左边的段向右边折，右边的段向左边折；然后将它们叠加；

　　6、移位法

　　　　将关键码分为多段，左边的段右移，右边的段左移；然后将它们叠加；

　　7、随机数法：

　　　　选择一个随机函数，取关键码的随机函数值；

处理冲突的方法：　

　　开放地址法：

　　　　1、线性探测法；　　　　

　　　　　　当冲突发生时，使用某种探查技术在散列中形成一个探序列，沿着该序列查找，直到找到关键字或一个开发的地址（地址单元为空）

　　　　　　例如：记录关键码为（3、8、12、17、9），取m=10（存储空间为10）；p=5，散列函数h=key%p；

　　　　2、双哈希函数探测法；　　　　　　

　　　　　　例如：关键码（4、11、16、54），m=11, p=7, h=key%p,二次散列函数为：hi=（h（key）+key%（p-1））%p；

　　链接法

　　　　将散列表的每个节点增加一个指针字段，用于链接同义词的子表，链表中的结点都是同义词；