Error message here!

Hide Error message here!

忘记密码?

Error message here!

请输入正确邮箱

Hide Error message here!

密码丢失?请输入您的电子邮件地址。您将收到一个重设密码链接。

Error message here!

返回登录

Close

解决hash冲突之分离链接法

xtu熊大 2019-02-01 18:48:00 阅读数:202 评论数:0 点赞数:0 收藏数:0

解决hash冲突之分离链接法

分离链接法:其做法就是将散列到同一个值的所有元素保存到一个表中。

这样讲可能比较抽象,下面看一个图就会很清楚,图如下

 

相应的实现可以用分离链接散列表来实现(其实就是一个linkedList数组)

至于基本的增加、删除和查询的思路都是先根据散列函数来确定遍历哪个链表。然后再到被确定的链表中执行一次查找,然后再进行相应的操作。

接下来就讲几个注意点吧

 (一)什么时候需要rehash来扩大散列表的大小

讲这个的时候,先介绍一下什么是装填因子。

装填因子 = 关键字个数 / 表长  

当我们使用分离链接法来处理冲突的时候,我们肯定希望装填因子最好为1,因为这个能尽可能将查找代价降到最低,所以当装填因子大于1的时候,我们会需要rehash来扩大散列表的大小。

rehash函数的具体实现如下(这是数据结构与算法书上的伪代码):

private void rehash() {
List<AnyType>[] oldLists = theLists;
theLists = new List[nextPrime(2*theLists.length)];
for(int j=0; j<theLists.length;j++)
theLists[j] = new LinkedList<>();
currentSize = 0;
for(int i=0; i<oldLists.length;i++)
for(AnyType item : oldLists[i])
insert(item);
}

其实大概的思路就是:将当前表的大小翻倍,但是表的大小必须是大于翻倍后的素数(下面贴出了nextPrime的具体实现)

这里表的大小必须要是素数是为了保证一个好的分布,尽可能减少冲突。

(二)散列函数的大概实现

这里先贴出书上的myhash()方法的具体实现

private int myhash(AnyType x) {
int hashVal = x.hashCode();
hashVal %= theLists.length;
if(hashVal < 0) {
hashVal += theLists.length;
}
return hashVal;
}

思路也比较简单,就是先得到插入数据的hashCode,然后对表的大小取余;如果结果是负数的话,就加上表的大小即可。

工具类:

nextPrime

//返回大于某数的下一个素数
static int NextPrime (int N) {
if (N % 2 == 0)
++N;
int i;
for (; ; N += 2){
for (i = 3; i*i <= N; i+=2)
if (N % i == 0)
goto ContOuter;
return N;
ContOuter:;
}
}

 

版权声明
本文为[xtu熊大]所创,转载请带上原文链接,感谢
https://www.cnblogs.com/xtuxiongda/p/10346704.html

编程之旅,人生之路,不止于编程,还有诗和远方。
阅代码原理,看框架知识,学企业实践;
赏诗词,读日记,踏人生之路,观世界之行;

支付宝红包,每日可领