• 微信公众号:美女很有趣。 工作之余,放松一下,关注即送10G+美女照片!

HashMap底层是如何检测重复的?

开发技术 开发技术 3小时前 2次浏览

HashMap底层是如何检测重复的?

HashMap,它在添加元素时首先会通过该元素的hasecode值得到一个hash值。再通过此hash值计算得到此元素要存储的索引位置。

判断table表的索引位置是否为空,为空则直接添加

否则,这里有三个判断分支,首先判断要添加的元素的hash值与此位置元素的hash值是否相等,不相等会产生一个短路与直接进入下一个分支判断,相等则会继续判断这两个元素的equals值是否相等(为减少equals在方法的调用次数,会先对其hashCode值进行比较),相等则不做任何操作,最终方法返回false添加失败,equals值不相等的话也是进入下一分支判断

判断此位置的元素是不是一个红黑树节点,是则按照红黑树的方法进行判断,不是则进入最后的分支判断

将要添加的元素与这个索引位置的元素为起点的链表上的所有节点进行循环比较,有相同的就退出循环添加失败返回false,都不相同就将此元素添加到链表的最后,

添加完后会立即进行链表长度的判断,达到8就调用树化的方法。但不一定树化成功,树化还有一个条件是table表的大小达到64,未达到的情况下进行table表的扩容。

核心原码分析:

//V:添加的元素Key不重复:返回null;key重复:返回原有key对应的value值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    HashMap.Node[] tab;
    int n;
    //this.table:存放node节点的数组
    if ((tab = this.table) == null || (n = tab.length) == 0) {
        //this.resize():此方法对table进行了初始化空间大小为16,
        n = (tab = this.resize()).length;
    }

    Object p;
    int i;
    //根据key的哈希值计算此key应该存放在table表的那个索引位置,并将这个对象赋值给p
    //再判断p是否为null
    //p为空表示还没有存放元素,就创建一个Node(key,value),并将其存放在此位置
    if ((p = tab[i = n - 1 & hash]) == null) {
        tab[i] = this.newNode(hash, key, value, (HashMap.Node)null);
    } else {
        Object e;
        Object k;
        /**
        *先比较的是当前索引位置对应链表的第一个位置的元素(p)与要添加的key值的元素是否相等,
        不相等:产生短路与进行下一判断条件
        相等:再比较两元素是否为同一对象或者其两对象equals值是否相等(引用同一对象),满足其中一个条件则
        此key值已存在,它添加失败,给e赋值为原有的值并在下方返回。
        */
        if (((HashMap.Node)p).hash == hash && ((k = ((HashMap.Node)p).key) == key || key != null && key.equals(k))) {
            e = p;
         //再判断p是不是一棵红黑树,按照红黑树的方法进行比较
        } else if (p instanceof HashMap.TreeNode) {
            e = ((HashMap.TreeNode)p).putTreeVal(this, tab, hash, key, value);
        //进入这个条件,说明它是一个链表,则让Key与以p为起点的链表上的所有节点值循环比较,相等退出,不相等添加在链表的最后
        } else {
            int binCount = 0;//记录遍历到的第binCount个节点
            while(true) {
                //key依次与链表的每一个元素比较后都不相同,则创建其相关节点并添加到链表的最后
                //将元素添加到链表最后立即判断此时链表的长度是否满足树化条件
                if ((e = ((HashMap.Node)p).next) == null) {
                    ((HashMap.Node)p).next = this.newNode(hash, key, value, (HashMap.Node)null);
                    //当链表长度等于8时,将此链表转化为红黑树
                    if (binCount >= 7) {
                        //此时调用此方法不一定真正进行树化,会再进行判断数组的大小是否达到64
                        //达到:进行树化,未达到进行数组扩容。
                        this.treeifyBin(tab, hash);
                    }
                    break;
                }
				//key与该链表的每一个元素比较后出现相同的情况直接break,在后面方法会返回此节点的值。
                if (((HashMap.Node)e).hash == hash && ((k = ((HashMap.Node)e).key) == key || key != null && key.equals(k))) {
                    break;
                }

                p = e;
                ++binCount;
            }
        }

        if (e != null) {
            //将原位置的value值进行缓存
            V oldValue = ((HashMap.Node)e).value;
            if (!onlyIfAbsent || oldValue == null) {
                //将新的value值替换原有的value值
                ((HashMap.Node)e).value = value;
            }
            this.afterNodeAccess((HashMap.Node)e);
            return oldValue;//返回的是原位置的value
        }
    }

    ++this.modCount;
    //threshold:临界值,根据当前数组容量与加载因子(默认0.75)计算得出
    //若当前数组中节点个数大于此临界值则需要扩容 
    if (++this.size > this.threshold) {
        this.resize();
    }
	//此方法为HashMap留给其子类实现的(实现一个有序链表等),对于hashMap来说此方法为一个空方法
    this.afterNodeInsertion(evict);
    return null;
}

程序员灯塔
转载请注明原文链接:HashMap底层是如何检测重复的?
喜欢 (0)