首页   快速返回

常用hash算法及冲突解决方法     所属分类 java
常用hash算法

a. 直接定址法:直接以关键字k或者k加上某个常数(k+c)作为哈希地址(H(k)=ak+b)。
b. 数字分析法:提取关键字中取值比较均匀的数字作为哈希地址(如一组出生日期,相较于年-月,月-日的差别要大得多,可以降低冲突概率)
c. 分段叠加法:按照哈希表地址位数将关键字分成位数相等的几部分,其中最后一部分可以比较短。然后将这几部分相加,舍弃最高进位后的结果就是该关键字的哈希地址。
d. 平方取中法:如果关键字各个部分分布都不均匀的话,可以先求出它的平方值,然后按照需求取中间的几位作为哈希地址。
e. 伪随机数法:选择一随机函数,取关键字的随机值作为散列地址,通常用于关键字长度不同的场合。
f. 除留余数法:用关键字k除以某个不大于哈希表长度m的数p,将所得余数作为哈希表地址(H(k)=k%p, p<=m; p一般取m或素数)。

常用冲突解决方法

a. 链地址法:将哈希表的每个单元作为链表的头结点,所有哈希地址为 i 的元素构成一个同义词链表。即发生冲突时就把该关键字链在以该单元为头结点的链表的尾部。
b. 开放定址法:即发生冲突时,去寻找下一个空的哈希地址。只要哈希表足够大,总能找到空的哈希地址。
c. 再哈希法:即发生冲突时,由其他的函数再计算一次哈希值。
d. 建立公共溢出区:将哈希表分为基本表和溢出表,发生冲突时,将冲突的元素放入溢出表。


jdk中使用 链地址法 解决哈希冲突 , 新增节点头部插入

上一篇     下一篇
并发编程的挑战摘要

并发机制的底层实现原理摘要

java7 hashmap 要点

java8 hashmap 要点

hashmap在java7和8中的区别

java位运算