哈希函数的构造方法以及哈希表解决冲突的方式

哈希表

哈希表的思想就是在待查记录的关键字值和它的存储位置之间建立一个确定的对应关系则查找时不必再进行关键字值间的比较。
根据设定的哈希函数及处理冲突的方法将查找表中各数据元素存储在一段有限的连续空间中&＃xff0c;即得哈希表。

这里有两个比较重要得问题&＃xff1a;哈希函数的构造、处理冲突的方法。

哈希函数的构造方法

1、直接定址法

直接根据数据的值来映射到地址&＃xff0c;比如对数字10、11、12、13…可以将其映射到一块连续的内存中。

2、数字分析法

根据数据的某些数字&＃xff08;比如百位和十位数字&＃xff09;来映射到地址。

3、平方取中法

若关键字比较短&＃xff0c;则可先对关键字值求平方&＃xff0c;然后取运算结果的中间几位为哈希地址。

4、折叠法

将关键字值分割成位数相同的几个部分&＃xff0c;然后取这几部分的叠加和&＃xff08;舍去进位&＃xff09;作为哈希地址。

5、除留余数法

H&＃xff08;key)&＃61;key%13

处理冲突的几种方法

处理冲突是指对于一个待插入哈希表的数据元素&＃xff0c;若按给定的哈希函数求得的哈希地址已被占用&＃xff0c;则按一定规则求下一哈希地址&＃xff0c;如此重复&＃xff0c;直至找到一个可用的地址以保存该元素。

1、开放地址法

基本思想是&＃xff0c;如果映射的地址被占用了&＃xff0c;在哈希函数值的基础上加上指定数值&＃xff0c;这样就可以把冲突的地址给错开&＃xff0c;然后重新开辟新的地址用来存储。根据增量值的不同&＃xff0c;分为线性探测再散列和二次探测再散列。

线性探测例子&＃xff1a;
下面在映射18时&＃xff0c;发现18%7&＃61;4&＃xff0c;但是哈希表的4已经被占用&＃xff0c;对4进行加1&＃xff0c;映射到5&＃xff0c;发现5是空的&＃xff0c;放到位置5即可。

当值为34时&＃xff0c;发现哈希函数值为6&＃xff0c;但是已经被占用&＃xff0c;这时对其加1&＃xff0c;发现0的位置再次被占用&＃xff0c;那就在此基础上再次加1&＃xff08;实际就是加2&＃xff09;&＃xff0c;发现1位置是空的&＃xff0c;正好可以放置元素。

这个例子也是如此&＃xff1a;

关于二次探测方式&＃xff0c;和线性探测方式相似~

比如对68来说&＃xff0c;68%11&＃61;2&＃xff0c;结果2处被占用&＃xff0c;这时对2&＃43;1^{2&＃61;3&＃xff0c;结果发现3也被占用&＃xff0c;这时对3-1}2&＃61;2,发现2再次被占用&＃xff0c;这时对2&＃43;2^2&＃61;6&＃xff0c;6位置未被占用&＃xff0c;放入即可。

2、链地址法

将所有按给定的哈希函数求得的哈希地址相同的关键字存储在同一线性链表中&＃xff0c;且使链表按关键字有序&＃xff08;比如大小等属性&＃xff09;。

3、公共溢出区

若关键字所对应的哈希地址已被占用&＃xff0c;则保存到公共溢出区中。一般在开辟地址的时候会产生哈希地址和公共溢出区两块~

4、再哈希法

再哈希法的基本思想是同时构造多个不同的哈希函数&＃xff1a;
Hi&＃61;RH1(key&＃xff09;&＃xff0c;i&＃61;1&＃xff0c;2&＃xff0c;3&＃xff0c;…k
当哈希地址Hi&＃61;RH1(key)发生冲突时&＃xff0c;再计算Hi&＃61;RH2&＃xff08;key&＃xff09;…&＃xff0c;直到冲突不再产生。这种方法不易产生聚焦&＃xff0c;但增加了计算时间~

如在哈希表中查找元素

在哈希表中查找数据元素的过程与将数据元素插入哈希表的过程基本一致&＃xff0c;即&＃xff1a;
根据待查关键字值&＃xff0c;按给定的哈希函数&＃xff0c;求哈希地址&＃xff1b;若该地址上无数据元素&＃xff0c;则查找失败。
若地址上有数据元素则进行关键字值间的比较&＃xff1b;
若相等&＃xff0c;则查找成功&＃xff1b;
若不等&＃xff0c;则按冲突处理方法求下一可能的存储地址。

虽然哈希表在关键字值与存储位置间建立了映像&＃xff0c;但由于冲突的存在&＃xff0c;查找时仍需进行关键字之间的比较&＃xff0c;因此仍以查找成功时的平均查找长度和查找不成功时的比较次数作为衡量查找效率的依据。