您的当前位置:首页正文

HashMap源码解析(基于JDK 1.8)-------------------破晓

2024-11-08 来源:个人技术集锦

HashMap源码解析------------JDK1.8

前言

JDK 1.8的HashMap与JDk1.7版本相比最大的区别是,为了避免哈希冲突,使用红黑树的数据结构代替了1.7版本中的单项链表,因为红黑树的插入。增加,删除操作的时间复杂度都为O(lg n),在效率上查找起来要比链表的O(n)更快。我们可以将JDK1.8的HashMap理解为是链表、数组、红黑树的结合体

1.数据结构

HashMap并不是只要hash冲突就直接以红黑树这种复杂的方式去储存冲突的节点,而是一开始使用链表的方式,当桶节点的数量大于8时,会从链表转化为红黑树的方式储存,当筒节点的数量小于6时,又会从红黑树退化为链表,当然前提是该桶是以红黑树储存的。

Node< K, V >

这里和Jdk1.7版本相比基本没有区别

    static class Node<K,V> implements Map.Entry<K,V> {
        //key的HashCode(此hashcode是通过hash方法扰乱后的结果)
        final int hash;
        //HashMap的键
        final K key;
        //HashMap的值
        V value;
        //下一个节点的引用
        Node<K,V> next;

        //4参数构造方法
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = value;
            this.next = next;
        }

TreeNode< K, V >

TreeNode<K,V>类继承于LinkedHashMap.Entry<K,V>类
LinkedHashMap, Entry<K,V>又继承于HashMap.Node<K,V>l类
所以 TreeNode<K,V>类的构造方法中的本质上是调用了HashMap.Node<K,V>类的四参构造方法

//此类的一个对象就代表红黑树的一个节点
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
        TreeNode<K,V> parent;  //节点的父
        TreeNode<K,V> left;	   //节点的左孩子
        TreeNode<K,V> right;   //节点的右孩子
        TreeNode<K,V> prev;    // 保存前一个节点的引用,红黑树节点也会形成一条链
        boolean red;//节点的颜色
        TreeNode(int hash, K key, V val, Node<K,V> next) {
            super(hash, key, val, next);
        }

Node<K,V>,TreeNode<K,V>,再加上下面属性提到的table数组,就构成了HashMap的结构——哈希桶(也可以叫散列桶)

2.属性

//序列号,用于序列化和反序列化操作
private static final long serialVersionUID = 362498820763181265L;


    //默认的容量为16,具体为什么是16,这是通过大量计算得到的最优解,不必纠结,该容量必须是2的幂次方
    static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

    /**
     * The maximum capacity, used if a higher value is implicitly specified
     * by either of the constructors with arguments.
     * MUST be a power of two <= 1<<30.
     */
    //HashMap的最大容量为1<<30,即2的30次方
    static final int MAXIMUM_CAPACITY = 1 << 30;

    /**
     *负载因子,是用来计算是否要进行扩容操作的阀值,
     *比如HashMap的容量为16,阀值 = 16 * 0.75 = 12;
     *也就是说当HashMap被使用12个元素空间时,就要进行扩容,以保证HashMap的效率

     *有的人估计会纠结为什么是0.75,我在这里作一个简单的解释
     *假设负载因子是1,HashMap的容量是16,那么随着HashMap中元素的增加,哈希冲突会越来越严重
     *Jdk1.8中的解决冲突的数据结构是红黑树,大量的哈希冲突会导致红黑树高度会越来越高。大大减小了查询速率
     *假设负载因子是0.5,也就是当HashMap的容量用到一半的时候,就进行的扩容,虽然这样可以减少红黑树的高度,提高查询效率
     *但是以前需要1M的存储空间,现在就需要2M。换句话说就是,我们虽然获得了时间,但是我们牺牲了空间

     *所以0.75是编辑HashMap的那些高手们中和时间与空间得到的一个比较合适的值
     *
     */
    static final float DEFAULT_LOAD_FACTOR = 0.75f;

    /*
	当桶的节点数大于为8时,将链表转化为红黑树
     */
    static final int TREEIFY_THRESHOLD = 8;

    /**
     当红黑树结构的节点数小于6时,节点退化为链表
     */
    static final int UNTREEIFY_THRESHOLD = 6;

    /*
	 当整个hashMap中元素数量大于64时,也会进行转为红黑树结构。
     */
    static final int MIN_TREEIFY_CAPACITY = 64;
	
	//储存Node数据结构的数据
    transient Node<K,V>[] table;

    /**
    将数据转换成set的另一种存储形式,这个变量主要用于迭代功能。
     */
    transient Set<Map.Entry<K,V>> entrySet;


    //HashMap中的元素数量
    transient int size;

    //每次对HashMap的操作的会使modCount++;可以用来检查线程安全,官方称这种检查方式为fail-fast
    transient int modCount;


    //threshold为阈值,计算方法为threshold = initialCapacity * loadFactor;总体作用上方注释有说明
    int threshold;

    //负载因子
    final float loadFactor;

