散列表（Hash table，也叫哈希表），是根据关键字(Key value)而直接访问在内存存储位置的数据结构。也就是说，它通过把键值通过一个函数的计算，映射到表中一个位置来访问记录，这加快了查找速度。这个映射函数称做散列函数，存放记录的数组称做散列表。
1 开放定址法：
基本做法：当冲突发生时，使用某种哈希函数 Sphlib
iis7站长之家在哈希表中形成一探查序列，然后沿着此探查序列逐个单元地查找，直到碰到一个开放的地址（即该地址单元为空）为止。
在哈希表中形成一探查序列时，可有三种不同的方法:
⑴ 线性探测法:
基本思想：将散列看成是一个环形表，探测序列是(假设表长为m)：
H(k),H(k)+1,H(k)+2,…,m-1,0,1,…,H(k)-1
用线性探法解决冲突时，求下一个开放地址的公式为：
Hi = (H(k)+i) MOD m
例:
设有哈希函数 H ( key ) = key mod 7 ，哈希表的地址空间为 0 ～ 6 ，对关键字序列（ 32 ， 13 ， 49 ， 55 ， 22 ， 38 ， 21 ）按线性探测再散列和二次探测再散列的方法分别构造哈希表。
解：
线性探测再散列：
32 ％ 7 = 4 ； 13 ％ 7 = 6 ； 49 ％ 7 = 0 ；
55 ％ 7 = 6 发生冲突，下一个存储地址（ 6 ＋ 1 ）％ 7 ＝ 0 ，仍然发生冲突，再下一个存储地址：（ 6 ＋ 2 ）％ 7 ＝ 1 未发生冲突，可以存入。
22 ％ 7 ＝ 1 发生冲突，下一个存储地址是：（ 1 ＋ 1 ）％ 7 ＝ 2 未发生冲突；
38 ％ 7 ＝ 3 ；
21 ％ 7 ＝ 0 发生冲突，按照上面方法继续探测直至空间 5 ，不发生冲突，所得到的哈希表对应存储位置：
下标： 0 1 2 3 4 5 6
49 55 22 38 32 21 13
⑵ 二次探测法:
二次探测法的探测序列依次是12，-12，22，-22，…等，当发生冲突时，求下一个开放地址的公式为：
H2i-1 = (H(k)+i2) MOD m
H2i = (H(k)-i2) MOD m (1=< i <= (m-1)/2 )
优点：减少了堆集发生的可能性。
缺点：不容易探测到整个哈希表空间。
注意：对于利用开放地址法处理冲突所产生的哈希表中删除一个元素时需要谨慎，不能直接地删除，因为这样将会截断其他具有相同哈希地址的元素的查找地址，所以，通常采用设定一个特殊的标志以示该元素已被删除。
⑶ 伪随机探测法:
采用随机探查法解决冲突时，求下一个开放地址的公式为：
Hi = (H(k)+Ri) MOD m
其中：R1，R2，…，Rm-1是1，2，…，m-1的一个随机排列。如何得随机排列，涉及到随机数的产生问题。
2 再哈希法：
基本做法：当冲突发生时，使用另一个哈希函数计算得到一个新的哈希地址，直到冲突不再发生时为止，即
Hi = RHi(key) i = 1,2,…,k
其中，RHi均是不同的哈希函数。
这种方法的优点是不易产生"堆集"，但缺点是增加了计算时间。
3 链地址法：
基本做法：将所有关键字为同义词的结点链接在同一个单链表中。若选定的哈希函数所产生的哈希地址为0~m-1,则可将哈希表定义成一个由m个链表头指针组成的指针数组。
这种方法的优点是：
① 不产生"堆集"。
② 由于结点空间是动态申请的，故更适合于造表前无法确定表长的情况。
③ 从表中删除结点容易。
4 公共溢出区法法：
基本做法：假设哈希函数的值域为[0..m-1]，则设向量HashTable[0..m-1]为基本表，每个分量存放一个记录，另设立向量OverTable[0..v]为溢出表。所有关键字和基本表中关键字为同义词的记录，不管它们由哈希函数得到的哈希地址是什么，一旦发生冲突，都被填入溢出表中。
在哈希表上进行查找的过程和建表的过程基本一致。假设给定的值为K，根据建表时设定的哈希函数H，计算出哈希地址H(K)，若表中该地址对应的空间未被占用，则查找失败，否则将该地址中的结点与给定值K比较，若相等则查找成功，否则按建表时设定的处理冲突方法找下一个地址，如此反复下去，直到找到某个地址空间未被占用（查找失败）或者关键字比较相等（查找成功）为止。
-
本站(WWW.)旨在分享和传播互联网科技相关的资讯和技术，将尽最大努力为读者提供更好的信息聚合和浏览方式。
本站(WWW.)站内文章除注明原创外，均为转载,整理或搜集自网络.欢迎任何形式的转载，转载请注明出处.
转载请注明：文章转载自:[169IT-IT技术资讯]
本文标题:哈希表处理冲突的方法
