03-15 09:17 阅读 190

ArrayList、LinkedList和HashMap源码梳理

ArrayList

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）

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

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方法

/**

* 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)

/**

* 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;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

// 存储Node数组。

transient Node<K, V>[] table;

n = (tab = resize()).length;

resize()

/**

* 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;

}

100

101

102

103

104

105

106

107

108

109

110

111

112

113

114

115

116

117

118

119

120

121

122

123

124

125

126

127

128

129

130

131

132

133

134

135

136

137

138

139

140

141

142

143

144

145

146

147

148

149

150

151

152

153

154

155

156

157

158

159

160

161

162

163

164

165

166

167

168

169

170

171

172

173

174

175

176

177

最终结论：即当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);

}

————————————————

原文链接：https://blog.csdn.net/weixin_41109763/article/details/114502188