3.构造方法

双参构造中的tableSizeFor(initialCapacity);方法下面的内容会提到

    /*
     *双参构造方法
     *initialCapacity,HashMap初始容量
     *loadFactor负载因子
     */
    public HashMap(int initialCapacity, float loadFactor) {
        //初始容量小于0,
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        //初始容量大于最大容量,将初始容量赋值为最大容量
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        /*
        负载因子不可能小于零,也不能是NaN,读者可以自己输出一下System.out.println(0.0f/0.0f);
        就可以知道NaN是什么了,实际上就是如果loadFactor是通过除法计算得来的,当分母为零时,计算的结果就是NaN
        NaN的全称为Not a Number,显然是不能作为负载因子的
        */
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);

        this.loadFactor = loadFactor;
        //JDK1.7版本直接将initialCapacity赋值给threshold
        this.threshold = tableSizeFor(initialCapacity);
    }
    
    //初始化HashMap使用自己定义的初始容量,使用默认的负载因子0.75f
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
    //无惨构造最简单全部使用默认的属性
    public HashMap() {
        this.loadFactor = DEFAULT_LOAD_FACTOR;
    }

   //使用一个实现Map接口的容器来初始化一个HashMap
    public HashMap(Map<? extends K, ? extends V> m) {
        this.loadFactor = DEFAULT_LOAD_FACTOR;//默认负载因子0.75f

        putMapEntries(m, false);
    }


    final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
        //得到参数m容器的元素个数
        int s = m.size();
        //如果这是个空容器这个方法就直接结束了
        if (s > 0) {
        	//初始化table数组
            if (table == null) {
                //通过元素的个数和负载因子反推出原数组的容量,加1是因为除以一个小数,一般都会得到小数
                float ft = ((float)s / loadFactor) + 1.0F;
                //这个容量要大于MAXIMUM_CAPACITY,就将它赋值为MAXIMUM_CAPACITY
                int t = ((ft < (float)MAXIMUM_CAPACITY) ?
                         (int)ft : MAXIMUM_CAPACITY);
				
				//初始化threshold
                if (t > threshold)
                	//tableSizeFor(t)方法是返回一个大于t的2的幂次方,比如t = 13 就返回16
                    threshold = tableSizeFor(t);
            }
            //table数组已经被初始化,并且数量大于负载因子,进行扩容
            else if (s > threshold)
                resize();
            //遍历参数m,将其中的键值对,加入到本对象的table数组中
            for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
                K key = e.getKey();
                V value = e.getValue();
                putVal(hash(key), key, value, false, evict);
            }
        }
    }

4.核心方法

hash(Object key)方法

详情可以去看我的另一篇博文

 /*
    此方法与JDk1.7版本的hash方法在功能上一样
    都是的到key的hashcode,并进行一系列的扰动操作得到一个hash值
    处理方式上不同的是JDK1.8采用将32为的hashcode的高16位于低16异或的方式进行扰动
    省去了JDK1.7版本大量的位运算。这算是Jdk1.8版本对于Jdk1.7版本的一个优化
    */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

tableSizeFor(int cap)方法

/**
     * 这方法类似于JDK 1.7版本的highestOneBit(int i)方法,详情请看JDK1.7版本的博客
     tableSizeFor(int cap)返回一个大于等于cap的2的幂次方,作为table数组的容量
    */
    static final int tableSizeFor(int cap) {
        int n = cap - 1;                    
        n |= n >>> 1;
        n |= n >>> 2;
        n |= n >>> 4;
        n |= n >>> 8;
        n |= n >>> 16;
        //以上操作使变量n的低位编程连续的1
        //比如  0101 => 0111,这么做的的好处是只需给n加1,返回值就会变成2的幂次方
        //我们table数组的容量必须是2的幂次方
        return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
    }

put方法

