首页 > 编程知识 正文

处理hash冲突,hashmap实例

时间:2023-05-05 06:36:35 阅读:16064 作者:4379

HashMap一直以来都知道线程不安全,但为什么线程不安全呢? 如果是多线程操作,线程什么时候不安全呢?

首先,让我们看看HashMap的基本存储结构。 HashMap的基础是条目数组。 HashMap在发生Hash冲突时使用拉链法解决冲突。 Entry内部变量:

finalObjectkey;

对象值;

进入下一步;

inthash;

可以看到在Entry内部的next变量中使用了链表。 此时,如果在有多个线程的时间点同时操作散列映射以执行推送操作,且大于两个密钥的散列值相同,则必须解决碰撞冲突,如图中的a1、a2所示。 有关解决冲突的方法,如上所述,我们在此不讨论链表的结构。 不讨论是从链表的开头插入还是从末尾首先插入。 现在,如果两个线程取正好对应的位置的开头节点e-1,则如图所示,最终结果将丢失a-1和a-2这两个数据中的一个。

看看put方法

publicobjectput(objectobj,Objectobj1) )。

{

if(table==empty_table ) )。

基础设施表(threshold;

if(obj==null ) )。

returnputfornullkey(obj1;

inti=hash(obj );

intj=indexfor(I,table.length );

for (输入项=table [ j ]; 进入!=null; 输入=输入.下一步)

{

Objectobj2;

if (entry.hash==I ((obj2=entry.key )==obj||obj.equals ) obj2) )

{

Objectobj3=entry.value;

entry.value=obj1;

输入.记录访问(this;

返回对象3;

}

}

模具计数;

详细信息(I,obj,obj1,j );

返回空值;

}

put方法未同步,也调用了addEntry方法。

voidaddentry(inti,Objectobj,Objectobj1,intj )。

{

if(size=Thresholdnull!=table[j] )

{

resize(2*table.Length );

i=null==obj? 0:混列(obj );

j=indexfor(I,table.length );

}

创建条目(I,obj,obj1,j );

}

因为addEntry方法仍然不同步,所以会损害线程的安全。 我不会说明其他同样的操作,但是看了源代码就知道了。 下面主要介绍HashMap非线程安全的原因。 我知道HashMap有扩展功能。 对应的方法是HashMap的resize方法。

语音重置(Inti )。

{

企业[ ]=table;

intj=aentry.length;

if(j==1073741824 ) )。

{

threshold=2147483647;

返回;

}else

{

企业1 [ ]=newentry [ I ];

传输器(a入口1,inithashseedasneeded(I ) );

表=a entry 1;

threshold=(int ) math.min ) ) float ) i*loadFactor,1.073742E 009F );

返回;

}

}

可见扩展方法也不同步。 在扩展过程中,代码将显示新的容量数组,重新计算原始数组中的所有键值对,将其写入新数组,然后指向新生成的数组。

在多个线程同时检测到总数超过阈值的同时调用resize操作,每个操作生成新数组,rehash并将其分配给该map下面的数组table。 因此,只有最后一个线程生成的新数组被分配给table变量,而其他线程的则丢失。 另外,如果某些线程已完成赋值,而另一些线程天真苗条,则使用已经赋值的table作为原始数组也是一个问题。

版权声明:该文观点仅代表作者本人。处理文章:请发送邮件至 三1五14八八95#扣扣.com 举报,一经查实,本站将立刻删除。