hashmap的结构
Snip20180615_8.png
如上图所示，hashmap的组成有两部分，数组 + 链表，不过在jdk1.8之后，变成了数组 + 链表 + 树，树为红黑树。
在上图中，数组中存储的是 一个链表的头结点，即first，节点要放在哪个下标，需要通过hash(key.hashcode) % tab.length (对数据取模，不过实际运算时采用&按位与运算) 来计算。
数组的每个下标成员都是一个链表的头节点，链表元素之间维护一个指针，指向下一个元素。链表中的元素key值对应的hash(key.hashcode) % tab.length 都是相同的，也就是有相同的数组下标。
在jdk1.8之前，每个index对应的中都是一个单向链表，在极端情况下，如果每个key对应的index都相同，hashmap将会变成类似上图所示，index从1到7的数据都是空的，所有数据都在index=0处的链表中。假设此时有8个元素，如果对hashmap get数据，时间复杂度将从O(1)变成O(n).也就是从数组中根据下标直接取，变成了需要根据链表一个一个遍历查找。
而在jdk1.8之后，这部分实现做了优化，详见下文。
补充下数组和链表的特性：
数组必须事先定义固定的长度（元素个数），不能适应数据动态地增减的情况。当数据增加时，可能超出原先定义的元素个数；当数据减少时，造成内存浪费。
数组是静态分配内存，并且在内存中连续。
数组利用下标定位，时间复杂度为O(1)
数组插入或删除元素的时间复杂度O(n)
数组的特点是：寻址容易，插入和删除困难；
链表存储区间离散，占用内存比较宽松。
链表是动态分配内存，并不连续。
链表定位元素时间复杂度O(n)
链表插入或删除元素的时间复杂度O(1)
链表的特点是：寻址困难，插入和删除容易。</pre>
Node
hashmap中的基础元素：
/**
* Basic hash bin node, used for most entries. (See below for
* TreeNode subclass, and in Linkedhashmap for its Entry subclass.)
*/
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
public final K getKey() { return key; }
public final V getValue() { return value; }
public final String toString() { return key + "=" + value; }
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
public final boolean equals(Object o) {
if (o == this)
return true;
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
if (Objects.equals(key, e.getKey()) &&
Objects.equals(value, e.getValue()))
return true;
}
return false;
}
}
这个就是hashmap中的元素结构，实现了Map.Entry接口，可以看包含了四个属性：hash、key、value、next。
key、value很好理解，分别代表存储的泛型key和对应的泛型value。
next指向的是下一个节点，这里的存储结构是一个单向链表。
hash是指key的hash值，但并不是key.hashcode()，而是通过上文的hash方法得到的值。在jdk1.8中，就是(h = key.hashCode()) ^ (h >>> 16)。
从上面可以知道，hashmap中所有数据都是存在Node[]数据中的，但是怎么用一个数组完成了类似于上图的数组+链表结构呢？下面一一说明。
取get
先看下get的源码：
/**
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code (key==null ? k==null :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}. (There can be at most one such mapping.)
*
* <p>A return value of {@code null} does not <i>necessarily</i>
* indicate that the map contains no mapping for the key; it's also
* possible that the map explicitly maps the key to {@code null}.
* The {@link #containsKey containsKey} operation may be used to
* distinguish these two cases.
*
* @see #put(Object, Object)
*/
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Implements Map.get and related methods
*
* @param hash hash for key
* @param key the key
* @return the node, or null if none
*/
final Node<K,V> getNode(int hash, Object key) {
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) {
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}
可以看到，最终实现是在getNode中完成的。
这里详细看下getNode的实现：
先看最外层的if
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {......}
return null;
这里如果不满足if中的三个条件，就直接返回null。
- 条件一： (tab = table) != null，判断hashmap中的存储结构 table 是否为空，如果为空，直接中断判断，跳转到最后，返回null
- 条件二： (n = tab.length) > 0, 判断hashmap中的存储结构 table中是否有元素，如果没有，直接中断判断，跳转到最后，直接返回null
- 条件三：（first = tab[(n-1) & hash]) ！= null，注意这里，参照上面的indexFor方法，(n-1) & hash 是取模同样的效果，这里根据hash获取到的index下标，然后判断tab[下标]是否有对应的元素，如果没有，直接跳转到最后，返回null。
看内层的第一个if
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
return first;
这里判断first的第一个元素是不是需要的值，根据hash、key的值是否匹配来决定。
first是根据tab[(n-1) & hash]来取到的，也就是已经确定了数组下标对应的链表。
看内层第二个if
if ((e = first.next) != null) {
if (first instanceof TreeNode)
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
这里是常规操作，链表中第一个元素（头结点）如果不是需要get的值，那么会进入到这段代码。
首先会判断，是否为TreeNode（这是Node的孙子类，上面已有说明），如果是，会进入getTreeNode的逻辑，否则，进入一个do…while循环
do…while循环中，会根据单项链表来依次确认是否有匹配的数据。
存put
看下代码实现：
/**
* 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>.)
*/
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/**
* Implements Map.put and related methods
*
* @param hash hash for key
* @param key the key
* @param value the value to put
* @param onlyIfAbsent if true, don't change existing value
* @param evict if false, the table is in creation mode.
* @return previous value, or null if none
*/
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)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
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;
}
可以看到，实际的实现在putVal方法中，老规矩，还是一行一行的看：
第一个if判断：
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
如果table数组为null，或者数组长度为0，则走到扩容逻辑。
第二个if判断
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
如果数组对应的下标（通过 (n-1) & hash 来获取，其中n是数组tab的长度）为null，也就是对应位置没有元素，直接塞入即可。
else处理
也就是说，这里是table不为空，且table[i]的位置有元素的情况下，处理的逻辑。分两大步：
第一步，寻找需要将数据插入的位置-即e节点：
Node<K,V> e; K k;
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
for (int binCount = 0; ; ++binCount) {
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;
}
}
e代表需要插入的位置所对应的节点。
else中的第一个if：
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
在这里，如发现头结点p 其对应的hash、key值完全匹配，那么这个node对象就是要被覆盖的节点。
- else中的第二个if：
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
如果头节点已经是treeNode类型，就走到了红黑树的处理逻辑中，这块后续统一梳理。
- else中的else：
如果需要put的地方既不是头节点，也不是treeNode类型，那么就需要走以下处理：
/**
* The bin count threshold for using a tree rather than list for a
* bin. Bins are converted to trees when adding an element to a
* bin with at least this many nodes. The value must be greater
* than 2 and should be at least 8 to mesh with assumptions in
* tree removal about conversion back to plain bins upon
* shrinkage.
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* The bin count threshold for untreeifying a (split) bin during a
* resize operation. Should be less than TREEIFY_THRESHOLD, and at
* most 6 to mesh with shrinkage detection under removal.
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* The smallest table capacity for which bins may be treeified.
* (Otherwise the table is resized if too many nodes in a bin.)
* Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts
* between resizing and treeification thresholds.
*/
static final int MIN_TREEIFY_CAPACITY = 64;
需要注意这三个常量，都是树化相关的
- TREEIFY_THRESHOLD=8，根据注释可以知道，如果一个链表的节点数大于等于8，就可能会触发转换为树的操作（为什么是可能呢，这个跟整个table的capacity容量有关，也就是参数MIN_TREEIFY_CAPACITY）。
- UNTREEIFY_THRESHOLD 在resize的时候，链表如果重排之后数小于这个值，就会从树状结构回退到单向列表
- MIN_TREEIFY_CAPACITY 刚刚说的最小树化容量值。如果一个hashmap的容量值小于这个阈值，频繁扩容的可能性更大，这时候如果树化，会频繁因为resize导致树再转换为链表，得不偿失。所以在treeifyBin中加入了一个capacity的判断，小于MIN_TREEIFY_CAPACITY值，会直接resize。
else {
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 为什么减一呢？因为马上就要新增一个节点，占据了链表的一个元素计数。这里只需要大于等于7，加上头节点，链表就有至少8个元素。
treeifyBin(tab, hash);
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
可以看到，这里在for循环中，做了两个if判断处理
- for中第一个if：
上面已经确定了p节点不是需要被覆盖的node节点，如果p.next是null，那么这里就直接将p.next指向一个新创建节点，新增key、value就在这里轻飘飘的实现了�。这里还做了一个额外的操作，就是判断是否需要树化。
需要注意的是，自己之前的认识有个误区，认为这里e = p.next，然后下面对p.next赋值时，e也应该有值，毕竟是同一个引用。但是这里e的值在 p.next = newNode之后，依然是null。看下面的验证代码：
public class Node {
String key;
String value;
Node next;
public Node(String key, String value, Node next) {
this.key = key;
this.value = value;
this.next = next;
}
}
public class NextTest {
public static void main(String[] args) {
Node p = new Node("p1","p2",null);
Node e;
if((e = p.next) == null){
p.next = new Node("p3","p4",null);
}
System.out.println(e); // null
}
}
这里在执行第23行，p.next = new Node() 之后，e依然是指向了null，而非新的node节点。
也就是这里，e这个引用通过p.next指向的是null，p.next的引用指向修改后，e的引用并没有发生变化。
- for中的第二个if：
如果节点e = p.next 不是null，且e的key、hash均与需要put进来的数据匹配，那么e节点会被覆盖，直接跳出。
- 最后一个 p = e :
相当于p = p.next，继续做循环，在链表中一个节点一个节点的loop下去，如果一直没有需要覆盖的节点，那么就会走到 e = p.next = null的分支，创建一个新节点，并且将上一个节点的next指向这个新节点(p.next = newNode())，然后跳出。这里有点儿绕，但是仔细想了，暂时没发现有别的深意。
这里需要注意的是，之前网上有资料说新增节点会放到头结点，也就是newNode.next = oldNode，但是在jdk1.8代码中反而是 old.next=new，也就是将新数据放在队尾。
第二步，执行替换操作：
如果e不为null，表明e节点这次需要被覆盖，把新value设置进去，所以代码如下：
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
注意这里的onlyIfAbsent，这个参数默认为false。如果为true，则不修改原数据。
afterNodeAccess的实现为空，看注释是说为LinkedHashMap预留，这里忽略即可。
最后的处理
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
修改次数 modCount+1，这个修改次数需要注意，如果在foreach的时候对hashmap修改了，会报ConcurrentModificationException，是否修改就是根据操作前后的modCount对比来判断的。
如果size大于扩容阈值，这里会触发扩容动作。
扩容resize
一直在说扩容，终于到了，扩容其实就是对table进行扩展，设定新的capacity、threshold，并迁移oldTab中的数据。先看具体的注释和实现：
/**
* 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
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
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"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
注意注释：
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.
啥意思嘞？hashmap每次扩容都是之前的2倍，所以元素要么还在原来的index对应的链表中，要么在移动oldCapacity（原容量）的位置。下面举例说明
比如从16 扩容到 32，即n = 16 —> n = 32
n-1 = 15 ——> 0000 1111
new n-1 = 31 ——> 0001 1111
注意左边新增了一位，这个是关键！
位置变化：
假设一个元素的hash是 0001 0101
扩容之前，oldIndex = (n - 1) & hash = 0101 = 5,也就是index = 5
扩容之后：newIndex = (n - 1) & hash = 10101 = 21,也就是index = 21
21 - 5 = 16 = 原来的capacity
位置不变:
假设一个元素的hash是 0000 0010
扩容之前，(n - 1) & hash = 0010 = 2
扩容之后，(n - 1) & hash = 0010 = 2
扩容前后位置不变
可以看到，一个元素的位置变不变，跟它本身的hash值 在新增的那一位是0 还是 1 有直接关系。
- 如果是0，那么index计算的时候跟原来保持一致，位置不变。
- 如果是1，那么index计算的时候，newValue = oldValue + 2的N次方，刚好这个2的N次方，是原来的capacity（因为都是两倍扩容）
- 所以扩容之后，不需要频繁的移位处理，只需要把对应新增位为1的元素，直接放到newIndex(=oldIndex + oldCapacity )位置即可。这也是hashmap每次扩容变为原有容量2倍的原因之一。
理解了这部分之后，继续去看代码就会简单很多。下面开始代码的学习
代码:
准备工作：
Node<K,V>[] oldTab = table; // 原有的Node数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 原capacity容量
int oldThr = threshold; // 原resize阈值
int newCap, newThr = 0; // 定义新的capacity、threshold
计算扩容后的容量、阈值
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) { // 极限值，最大容量了，无法再继续扩容
threshold = Integer.MAX_VALUE;
return oldTab; // 直接把threshold设置为最大值，避免再触发扩容，然后返回
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) // 如果原有容量 * 2 小于最大值，且原有容量大于等于16，newCap和newThr都通过左移一位直接设置为原来的两倍
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 如果oldThr大于零，oldCap肯定也大于0，这里应该走不到。估计是极端情况下才到
newCap = oldThr;
else { // 如果刚开始oldCap和oldThr都是0，用默认数据初始化newCap和newThr，分别是16和12
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果newThr还是0，这里再初始化一次，防呆
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 把获取到的扩容阈值newThr赋值给实际的threshold，正式生效
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 扩容后的Node数组，把容量设置为newCap值
table = newTab; // 用实际的newTab 替换掉 原有的table
数据搬迁
需要将数据从oldTab迁移到newTab中，主要是做了注释中说的那段逻辑，即计算新的index值，只有两种结果，不变，或者变为oldIndex+oldCap.
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { // 循环处理oldTab中的节点数据
Node<K,V> e; // 处理中的临时节点
if ((e = oldTab[j]) != null) { // 获取元素数据，存放在临时节点e中
oldTab[j] = null; // 置空原有节点数据引用，方便后续gc
if (e.next == null) // 如果当前节点是当前链表中最后一个节点，根据e的hash及newTab的
newTab[e.hash & (newCap - 1)] = e;// length计算出新的index，并将e赋值到这个节点中
else if (e instanceof TreeNode) // 如果是红黑树，转到split方法中处理
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 以上两种情况都不是，说明是小于等于8个节点的链表数据处理.
// 下面就是需要处理具体的数据搬迁了，主要关注index值的计算
else { // preserve order
Node<K,V> loHead = null, loTail = null; // index不变的数据链表，low
Node<K,V> hiHead = null, hiTail = null; // newIndex=oldIndex+oldCap的数据，high
Node<K,V> next;
// 循环处理，这里处理的是index=j的一个链表中的所有数据，这里是尾部插入
do {
next = e.next; // e = oldTab[j] 通过next做循环，第一次e是头结点
// 假设 oldCap = 16，也就是 0001 0000
// e.hash = 0001 1010 0000
// 那么 e.hash & olcCap = 0000 0000 0000，也就是等于0
// 注意这里做&操作的，不是oldCap-1，而是oldCap，都是2的N次方，也就是只有一位是1
// 这里是等于0的，也就是index不变的，newIndex = oldIndex
if ((e.hash & oldCap) == 0) {
if (loTail == null) // 由于采用尾插方式，所以刚开始loTail=null
loHead = e; // 设定loHead=第一个元素，作为newTab[j]的头结点
else
loTail.next = e; // 如果loTail != null，不是链表第一个节点，尾插
loTail = e; // 设定loTail为e，循环下一个。
// 注意这时候，loHead 和 loTail都指向同一个节点，也就是头节点，所以loHead.next = 下一个处理节点，真神奇的写法，赞！
}
// oldCap = 16 = 0001 0000
// e.hash = 0001 1001 0010
// e.hash & oldCap = 0000 0001 0000 != 0
// 所以这里是index变化的，newIndex = oldIndex + oldCap
else {
if (hiTail == null) // 第一个迁移过来的元素处理时，hiTail=null
hiHead = e; // 设置 hiHead = 第一个元素，作为newTab[j+oldCap]的头节点
else
hiTail.next = e; // 如果hiTail != null，不是链表第一个节点，尾插
hiTail = e;
// 同理，这时候hiHead 和 hiTail都指向同一个节点，也就是头节点，所以hiHead.next = 下一个迁移过来的节点，再次赞一个！
}
} while ((e = next) != null); // 更新e的值为next，也就是指向下一个节点，也就是做遍历条件更新
// 将loHead作为newTab的第j个节点，loHead.next = 后面的元素链表
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 将hiHead作为newTab的第j+oldCap个节点，hiHead.next = 后面的元素链表
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab; // 循环结束后，处理完成，返回newTab
其实具体实现的点都在代码里面说明了，这里再着重总结以下：
- newIndex = oldIndex 或者 oldIndex + oldCap
- 迁移过来的元素采用尾插方式，也就是从链表尾部插入。
- loHead 和 loTail 处理的是index不变的数据，也就是newIndex = oldIndex的数据。loHead指头结点，只用两次，一次是刚开始处理时的赋值，一次是放到newTab时的引用。
- hiHead 和 hiTail处理的是index变化的数据，也就是newIndex = oldIndex + oldCap的数据。同理，hiHead也是头结点。
compute & merge & foreach
新增的部分实现，先不啃了，暂时没那么常用，大概扫一扫。
红黑树的相关的地方，参考下一篇文章。
网友评论