ArrayList、LinkedList和HashMap源码梳理

ArrayList

ArrayList、LinkedList和HashMap源码梳理

add(E e):新增元素

1、先判断是否需要扩容,如果需要就进行扩容,然后将元素存在size的位置,如果ArrayList为空的时候,进来的第一个元素,那么就应该将该元素放在ArrayList的第0个位置,这个时候即elementData[0] = e;然后size大小再进行++操作,表示这个时候ArrayList的大小增加了1

public boolean add(E e) {    /** 确定是否需要扩容,如果需要,则进行扩容操作*/    ensureCapacityInternal(size + 1);  // Increments modCount!!    // eg1:size=0,elementData[0]="a1",然后a自增为1    elementData[size++] = e;    return true; } 

2、传入容器元素个数+1的值给ensureCapacityInternal方法,该方法中进行了ArrayList大小计算。该最小容量指的是ArrayList中现在的元素个数,再+1,因为我们要做的是保存操作,保存之后ArrayList大小就会+1,这样的话我们就需要保证ArrayList是否可以满足本次添加

// eg1:第一次新增元素,所以size=0,则:minCapacity=size+1=1 private void ensureCapacityInternal(int minCapacity) {     // eg1:第一次新增元素,calculateCapacity方法返回值为DEFAULT_CAPACITY=10     ensureExplicitCapacity(calculateCapacity(elementData, minCapacity)); } 

在此方法中,我们进行重新计算ArrayList所需要的的容量大小,如果ArrayList中没有数据,那么ArrayList的大小就为10,如果不为空,那就返回ArrayList中元素的个数

/** * 计算ArrayList的容量  *  * 如果elementData数组中没有已存储的元素,则返回默认值10  * 否则,返回minCapacity。  *  * @param elementData 底层存储ArrayList元素的数组  * @param minCapacity ArrayList中的元素个数  * @return  */ // eg1:第一次新增元素,elementData={} minCapacity=1 private static int calculateCapacity(Object[] elementData, int minCapacity) {     if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {         // eg1:满足if判断,DEFAULT_CAPACITY=10         return Math.max(DEFAULT_CAPACITY, minCapacity);     }     return minCapacity; } 

当第一次增加元素的时候,传进来的这个minCapacity大小为默认值10,因为我刚开始什么数据都没有的时候,我所需要的容量是10,那我所需要的容量大于我现在容器的大小,我就要进行一次扩容操作。
modCount成员变量记录着集合的修改次数,也就是每次add或者remove它的值都会加1
ArrayList是非线程安全的,在使用迭代器遍历的时候,用来检查列表中的元素是否发生结构性变化(列边元素数量发生改变了),主要是在多线程环境下使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构。即,在多线程对一个ArrayList的数据操作的时候,它会去判断遍历次数与modcount是否相等,如果不等就会抛出异常CurrentModificationException

/** * 确保明确的ArrayList的容量 * @param minCapacity ArrayList所需的最小容量 */ // eg1:第一次新增元素,minCapacity=10 private void ensureExplicitCapacity(int minCapacity) {    // eg1: modCount++后,modCount=1    modCount++;     /** 如果所需的最小容量大于elementData数组的容量,则进行扩容操作 */    if (minCapacity - elementData.length > 0) { // eg1:10-0=10,满足扩容需求        // eg1:minCapacity=10        grow(minCapacity);    } } 

扩容操作,传进来的参数是所需要的最小容量,如果是第一次新增元素,那长度就要扩容为10。
记录oldCapacity,newCapacity为oldCapacity的1.5倍
如果新的长度newCapacity依然无法满足需要的最小扩容量minCapacity,则新的扩容长度值为minCapacity,因为我们扩容最终的目的是要≥minCapacity,那当我们的原newCapacity小于minCapacity的时候,那我们就需要将newCapacity设置为minCapacity即10。
如果newCapacity超出了最大的数组长度MAX_ARRAY_SIZE

Integer.MAX_VALUE - 8的原因:在数组的对象头里有一个_length字段,记录数组长度,只需要去读_length字段就可以了,所以ArrayList中定义的最大长度为Integer最大值减8,这个8就是就是存了数组_length字段。

/** * The maximum size of array to allocate. * Some VMs reserve some header words in an array. * Attempts to allocate larger arrays may result in * OutOfMemoryError: Requested array size exceeds VM limit * * 要分配的数组的最大大小。一些vm在数组中保留一些头字。 * 尝试分配较大的数组可能会导致OutOfMemory错误:请求的数组大小超过了虚拟机限制 */ // MAX_ARRAY_SIZE=2147483639=01111111 11111111 11111111 11110111 private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8; 

那么调用方法hugeCapacity,将minCapacity作为参数,此时的minCapacity为传进来的10 ,如果小于0(有符号整数,最高位1表示负数),就抛出OutOfMemoryError,否则判断minCapacity与MAX_ARRAY_SIZE的关系,如果minCapacity大,那么取Integer的最大值,如果MAX_ARRAY_SIZE大,则取MAX_ARRAY_SIZE赋值给newCapacity

private static int hugeCapacity(int minCapacity) {     if (minCapacity < 0) { // overflow         throw new OutOfMemoryError();     }     return (minCapacity > MAX_ARRAY_SIZE) ? Integer.MAX_VALUE : MAX_ARRAY_SIZE; } 

最后,扩展数组长度为newCapacity,并且将旧数组中的元素赋值到新的数组中

/**  * Increases the capacity to ensure that it can hold at least the  * number of elements specified by the minimum capacity argument.  *  * 扩容操作  *  * @param minCapacity 所需要的最小扩容量  */ // eg1:第一次新增元素,minCapacity=10,即:需要将elementData的0长度扩容为10长度。 private void grow(int minCapacity) {      /** 原有数组elementData的长度*/     int oldCapacity = elementData.length; // eg1:oldCapacity=0      /**      * A >> 1 等于 A/2      * eg: 3 >> 1 = 3/2 = 1      *     4 >> 1 = 4/2 = 2      * ------------------------      * A << 1 等于 A*2      * eg: 3 << 1 = 3*2 = 6      *     4 << 1 = 4*2 = 8      *      * 000100 >> 1 = 000010      * 000100 << 1 = 001000      */     /** 新增oldCapacity的一半整数长度作为newCapacity的额外增长长度 */     int newCapacity = oldCapacity + (oldCapacity >> 1); // eg1:newCapacity=0+(0>>1)=0      /** 新的长度newCapacity依然无法满足需要的最小扩容量minCapacity,则新的扩容长度为minCapacity */     if (newCapacity - minCapacity < 0) {         // eg1:newCapacity=10         newCapacity = minCapacity;     }      /** 新的扩容长度newCapacity超出了最大的数组长度MAX_ARRAY_SIZE */     if (newCapacity - MAX_ARRAY_SIZE > 0) {         newCapacity = hugeCapacity(minCapacity);     }      /** 扩展数组长度为newCapacity,并且将旧数组中的元素赋值到新的数组中 */     // eg1:newCapacity=10, 扩容elementData的length=10     elementData = Arrays.copyOf(elementData, newCapacity); } 

get(int index):获取元素

两个步骤:一检查索引范围、二返回对应位置上的元素

/** * Returns the element at the specified position in this list. * 返回list中指定位置的元素 * @param index index of the element to return * @return the element at the specified position in this list * @throws IndexOutOfBoundsException {@inheritDoc} */ public E get(int index) {     rangeCheck(index);     return elementData(index); } 

如果index大于等于list大小(因为数组的index下标都是从0开始的,所以是包含等于list),抛出IndexOutOfBoundsException

/**  * Checks if the given index is in range.  If not, throws an appropriate  * runtime exception.  This method does *not* check if the index is  * negative: It is always used immediately prior to an array access,  * which throws an ArrayIndexOutOfBoundsException if index is negative.  */ // eg1:index=0 private void rangeCheck(int index) {     if (index >= size) {         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));     } } 

返回指定位置上的元素,并将元素强转为泛型中指定的类型

E elementData(int index) {     return (E) elementData[index]; } 

set(int index, E element):设置元素

三步操作:
一、判断index是否在范围内,与get方法中的范围检查方法一致
二、获得index下标对应的旧值、用于方法返回
三、将index下标对应的值,赋值为新值——element

 /**  * Replaces the element at the specified position in this list with  * the specified element.  *   * @param index   index of the element to replace  * @param element element to be stored at the specified position  * @return the element previously at the specified position  * @throws IndexOutOfBoundsException {@inheritDoc}  */ public E set(int index, E element) {     /** 判断index是否超出了ArrayList中包含的元素数量,如果超出,则抛出IndexOutOfBoundsException异常 */     rangeCheck(index);      /** 获得index下标对应的旧值 */     E oldValue = elementData(index);      /** 将index下标对应的值,赋值为新值——element */     elementData[index] = element;      /** 返回index下标对应的旧值 */     return oldValue; } 

remove(int index):删除元素

1.范围校验
2.modCount++:modCount成员变量记录着集合的修改次数,也就是每次add或者remove它的值都会加1(modCount用于控制用户在并发的情况修改arraylist里的数据造成数据混乱的变量,每循环一次,就会对这个变量加1)
ArrayList是非线程安全的,在使用迭代器遍历的时候,用来检查列表中的元素是否发生结构性变化(列边元素数量发生改变了),主要是在多线程环境下使用,防止一个线程正在迭代遍历,另一个线程修改了这个列表的结构。即,在多线程对一个ArrayList的数据操作的时候,它会去判断遍历次数与modcount是否相等,如果不等就会抛出异常CurrentModificationException
3.将移除的位置后面的元素整体向前移动一位
4.通知jvm将之前的最后一位元素进行垃圾回收
5.返回已被删除的元素

// eg1:elementData中保存了{"a1","a2","a3","a4"},删除第一个元素,即:index=0 public E remove(int index) {     /** 校验传入的参数index是否超出了数组的最大下标,如果超出,则抛出:IndexOutOfBoundsException异常*/     rangeCheck(index);      /** 集合的修改次数加1 */     modCount++;      // eg1:String oldValue="a1"     /** 获得index下标对应的旧值oldValue */     E oldValue = elementData(index);      // eg1:numMoved=4-0-1=3     /** 获得需要移动元素的个数 */     int numMoved = size - index - 1;     if (numMoved > 0) {         /** 从需要删除的index后一位开始到末尾的这部分数据,整体都向前移动一个元素。*/         System.arraycopy(elementData, index + 1, elementData, index, numMoved);     }     /** 通知jvm将之前的最后一位元素进行垃圾回收 */     elementData[--size] = null; // clear to let GC do its work      /** 返回已被删除的元素 */     return oldValue; } 

LinkedList

ArrayList、LinkedList和HashMap源码梳理

add(E e):新增元素

 /**  * Appends the specified element to the end of this list.  *  * <p>This method is equivalent to {@link #addLast}.  *  * @param e element to be appended to this list  * @return {@code true} (as specified by {@link Collection#add})  */ // eg1: e="a1" public boolean add(E e) {     linkLast(e);     return true; } 
/**  * 将新添加的元素e作为链表的最后一个元素, 并维护进去  */ // eg1: e="a1" void linkLast(E e) {     final Node<E> l = last;      // eg1: newNode    null<--"a1"-->null     /** 创建一个e的Node节点,前置指向原last节点,后置指向null */     final Node<E> newNode = new Node<>(l, e, null);      /** 将newNode节点赋值为last节点 */     last = newNode;      // eg1: l=null     if (l == null) {         /** 如果是第一个添加的元素,则first指针指向该结点*/         first = newNode; // eg1: first指向newNode     } else {         /** 如果不是第一个添加进来的元素,则更新l的后置结点指向新添加的元素结点newNode*/         l.next = newNode;     }     size++;     modCount++; } 

get(int index):获取元素

两步
一、检查元素索引是否越界
二、返回对应结点的元素值

/**  * Returns the element at the specified position in this list.  *  * @param index index of the element to return  * @return the element at the specified position in this list  * @throws IndexOutOfBoundsException {@inheritDoc}  */ /**  * 查询指定下标index的结点  */ public E get(int index) {     checkElementIndex(index);     return node(index).item; } 

一、索引范围必须是在0-size之间,不包含size。不在此范围之中,抛出越界异常

/**  * 校验是否越界  *  * @param index  */ private void checkElementIndex(int index) {     /** index >= 0 && index < size */     if (!isElementIndex(index)) {         throw new IndexOutOfBoundsException(outOfBoundsMsg(index));     } }  /**  * Tells if the argument is the index of an existing element.  */ private boolean isElementIndex(int index) {     return index >= 0 && index < size; } 

二、返回结点的值
如果需要获取的index小于总长度size的一半,则从头部开始向后遍历查找
否则从尾部开始向前遍历查找

/**  * Returns the (non-null) Node at the specified element index.  *  * 根据传入的index值,返回对应的结点node  */ // eg1:index=0 Node<E> node(int index) {     // assert isElementIndex(index);      /** 如果需要获取的index小于总长度size的一半,则从头部开始向后遍历查找 */     if (index < (size >> 1)) {         Node<E> x = first;         for (int i = 0; i < index; i++) {             x = x.next; // 从first结点向后next查找,直到index下标node,返回node         }         return x;     } else { /** 从尾部开始向前遍历查找 */         Node<E> x = last;         for (int i = size - 1; i > index; i--) {             x = x.prev; // 从last结点向前prev查找,直到index下标node,返回node         }         return x;     } } 

HashMap

put(K key, V value)

/**  * Associates the specified value with the specified key in this map.  * If the map previously contained a mapping for the key, the old  * value is replaced.  *  * @param key   key with which the specified value is to be associated  * @param value value to be associated with the specified key  * @return the previous value associated with <tt>key</tt>, or  * <tt>null</tt> if there was no mapping for <tt>key</tt>.  * (A <tt>null</tt> return can also indicate that the map  * previously associated <tt>null</tt> with <tt>key</tt>.)  */ // eg1: hashMap.put(0, "a0"); // eg2: hashMap.put(1, "a1"); // eg3: hashMap.put(16, "a16"); // eg4: hashMap.put(32, "a32"); //eg5:hashMap.put(48,"a48");hashMap.put(64,"a64");hashMap.put(80,"a80"); hashMap.put(96, "a96");hashMap.put(112, "a112"); // eg6: hashMap.put(128, "a128"); public V put(K key, V value) { 	// 我们本次使用的数二进制位数都是低于十六位的,所以都是原数输出,即输入1,hash(1)等于1     return putVal(hash(key), key, value, false, true); } 

hash方法
ArrayList、LinkedList和HashMap源码梳理

/** * Computes key.hashCode() and spreads (XORs) higher bits of hash * to lower.  Because the table uses power-of-two masking, sets of * hashes that vary only in bits above the current mask will * always collide. (Among known examples are sets of Float keys * holding consecutive whole numbers in small tables.)  So we * apply a transform that spreads the impact of higher bits * downward. There is a tradeoff between speed, utility, and * quality of bit-spreading. Because many common sets of hashes * are already reasonably distributed (so don't benefit from * spreading), and because we use trees to handle large sets of * collisions in bins, we just XOR some shifted bits in the * cheapest possible way to reduce systematic lossage, as well as * to incorporate impact of the highest bits that would otherwise * never be used in index calculations because of table bounds. */ // egx: key="k1" // eg1: key=0 static final int hash(Object key) {    int h;    /**     * 按位异或运算(^):两个数转为二进制,然后从高位开始比较,如果相同则为0,不相同则为1。     *     * 扰动函数————(h = key.hashCode()) ^ (h >>> 16) 表示:     * 	>>> : 无符号右移,忽略符号位,空位都以0补齐     *      将key的哈希code一分为二。其中:     *      【高半区16位】数据不变。     *      【低半区16位】数据与高半区16位数据进行异或操作,以此来加大低位的随机性。     * 注意:如果key的哈希code小于等于16位,那么是没有任何影响的。只有大于16位,才会触发扰动函数的执行效果。     * */    // egx: 110100100110^000000000000=110100100110,由于k1的hashCode都是在低16位,所以原样返回3366    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);     /**     * case1:     *  h=高16位(全是0) and 低16位(有1)     *  h >>> 16 = 低16位全部消失,那么变成了32位(全是0)     *  h ^ (h >>> 16) = 原样输出     * case2:     *  h=高16位(有1) and 低16位(有1)     *  h >>> 16 = 低16位全部消失,那么变成了高16位(全是0)and低16位(有1)     *  h ^ (h >>> 16) = 不是原样输出  将原高16位于原低16位进行扰动。     */ } 

扰动函数————(h = key.hashCode()) ^ (h >>> 16)
我们的例子采用的key都是Integer类型,是因为Integer类型的hashCode值即为他本身
不使用String的原因是因为没有办法准确的插入到某个位置
Integer的hashCode()方法

/**  * Returns a hash code for this {@code Integer}.  */ @Override public int hashCode() {     return Integer.hashCode(value); }  /**  * Returns a hash code for a {@code int} value; compatible with  */ public static int hashCode(int value) {     return value; } 

String的hashCode()

/** * 计算String的哈希值 * * 假设 n=3 * i=0 -> h = 31 * 0 + val[0] * i=1 -> h = 31 * (31 * 0 + val[0]) + val[1] * i=2 -> h = 31 * (31 * (31 * 0 + val[0]) + val[1]) + val[2] *        h = 31*31*31*0 + 31*31*val[0] + 31*val[1] + val[2] *        h = 31^(n-1)*val[0] + 31^(n-2)*val[1] + val[2] * 即: *    s[0]*31^(n-1) + s[1]*31^(n-2) + ... + s[n-1] */ // eg1: key="k1" public int hashCode() {    // eg1: hash=0 h=0    int h = hash;    // eg1: value={'k','1'} value.length=2    /** 只有第一次计算hash值时,才进入下面逻辑中。此后调用hashCode方法,都直接返回hash*/    if (h == 0 && value.length > 0) {        char val[] = value;         for (int i = 0; i < value.length; i++) {            // eg1: val[0]=107 val[1]=49            h = 31 * h + val[i];        }        // eg1: 31(31*0+107)+49=3366        hash = h;    }    return h; } 

putVal(hash(key), key, value, false, true)
ArrayList、LinkedList和HashMap源码梳理

/** * Implements Map.put and related methods. * * @param hash         key的哈希值 * @param key          key值 * @param value        value值 * @param onlyIfAbsent 如果是true,则不改变已存在的value值 * @param evict        驱逐,赶出,逐出 if false, the table is in creation mode. * * @return previous value, or null if none */ // eg1: hash=0 key=0 value="a0" onlyIfAbsent=false evict=true // eg2: hash=1 key=1 value="a1" onlyIfAbsent=false evict=true // eg3: hash=16 key=16 value="a16" onlyIfAbsent=false evict=true // eg4: hash=32 key=32 value="a32" onlyIfAbsent=false evict=true // eg5: 由于执行步骤与eg4相似,故略过。 // eg6: hash=128 key=128 value="a128" onlyIfAbsent=false evict=true final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {    Node<K, V>[] tab;    Node<K, V> p;    int n, i;     // eg1: table=null    // eg2: table是长度为16的Node数组,且table[1]=Node(1, 1, "a1", null)    // eg3: table是长度为16的Node数组,且table[1]=Node(1, 1, "a1", null) ... table[6]=Node(6, 6, "a6", null)    // eg4: table是长度为16的Node数组,且table[1]=Node(1, 1, "a1", null) ... table[6]=Node(6, 6, "a6", null)    // eg6: table是长度为16的Node数组,且table[1]=Node(1, 1, "a1", null) ... table[6]=Node(6, 6, "a6", null)    /** 如果是空的table,那么默认初始化一个长度为16的Node数组*/    if ((tab = table) == null || (n = tab.length) == 0) {        // eg1: resize返回(Node<K, V>[]) new Node[16],所以:tab=(Node<K, V>[]) new Node[16], n=16        n = (tab = resize()).length;    }     // eg1: i = (n-1)&hash = (16-1)&0 = 1111&0000 = 0000 = 0; 即:p=tab[0]=null    // eg2: i = (n-1)&hash = (16-1)&1 = 1111&0001 = 0001 = 1; 即:p=tab[1]=null    // eg3: i = (n-1)&hash = (16-1)&16 = 1111&10000 = 0000 = 0; 即:p=tab[0]=Node(0, 0, "a0", null)    // eg4: i = (n-1)&hash = (16-1)&32 = 1111&100000 = 0000 = 0; 即:p=tab[0]=Node(0, 0, "a0", null)    // eg6: i = (n-1)&hash = (16-1)&128 = 1111&10000000 = 0000 = 0; 即:p=tab[0]=Node(0, 0, "a0", null)    /** 如果计算后的下标i,在tab数组中没有数据,那么则新增Node节点*/    if ((p = tab[i = (n - 1) & hash]) == null) {        // eg1: tab[0] = newNode(0, 0, "a0", null)        // eg2: tab[1] = newNode(1, 1, "a1", null)        tab[i] = newNode(hash, key, value, null);    } else { /** 如果计算后的下标i,在tab数组中已存在数据,则执行以下逻辑 */        Node<K, V> e;        K k;        // eg3: p.hash==0, hash==16,所以返回false        // eg4: p.hash==0, hash==32,所以返回false        // eg6: p.hash==0, hash==128,所以返回false        if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) { /** 如果与已存在的Node是相同的key值*/            e = p;        }        // eg3: p instanceof Node,所以为false        // eg4: p instanceof Node,所以为false        // eg6: p instanceof Node,所以为false        else if (p instanceof TreeNode) { /** 如果与已存在的Node是相同的key值,并且是树节点*/            e = ((TreeNode<K, V>) p).putTreeVal(this, tab, hash, key, value);        } else { /** 如果与已存在的Node是相同的key值,并且是普通节点,则循环遍历链式Node,并对比hash和key,如果都不相同,则将新的Node拼装到链表的末尾。如果相同,则进行更新。*/            for (int binCount = 0; ; ++binCount) {                // eg3: p.next == null                // eg4-loop1: p.next == Node(16, 16, "a16", null) 不为空                // eg4-loop2: p.next == null                /** 获得p节点的后置节点,赋值给e。直到遍历到横向链表的最后一个节点,即:该节点的next后置指针为null */                if ((e = p.next) == null) {                    // eg3: p.next = newNode(16, 16, "a16", null);                    // eg4-loop2: p.next == newNode(32, 32, "a32", null);                    // eg6: p.next == newNode(128, 128, "a128", null);                    p.next = newNode(hash, key, value, null);                     // eg3: binCount == 0                    // eg4-loop2: binCount == 1                    /** 如果Node链表大于8个Node,那么变为红黑树 */                    if (binCount >= TREEIFY_THRESHOLD - 1) {                        // eg6: tab={newNode(0, 0, "a0", [指向后面1个链表中的7个node]), newNode(1, 1, "a1", null)}, hash=128                        treeifyBin(tab, hash);                    }                    // eg3: break                    // eg4-loop2: break                    break;                }                // eg4-loop1: e.hash==16 hash==32 所以返回false                /** 针对链表中的每个节点,都来判断一下,是否待插入的key与已存在的链表节点相同,如果相同,则跳出循环,并在后续的操作中,将该节点内容更新为最新的插入值 */                if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) {                    break;                }                // eg4-loop1: p=e=Node(16, 16, "a16", null)                p = e;            }        }         // eg3: e = null        // eg4: e = null        /** 如果存在相同的key值*/        if (e != null) {            // egx: String oldValue = "v1"            V oldValue = e.value;            // egx: onlyIfAbsent=false            if (!onlyIfAbsent || oldValue == null) {                // egx: e = Node(3366, "k1", "v2", null)                /** 则将新的value值进行更新*/                e.value = value;            }            afterNodeAccess(e);            // egx: 返回oldValue="v1"            return oldValue;        }    }     // eg1: modCount==0 ++modCount==1    // eg2: modCount==1 ++modCount==2    // eg3: modCount==7 ++modCount==8    // eg4: modCount==8 ++modCount==9    ++modCount;     // eg1: size=0, threshold=12    // eg2: size=1, threshold=12    // eg3: size=7, threshold=12    // eg4: size=8, threshold=12    if (++size > threshold) {        resize();    }    afterNodeInsertion(evict); /** doing nothing */    return null; } 
// 存储Node数组。 transient Node<K, V>[] table; 

n = (tab = resize()).length;
resize()
ArrayList、LinkedList和HashMap源码梳理
ArrayList、LinkedList和HashMap源码梳理

/** * Initializes or doubles table size.  If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table 指的就是我们hashMap中的纵向表 * * table扩容 * * 常量命名解释: * Tab——>Table 表 * Cap——>Capacity 容量 * Thr——>Threshold 阈值,即达到这个值就应该开始扩容 */ final Node<K, V>[] resize() {    // eg1: table=null    // eg6: table != null    Node<K, V>[] oldTab = table;    // eg1: oldCap=0    // eg6: oldCap=16    int oldCap = (oldTab == null) ? 0 : oldTab.length;    // eg1: oldThr=threshold=0    // eg6: oldThr=threshold=12    int oldThr = threshold;    int newCap = 0;    int newThr = 0;    /** 第一步:根据情况,调整新表的容量newCap和阈值newThr*/    if (oldCap > 0) {        /** 如果老table的长度大于等于2^30(1 << 30)        1后面有30个0*/        if (oldCap >= MAXIMUM_CAPACITY) {            threshold = Integer.MAX_VALUE; /** 2^31-1  1后面有30个1 */            return oldTab;        }        /** 如果将老Table的长度增长2倍作为新的容量长度(newCap),是否小于2^30(1 << 30) 并且 老Table长度是否大于等于16(1 << 4)*/        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {            // eg6: newCap=32, newThr=24            newThr = oldThr << 1;        }    } else if (oldThr > 0) {        newCap = oldThr;    } else {        // eg1: oldCap=0 newCap=16 newThr=0.75f*16=12        // 即我的表容量为16,但我的阀值为12就是说,当我集合中的元素大小为12的时候我就要去做一个扩容操作,而不是等到16再去进行扩容。这里就是一个提前扩容的机制        newCap = DEFAULT_INITIAL_CAPACITY; /** 默认【表容量】为16(1 << 4) */        newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); /** 默认【阈值因子】为0.75f */    }     if (newThr == 0) {        float ft = (float) newCap * loadFactor;        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ? (int) ft : Integer.MAX_VALUE);    }    // eg1: threshold=newThr=12    // eg6: threshold=newThr=24    threshold = newThr;     /** 第二步:根据newCap和newThr,构建新数组 */    /** 初始化新表*/    @SuppressWarnings({"rawtypes", "unchecked"})    Node<K, V>[] newTab = (Node<K, V>[]) new Node[newCap];    // eg1: table=newTab=(Node<K, V>[]) new Node[16];    // eg6: table=newTab=(Node<K, V>[]) new Node[32];    table = newTab;    // eg1: oldTab=null    if (oldTab != null) { /** 如果老的table里有数据,则进行数据迁移*/        // eg6: oldCap=16        /** 循环纵向数组中的每个槽位Cap */        for (int j = 0; j < oldCap; ++j) {            Node<K, V> e;            // eg6-loop1: j=0, e=oldTab[0]=Node(0, 0, "a0", nodeRef)            // eg6-loop2: j=1, e=oldTab[1]=Node(1, 1, "a1", null)            if ((e = oldTab[j]) != null) {                // eg6-loop1: oldTab[0] = null                // eg6-loop2: oldTab[1] = null                oldTab[j] = null;                // eg6-loop1: e.next=Node(16, 16, "a16", nodeRef)                // eg6-loop2: e.next==null                if (e.next == null) { /** 没有后置节点,说明e是最后一个节点*/                    // eg6-loop2: e.hash==1, newCap=32, 1&(32-1)==1 即:newTab[1]=Node(1, 1, "a1", null)                    newTab[e.hash & (newCap - 1)] = e;                } else if (e instanceof TreeNode) { /** e是树节点*/                    ((TreeNode<K, V>) e).split(this, newTab, j, oldCap);                } else {                    Node<K, V> loHead = null;                    Node<K, V> loTail = null;                    Node<K, V> hiHead = null;                    Node<K, V> hiTail = null;                    Node<K, V> next;                    // 以下进行的是横向循环                    do {                        // eg6-loop1-loop1: next=e.next=Node(16, 16, "a16", nodeRef)                        // eg6-loop1-loop2: next=e.next=Node(32, 32, "a32", nodeRef)                        // eg6-loop1-loop3: next=e.next=Node(48, 48, "a48", nodeRef)                        // eg6-loop1-loop4: next=e.next=Node(64, 64, "a64", nodeRef)                        // eg6-loop1-loop5: next=e.next=Node(80, 80, "a80", nodeRef)                        // eg6-loop1-loop6: next=e.next=Node(96, 96, "a96", nodeRef)                        // eg6-loop1-loop7: next=e.next=Node(112, 112, "a112", nodeRef)                        // eg6-loop1-loop8: next=e.next=Node(128, 128, "a128", nodeRef)                        // eg6-loop1-loop9: next=e.next=null                        next = e.next; /** 获得oldTab数组下标的Node列表的下一个节点*/                        // eg6-loop1-loop1: e.hash=0, oldCap=16,  00000000&10000==00000==0                        // eg6-loop1-loop2: e.hash=16, oldCap=16, 00010000&10000==10000==16                        // eg6-loop1-loop3: e.hash=32, oldCap=16, 00100000&10000==00000==0                        // eg6-loop1-loop4: e.hash=48, oldCap=16, 00110000&10000==10000==16                        // eg6-loop1-loop5: e.hash=64, oldCap=16, 01000000&10000==00000==0                        // eg6-loop1-loop6: e.hash=80, oldCap=16, 01010000&10000==00000==16                        // eg6-loop1-loop7: e.hash=96, oldCap=16, 01100000&10000==00000==0                        // eg6-loop1-loop8: e.hash=112, oldCap=16, 01110000&10000==10000==16                        // eg6-loop1-loop9: e.hash=128, oldCap=16, 10000000&10000==10000==0                        if ((e.hash & oldCap) == 0) { /** 计算e在老表oldTab的下标,如果是第一个Node,即:下标index==0*/                            if (loTail == null) {                                // eg6-loop1-loop1: loHead=e=Node(0, 0, "a0", nodeRef)                                loHead = e; /** 将loHead指向oldTab数组第一个下标的第一个元素e*/                            } else {                                // eg6-loop1-loop3: loTail.next=e=Node(32, 32, "a32", nodeRef)                                // eg6-loop1-loop5: loTail.next=e=Node(64, 64, "a64", nodeRef)                                // eg6-loop1-loop7: loTail.next=e=Node(96, 96, "a96", nodeRef)                                // eg6-loop1-loop9: loTail.next=e=Node(128, 128, "a128", nodeRef)                                loTail.next = e; /** 建立新的链表 */                            }                            // eg6-loop1-loop1: loTail=e=Node(0, 0, "a0", nodeRef)                            // eg6-loop1-loop3: loTail=e=Node(32, 32, "a32", nodeRef)                            // eg6-loop1-loop5: loTail=e=Node(64, 64, "a64", nodeRef)                            // eg6-loop1-loop7: loTail=e=Node(96, 96, "a96", nodeRef)                            // eg6-loop1-loop9: loTail=e=Node(128, 128, "a128", nodeRef)                            loTail = e; /** 将loTail指向oldTab数组第一个下标的最后一个元素e*/                        } else { /** 如果不是oldTab中的第一个下标Node*/                            if (hiTail == null) {                                // eg6-loop1-loop2: hiHead=e=Node(16, 16, "a16", nodeRef)                                hiHead = e;                            } else {                                // eg6-loop1-loop4: hiTail.next=e=Node(48, 48, "a48", nodeRef)                                // eg6-loop1-loop6: hiTail.next=e=Node(80, 80, "a80", nodeRef)                                // eg6-loop1-loop8: hiTail.next=e=Node(112, 112, "a112", nodeRef)                                hiTail.next = e; /** 建立新的链表 */                            }                            // eg6-loop1-loop2: hiTail=e=Node(16, 16, "a16", nodeRef)                            // eg6-loop1-loop4: hiTail=e=Node(48, 48, "a48", nodeRef)                            // eg6-loop1-loop6: hiTail=e=Node(80, 80, "a80", nodeRef)                            // eg6-loop1-loop8: hiTail=e=Node(112, 112, "a112", nodeRef)                            hiTail = e;                        }                    }                    // eg6-loop1-loop1: e=next=Node(16, 16, "a16", nodeRef)                    // eg6-loop1-loop2: e=next=Node(32, 32, "a32", nodeRef)                    // eg6-loop1-loop3: e=next=Node(48, 48, "a48", nodeRef)                    // eg6-loop1-loop4: e=next=Node(64, 64, "a64", nodeRef)                    // eg6-loop1-loop5: e=next=Node(80, 80, "a80", nodeRef)                    // eg6-loop1-loop6: e=next=Node(96, 96, "a96", nodeRef)                    // eg6-loop1-loop7: e=next=Node(112, 112, "a112", nodeRef)                    // eg6-loop1-loop8: e=next=Node(128, 128, "a128", nodeRef)                    // eg6-loop1-loop9: e=next=null                    while ((e = next) != null); /** do-while */                     // eg6-loop1: loTail=Node(128, 128, "a128", null)                    if (loTail != null) {                        loTail.next = null;                        // eg6-loop1: j=0, newTab[0]=loHead=Node(0, 0, "a0", nodeRef)                        newTab[j] = loHead;                    }                     // eg6-loop1: loTail=Node(112, 112, "a112", nodeRef)                    if (hiTail != null) {                        // eg6-loop1: loTail=Node(112, 112, "a112", null)                        hiTail.next = null;                        // eg6-loop1: j=0, oldCap=16, newTab[16]=hiHead=Node(16, 16, "a16", nodeRef)                        newTab[j + oldCap] = hiHead;                    }                }            }        }    }    // eg1: newTab = (Node<K, V>[]) new Node[16]    // eg6: newTab = (Node<K, V>[]) new Node[32]    return newTab; } 

最终结论:即当Node链表大于8个Node且表tab的长度大于64才转变为红黑树
treeifyBin(tab, hash)

/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ // eg6: hash=128 // tab[0]=Node(0, 0, "a0", nodeRef)——>Node(16, 16, "a16", nodeRef)——>Node(32, 32, "a32", nodeRef)——>Node(48, 48, "a48",nodeRef)——>Node(64, 64, "a64", node)——>Node(80, 80, "a80", node)——>Node(96, 96, "a96", node)——>Node(112, 112, "a112", node) // tab[1]=Node(1, 1, "a1", null) final void treeifyBin(Node<K, V>[] tab, int hash) {    int n;    int index;    Node<K, V> e;    //  eg6: tab !=null, tab.length=16    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) { /** 当表tab的长度小于64时,只扩展数组大小,不转换为树 */        //  eg6: 执行resize()        resize();    } else if ((e = tab[index = (n - 1) & hash]) != null) { /** 如果新增的node要插入的数组位置已经有node存在了,取出该位置的node节点*/        TreeNode<K, V> hd = null; /** 头节点*/        TreeNode<K, V> tl = null; /** 尾节点*/        do {            /** 将Node转化为TreeNode——> new TreeNode<>(p.hash, p.key, p.value, next);*/            TreeNode<K, V> p = replacementTreeNode(e, null);             /** 将每个Node转换为TreeNode,并且用prev和next指针进行链接,并以hd为头节点*/            if (tl == null) {                hd = p;            } else {                p.prev = tl;                tl.next = p;            }            tl = p;        } while ((e = e.next) != null);         /** 如果头节点hd不为null,则进行树型化操作*/        if ((tab[index] = hd) != null) {            hd.treeify(tab);        }    } } 

版权声明:玥玥 发表于 2021-03-14 11:50:45。
转载请注明:ArrayList、LinkedList和HashMap源码梳理 | 女黑客导航