Hashmap非线程安全关于hash值冲突怎么处理

发布时间:2022-04-22 15:14:03 作者:iii
来源:亿速云 阅读:136

本篇内容主要讲解“Hashmap非线程安全关于hash值冲突怎么处理”,感兴趣的朋友不妨来看看。本文介绍的方法操作简单快捷,实用性强。下面就让小编来带大家学习“Hashmap非线程安全关于hash值冲突怎么处理”吧!

hash值冲突该怎么处理

都知道它是基于hash值,可以进行常量时间消化的存储结构。广泛用于各种情况下的高效key-value存储。这里有几个问题。首先,如果出现hash值冲突该怎么处理?相信很多人都不用思考就能说出,通过链表来解决冲突。就是将hash值相同值存储到一个挂载在该位置的链表里面去。但是这就又引出了新的问题,给一个key,它的hash值有冲突的情况下,它是如何在链表上取到你所期望的value的?这个就要去看hashmap的存储结构了。每一个key-value会被封装到一个entity中,map中存储的其实是这个entity。这样既存储了value,又存储了key。所有在链表上取值只需要比较key是否equal。这里又出现了一个问题,为什么建议重写key的equal和hash方法。重写hash方法能够保证不同对象用于不同的hash值,从而减少冲突,重写equal则可以在出现冲突的情况下,保证不出现错误覆盖的情况。

hashmap的put方法

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)//没有初始化,则要初始化,初始化调用的也是resize()方法
            n = (tab = resize()).length; 
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);//这个位置没有值,直接插入,重写hash方法的作用体现在这里
        else {//出现了冲突
            Node<K,V> e; K k;
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))//找到了如该key equal的value
                e = p;
            else if (p instanceof TreeNode)//事树节点,插入到树里。jdk8冲突节点数目达到一定值后,使用树结构存储
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                for (int binCount = 0; ; ++binCount) {//一直找到链表的结尾,将k-v插入
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                            treeifyBin(tab, hash);//是否需要改成树存储
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

上面的代码充分表明了key重写equal的作用。HashMap以key的value来获取值,所以一定要确保同一个key的hashcode在任何时候都不能改变。这也是为什么建议key是不可变对象,如string对象。如果key是对象,运行过程中key的hashcode因为内部值的改变而发生了改变,那么map中的value将永远丢失。

非线程安全体现

以上是关于kv的讨论,接下来是关于HashMap的另外的一个常见话题&mdash;&mdash;线程安全问题。多数人都知道它是非线程安全的。但是如果问你它非线程安全体现在哪里,恐怕会难住一批人。

首先容易想到的是多线程插入时出现了冲突的情况,多个线程同时插入,但是这其中有些值又出现了冲突。插入时大家都看到这个位置没有值,于是都进行插入,这样肯定会出现值覆盖,对外的表现就是值丢失。如果开始插入时,这个位置已经有了值,那么在插入链表过程中还是会出现值覆盖。

另外就是同时扩容问题。因为HashMap会在空间不足时自动扩容,大小变成之前的两倍。同时复制之前的值到新的数组中。冲突链也会进行复制。如果多个线程插入后同时看到容量需要调整,就都会调用resize方法。那么底层到达会出现什么问题就难以预测了。

所以这也是HashMap非线程安全的第二点体现。当然同时读写一个值也可能会存在数据跟期望不一致的情况。这也是非线程安全的表现。

到此,相信大家对“Hashmap非线程安全关于hash值冲突怎么处理”有了更深的了解,不妨来实际操作一番吧!这里是亿速云网站,更多相关内容可以进入相关频道进行查询,关注我们,继续学习!

推荐阅读:
  1. HashMap,难的不在Map,而在Hash
  2. Java线程安全与非线程安全解析

免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:is@yisu.com进行举报,并提供相关证据,一经查实,将立刻删除涉嫌侵权内容。

hashmap hash

上一篇:C语言怎么实现顺序栈

下一篇:CSS中如何设置内边距

相关阅读

您好,登录后才能下订单哦!

密码登录
登录注册
其他方式登录
点击 登录注册 即表示同意《亿速云用户服务条款》