流程图

 	
 	public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

    final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
        //tab代表table数组, p初值代表桶的头节点,n代表table数组的长度,i代表当前下标
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        //如果table数组不存在,或者数组的长度为0
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;
        //通过参数hash值求出下标,下标对应的桶没有元素,直接加入进去即可
        if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);
        //桶不为空
        else {
        	/*
        	桶不为空就存在如下三种情况
        	1.你要加入的节点的key与桶的头节点的一样
        	2.桶的头节点是TreeNode,桶是红黑树结构
        	3.桶的头节点不是TreeNode,桶是链表结构
        	*/
           //e用来临时表示一个节点,k代表桶的头节点p的键
            Node<K,V> e; K k;
            //如过你要加入的节点的key与桶的头节点的一样
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                //用变量e来记录该节点
                e = p;
            //如果桶的头节点是TreeNode
            else if (p instanceof TreeNode)
            	/*
            	像红黑树中添加节点,如果该节点已经存在,则返回该节点(不为null),如果添加成功返回null
            	*/
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            //如果桶的头节点不为TreeNode,也就是说,该桶目前是链表
            else {
                //遍历该链表
                for (int binCount = 0; ; ++binCount) {
                	//找到链表的尾节点,尾插法插入新的节点,若果遍历完最后一个节点,e= null
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        //如果此时链表在加入新节点后,此时该链表有9个节点,就要将该链表转化为红黑树	
                        if (binCount >= TREEIFY_THRESHOLD - 1)
                        	//将桶从链表结构变换为红黑树结构
                            treeifyBin(tab, hash);
                        break;
                    }
                    //如果键已经存在
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //如果HashMap中已经存在你要加入的键,这是e代表桶中那个已经存在的节点,返回老值,给节点赋为新的值
            if (e != null) { // existing mapping for key
            	
                V oldValue = e.value;
                
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }
        }
        //程序能执行到这里,说明桶中不存在与你要加入的节点的键相同的情况
        //修改次数加一
        ++modCount;
        //节点数量+1,如果此时的节点数量大于阈值,要对table数组进行扩容
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

treeifyBin方法

	//将Node转换为TreeNode节点
	TreeNode<K,V> replacementTreeNode(Node<K,V> p, Node<K,V> next) {
        return new TreeNode<>(p.hash, p.key, p.value, next);
    }
    
    final void treeifyBin(Node<K,V>[] tab, int hash) {
        int n, index; Node<K,V> e;
        //若果tab数组没有被初始化,通过resize方法去初始化
        if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
            resize();
        //通过hash值求出对应的下标,从数组中得到下标所对应的节点
        else if ((e = tab[index = (n - 1) & hash]) != null) {
            TreeNode<K,V> hd = null, tl = null;
            do {
                //将节点变化为TreeNode节点
                TreeNode<K,V> p = replacementTreeNode(e, null);
                if (tl == null)
                    hd = p;
                else {
                	//将TreeNode节点变为一条链
                    p.prev = tl;
                    tl.next = p;
                }
                tl = p;
            } while ((e = e.next) != null);
            if ((tab[index] = hd) != null)
            	//将链表转化为红黑树的储存结构
                hd.treeify(tab);
        }
    }

get方法

流程图

 //通过键得到对应的值
 public V get(Object key) {
        Node<K,V> e;
        return (e = getNode(hash(key), key)) == null ? null : e.value;
    }

    final Node<K,V> getNode(int hash, Object key) {d
        //tab代表table数组,first发表对应桶的头节点,n代表tab数组的大小,k代表键
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //如果数组存在,并且不为空,并且要查找的元素存在
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            //如果桶的头节点的hash值与key与你要查找的相等,直接返回桶的头节点
            if (first.hash == hash && // 
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            //如果该桶存在后续节点,将桶的第二个节点赋值给e
            if ((e = first.next) != null) {
            	//如果该桶的数据结构是红黑树
                if (first instanceof TreeNode)
                    //通过hash值和key值从红黑树中查找到对应的节点,并返回,没有找到返回null
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //不为红黑树,说明桶的数据结构是链表,那么就遍历该链表进行查找    
                do {
                	//如果hash值和键都与要查找的节点相等,返回该节点
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

resize方法

1.8版本的resize方法要比JDK1.7版本的更复杂,抛开红黑树,1.8版本的resize方法不光可以扩容table数组,还可以对其初始化

当初次使用resize方法时
threshold有两种情况:

final Node<K,V>[] resize() {
        //将当前的table数组用oldTab数组来临时保存
        Node<K,V>[] oldTab = table;
        //代表老数组的容量,如果老数组为null。容量就为0
        int oldCap = (oldTab == null) ? 0 : oldTab.length;
        //oldThr代表当前的threshold
        int oldThr = threshold;
        //newCap代表新的数组容量,newThr代表新的扩容阈值
        int newCap, newThr = 0;
        //非首次初始化时
        if (oldCap > 0) {
            //如果老容量已经是HashMap允许的最大容量了,那么将不进行扩容操作,直接返回老数组
            if (oldCap >= MAXIMUM_CAPACITY) {
                threshold = Integer.MAX_VALUE;
                return oldTab;
            }
            //如果老数组可以扩容,那么将它扩容两倍
            else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                     oldCap >= DEFAULT_INITIAL_CAPACITY)
                //如果扩容后的容量还是要比最大容量要小,那么新的扩容阈值也是老的两倍
                newThr = oldThr << 1; // 线性变化,容量扩大两倍,负载因子也扩大两倍
        }
        else if (oldThr > 0) //非无参构造初始化
            newCap = oldThr;
        else {               // 无参构造初始化,oldThr只有在无惨构造时才小于等于0
            //所以新的容量为默认容量16
            newCap = DEFAULT_INITIAL_CAPACITY;
            //新的扩容阈值是默认负载因子0.75 * 默认容量16 = 12
            newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
        }
        //当直接或者间接使用双参构造时
        if (newThr == 0) {
            //通过初始容量计算出扩容阈值
            float ft = (float)newCap * loadFactor;
            newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
        }
        //将新的扩容阈值赋值给当前的属性
        threshold = newThr;
        @SuppressWarnings({"rawtypes","unchecked"})
            //给table数组申请空间
            Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
        table = newTab;
        //以下操作是将老数组中的节点赋值给新数组中,如果是初始化数组,这部分不执行
        if (oldTab != null) {
            //遍历oldTable数组,挨个取出数组的每一个节点,数组中的节点会出现三种情况
            //1.不存在后续节点,直接放入到新数组中即可
            //2.存在后续节点,桶是红黑树的结构
            //3.存在后续节点,桶是链表的结构
            for (int j = 0; j < oldCap; ++j) {
                //e临时代表桶的头节点
                Node<K,V> e;

                if ((e = oldTab[j]) != null) {
                    //取出一个节点赋值给e,然后将该节点在数组中的存在清空
                    oldTab[j] = null;
                    //如果该节点不存在后续节点
                    if (e.next == null)
                        //通过e节点的hash值,对新容量求出新的下标,放入到新数组中即可
                        newTab[e.hash & (newCap - 1)] = e;
                    //如果此时桶的数据结构是红黑树
                    else if (e instanceof TreeNode)
                        //将红黑树拆分到新的HashMap数组中
                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                    else { // 此时桶的数据结构为链表
                        //将一条链表进行重新散列,可能会变成两条链表
                        //因为hash值是不变的,数组扩大两倍,所以在计算下标时会多算一位,这一位要么0,要么1
                        //所以同一个链表的节点进行哈希散列,会得到两种下标
                        Node<K,V> loHead = null, loTail = null;
                        Node<K,V> hiHead = null, hiTail = null;
                        Node<K,V> next;
                        //do-while循环之后,就会生成以loHead和hiHead为头节点的两个链表
                        do {
                            next = e.next;
                            //如果多取的这一位为0
                            if ((e.hash & oldCap) == 0) {
                                if (loTail == null)
                                    loHead = e;
                                else
                                    loTail.next = e;
                                loTail = e;
                            }
                            //如果多取的这一位为1
                            else {
                                if (hiTail == null)
                                    hiHead = e;
                                else
                                    hiTail.next = e;
                                hiTail = e;
                            }
                        } while ((e = next) != null);
                     
                        //如果loTail不为空,将该链表的头节点加入到新数组中
                        if (loTail != null) {
                            //将最后一个节点的链域赋为null
                            loTail.next = null;
                            //计算下标时多算的那一位为0是,该下标与原来的下标时一样的,就像010 = 10一样
                            newTab[j] = loHead;
                        }
                        //如果hiTail不为空,将该链表的头节点加入到新数组中
                        if (hiTail != null) {
                            //将最后一个节点的链域赋为null
                            hiTail.next = null;
                            //计算下标时多算的那一位为1是,该下标与原来的下标相差oldCap,就像010 = 1010一样
                            //010是取低三位,说明数组容量为8, 1010(B)= 10(D)= 2 + 8 = 10
                            newTab[j + oldCap] = hiHead;
                        }
                    }
                }
            }
        }
        //返回扩容后的新数组
        return newTab;
    }

remove方法

流程图

 //删除指定key的节点,并返回删除的值 
    public V remove(Object key) {
        Node<K,V> e;
        return (e = removeNode(hash(key), key, null, false, true)) == null ?
            null : e.value;
    }

   
    final Node<K,V> removeNode(int hash, Object key, Object value,
                               boolean matchValue, boolean movable) {
        //tab代表table数组  p代表桶的头节点,n代表桶的长度,index代表桶头节点在数组中的下标
        Node<K,V>[] tab; Node<K,V> p; int n, index;
        //tab数组存在,并且有容量,并且存在下标所对应的头节点
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (p = tab[index = (n - 1) & hash]) != null) {
            //node用来存储要删除的节点
            Node<K,V> node = null, e; K k; V v;
            //先判断桶的头节点是否是要删除的节点,如果是的话,将桶的头节点赋值给node
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                node = p;
            //如果该节点有后续节点
            else if ((e = p.next) != null) {
                //桶为红黑树结构
                if (p instanceof TreeNode)
                    //从红黑树中得到此节点,并赋值给node
                    node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
                else { //该桶的结构是单项链表
                    //遍历该链表,找到要删除的节点,并赋值给node
                    do {
                        if (e.hash == hash &&
                            ((k = e.key) == key ||
                             (key != null && key.equals(k)))) {
                            node = e;
                            break;
                        }
                        p = e;
                    } while ((e = e.next) != null);
                }
            }
            //node!= null,说明hashMap中存在要删除的节点
            //matchValue参数可以用来决定是否要用需要比较节点的值,如果matchValue = false
            //那么不论怎么样(!matchValue || (v = node.value) == value || (value != null && value.equals(v))))都为true
            if (node != null && (!matchValue || (v = node.value) == value ||
                                 (value != null && value.equals(v)))) {
                //如果要删除的节点是红黑树结构
                if (node instanceof TreeNode)
                    //从红黑树中删除该节点
                    ((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
                //如果要删除的节点是桶的头节点
                else if (node == p)
                    tab[index] = node.next;
                //要删除的节点是链表的非头节点
                else
                    //p是node的前一个节点
                    p.next = node.next;
                //操作数++
                ++modCount;
                //删除后元素数量减1
                --size;
                //该方法是一个包权限的方法,在HashMap中是一个空方法,可以被包内覆盖,作用是在删除一个节点后调用
                afterNodeRemoval(node);
                //返回被删除的节点
                return node;
            }
        }
        //HashMap中不存在要删除的节点返回null
        return null;
    }

clear()方法

 //和JDK1.7版本的处理方式一样,都是使用gc来回收空间
 public void clear() {
        Node<K,V>[] tab;
        modCount++;
        if ((tab = table) != null && size > 0) {
            size = 0;
            for (int i = 0; i < tab.length; ++i)
                tab[i] = null;
        }
    }

containsValue()方法

public boolean containsValue(Object value) {
        Node<K,V>[] tab; V v;
        if ((tab = table) != null && size > 0) {
            for (int i = 0; i < tab.length; ++i) {
            	//不管是红黑树还是链表都可以这个遍历,主要是因为treeifyBin方法,将红黑树节点也形成了一条链
                for (Node<K,V> e = tab[i]; e != null; e = e.next) {
                    if ((v = e.value) == value ||
                        (value != null && value.equals(v)))
                        return true;
                }
            }
        }
        return false;
    }

5.resize()方法多线程数据丢失的原因

在JDK1.7版本的HashMap中,为了避免Hash冲突采用的是头插法的方式向链表中插入新的节点,在多个线程同时进行扩容时,就有可能造成链表成环的情况,一旦链表成环,我们遍历时就会陷入死循环,所以在JDK1.8的版本中使用了尾插法的方式,但是这样就多线程安全了吗,答案是否定的,采用尾插法虽然避免了链表成环的问题,但是产生了新的问题——数据丢失,所以HashMap仍然不能再多线程的环境下使用。

如何造成数据丢失,下面的代码是resize方法的一部分

  1 if (oldTab != null) {
  2          for (int j = 0; j < oldCap; ++j) {
  3              Node<K,V> e;
  4              if ((e = oldTab[j]) != null) {
  5                 oldTab[j] = null;//通过gc回收空间
  6					if (e.next == null)
  7                   //通过e节点的hash值,对新容量求出新的下标,放入到新数组中即可
  8                    newTab[e.hash & (newCap - 1)] = e;

假设有两个线程A和线程B共同执行resize方法
线程A执行完第1行,时间片段到了,该线程被阻塞,线程B抢占到了CPU
线程B执行完第5行,时间片段结束,
线程A执行到第4行时,此时oldTab[j] == null,那么以e为头节点的链表或者红黑树就会被跳过去,新数组中将没有这些元素,这就造成了数据丢失

Top