HashMap
光从名字上应该也能猜到，HashMap肯定是基于hash算法实现的，这种基于hash实现的map叫做散列表（hash table）。
散列表中维护了一个数组，数组的每一个元素被称为一个桶（bucket），当你传入一个key = "a"进行查询时，散列表会先把key传入散列（hash）函数中进行寻址，得到的结果就是数组的下标，然后再通过这个下标访问数组即可得到相关联的值。
我们都知道数组中数据的组织方式是线性的，它会直接分配一串连续的内存地址序列，要找到一个元素只需要根据下标来计算地址的偏移量即可（查找一个元素的起始地址为：数组的起始地址加上下标乘以该元素类型占用的地址大小）。因此散列表在理想的情况下，各种操作的时间复杂度只有O(1)，这甚至超过了二叉查找树，虽然理想的情况并不总是满足的，关于这点之后我们还会提及。
为什么是hash？
hash算法是一种可以从任何数据中提取出其“指纹”的数据摘要算法，它将任意大小的数据（输入）映射到一个固定大小的序列（输出）上，这个序列被称为hash code、数据摘要或者指纹。比较出名的hash算法有MD5、SHA。
hash是具有唯一性且不可逆的，唯一性指的是相同的输入产生的hash code永远是一样的，而不可逆也比较容易理解，数据摘要算法并不是压缩算法，它只是生成了一个该数据的摘要，没有将数据进行压缩。压缩算法一般都是使用一种更节省空间的编码规则将数据重新编码，解压缩只需要按着编码规则解码就是了，试想一下，一个几百MB甚至几GB的数据生成的hash code都只是一个拥有固定长度的序列，如果再能逆向解压缩，那么其他压缩算法该情何以堪？
我们上述讨论的仅仅是在密码学中的hash算法，而在散列表中所需要的散列函数是要能够将key寻址到buckets中的一个位置，散列函数的实现影响到整个散列表的性能。
一个完美的散列函数要能够做到均匀地将key分布到buckets中，每一个key分配到一个bucket，但这是不可能的。虽然hash算法具有唯一性，但同时它还具有重复性，唯一性保证了相同输入的输出是一致的，却没有保证不同输入的输出是不一致的，也就是说，完全有可能两个不同的key被分配到了同一个bucket（因为它们的hash code可能是相同的），这叫做碰撞冲突。总之，理想很丰满，现实很骨感，散列函数只能尽可能地减少冲突，没有办法完全消除冲突。
散列函数的实现方法非常多，一个优秀的散列函数要看它能不能将key分布均匀。首先介绍一种最简单的方法：除留余数法，先对key进行hash得到它的hash code，然后再用该hash code对buckets数组的元素数量取余，得到的结果就是bucket的下标，这种方法简单高效，也可以当做对集群进行负载均衡的路由算法。
privateinthash(Key key) {
// & 0x7fffffff 是为了屏蔽符号位，M为bucket数组的长度
return(key.hashCode() & 0x7fffffff) % M;
}
要注意一点，只有整数才能进行取余运算，如果hash code是一个字符串或别的类型，那么你需要将它转换为整数才能使用除留余数法，不过Java在Object对象中提供了hashCode()函数，该函数返回了一个int值，所以任何你想要放入HashMap的自定义的抽象数据类型，都必须实现该函数和equals()函数，这两个函数之间也遵守着一种约定：如果a.equals(b) == true，那么a与b的hashCode()也必须是相同的。
下面为String类的hashCode()函数，它先遍历了内部的字符数组，然后在每一次循环中计算hash code（将hash code乘以一个素数并加上当前循环项的字符）：
/** The value is used for character storage. */
privatefinalcharvalue[];
/** Cache the hash code for the string */
privateinthash; // Default to 0
publicinthashCode() {
inth = hash;
if(h == 0&& value.length > 0) {
charval[] = value;
for(inti = 0; i < value.length; i++) {
h = 31* h + val[i];
}
hash = h;
}
returnh;
}
HashMap没有采用这么简单的方法，有一个原因是HashMap中的buckets数组的长度永远为一个2的幂，而不是一个素数，如果长度为素数，那么可能会更适合简单暴力的除留余数法（当然除留余数法虽然简单却并不是那么高效的），顺便一提，时代的眼泪Hashtable就使用了除留余数法，它没有强制约束buckets数组的长度。
HashMap在内部实现了一个hash()函数，首先要对hashCode()的返回值进行处理：
staticfinalinthash(Object key) {
inth;
return(key == null) ? 0: (h = key.hashCode()) ^ (h >>> 16);
}
该函数将key.hashCode()的低16位和高16位做了个异或运算，其目的是为了扰乱低位的信息以实现减少碰撞冲突。之后还需要把hash()的返回值与table.length - 1做与运算（table为buckets数组），得到的结果即是数组的下标。
table.length - 1就像是一个低位掩码（这个设计也优化了扩容操作的性能），它和hash()做与操作时必然会将高位屏蔽（因为一个HashMap不可能有特别大的buckets数组，至少在不断自动扩容之前是不可能的，所以table.length - 1的大部分高位都为0），只保留低位，看似没什么毛病，但这其实暗藏玄机，它会导致总是只有最低的几位是有效的，这样就算你的hashCode()实现得再好也难以避免发生碰撞。这时，hash()函数的价值就体现出来了，它对hash code的低位添加了随机性并且混合了高位的部分特征，显著减少了碰撞冲突的发生。
HashMap的散列函数具体流程如下图：
解决冲突
在上文中我们已经多次提到碰撞冲突，但是散列函数不可能是完美的，key分布完全均匀的情况是不存在的，所以碰撞冲突总是难以避免。
那么发生碰撞冲突时怎么办？总不能丢弃数据吧？必须要有一种合理的方法来解决这个问题，HashMap使用了叫做分离链接（Separate chaining，也有人翻译成拉链法）的策略来解决冲突。它的主要思想是每个bucket都应当是一个互相独立的数据结构，当发生冲突时，只需要把数据放入bucket中（因为bucket本身也是一个可以存放数据的数据结构），这样查询一个key所消耗的时间为访问bucket所消耗的时间加上在bucket中查找的时间。
HashMap的buckets数组其实就是一个链表数组，在发生冲突时只需要把Entry（还记得Entry吗？HashMap的Entry实现就是一个简单的链表节点，它包含了key和value以及hash code）放到链表的尾部，如果未发生冲突（位于该下标的bucket为null），那么就把该Entry做为链表的头部。而且HashMap还使用了Lazy策略，buckets数组只会在第一次调用put()函数时进行初始化，这是一种防止内存浪费的做法，像ArrayList也是Lazy的，它在第一次调用add()时才会初始化内部的数组。
不过链表虽然实现简单，但是在查找的效率上只有O(n)，而且我们大部分的操作都是在进行查找，在hashCode()设计的不是非常良好的情况下，碰撞冲突可能会频繁发生，链表也会变得越来越长，这个效率是非常差的。Java 8对其实现了优化，链表的节点数量在到达阈值时会转化为红黑树，这样查找所需的时间就只有O(log n)了，阈值的定义如下：
/**
* 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.
*/
staticfinalintTREEIFY_THRESHOLD = 8;
如果在插入Entry时发现一条链表超过阈值，就会执行以下的操作，对该链表进行树化；相对的，如果在删除Entry（或进行扩容）时发现红黑树的节点太少（根据阈值UNTREEIFY_THRESHOLD），也会把红黑树退化成链表。
/**
* 替换指定hash所处位置的链表中的所有节点为TreeNode，
* 如果buckets数组太小，就进行扩容。
*/
finalvoidtreeifyBin(Node<K,V>[] tab, inthash) {
intn, index; Node<K,V> e;
// MIN_TREEIFY_CAPACITY = 64，小于该值代表数组中的节点并不是很多
// 所以选择进行扩容，只有数组长度大于该值时才会进行树化。
if(tab == null|| (n = tab.length) < MIN_TREEIFY_CAPACITY)
resize();
elseif((e = tab[index = (n - 1) & hash]) != null) {
TreeNode<K,V> hd = null, tl = null;
// 转换链表节点为树节点，注意要处理好连接关系
do{
TreeNode<K,V> p = replacementTreeNode(e, null);
if(tl == null)
hd = p;
else{
p.prev = tl;
tl.next = p;
}
tl = p;
} while((e = e.next) != null);
if((tab[index] = hd) != null)
hd.treeify(tab); // 从头部开始构造树
}
}
// 该函数定义在TreeNode中
finalvoidtreeify(Node<K,V>[] tab) {
TreeNode<K,V> root = null;
for(TreeNode<K,V> x = this, next; x != null; x = next) {
next = (TreeNode<K,V>)x.next;
x.left = x.right = null;
if(root == null) { // 初始化root节点
x.parent = null;
x.red = false;
root = x;
}
else{
K k = x.key;
inth = x.hash;
Class<?> kc = null;
for(TreeNode<K,V> p = root;;) {
intdir, ph;
K pk = p.key;
// 确定节点的方向
if((ph = p.hash) > h)
dir = -1;
elseif(ph < h)
dir = 1;
// 如果kc == null
// 并且k没有实现Comparable接口
// 或者k与pk是没有可比较性的（类型不同）
// 或者k与pk是相等的（返回0也有可能是相等）
elseif((kc == null&&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 确定方向后插入节点，修正红黑树的平衡
TreeNode<K,V> xp = p;
if((p = (dir <= 0) ? p.left : p.right) == null) {
x.parent = xp;
if(dir <= 0)
xp.left = x;
else
xp.right = x;
root = balanceInsertion(root, x);
break;
}
}
}
}
// 确保给定的root是该bucket中的第一个节点
moveRootToFront(tab, root);
}
staticinttieBreakOrder(Object a, Object b) {
intd;
if(a == null|| b == null||
(d = a.getClass().getName().
compareTo(b.getClass().getName())) == 0)
// System.identityHashCode()将调用并返回传入对象的默认hashCode()
// 也就是说，无论是否重写了hashCode()，都将调用Object.hashCode()。
// 如果传入的对象是null，那么就返回0
d = (System.identityHashCode(a) <= System.identityHashCode(b) ?
-1: 1);
returnd;
}
解决碰撞冲突的另一种策略叫做开放寻址法（Open addressing），它与分离链接法的思想截然不同。在开放寻址法中，所有Entry都会存储在buckets数组，一个明显的区别是，分离链接法中的每个bucket都是一个链表或其他的数据结构，而开放寻址法中的每个bucket就仅仅只是Entry本身。
开放寻址法是基于数组中的空位来解决冲突的，它的想法很简单，与其使用链表等数据结构，不如直接在数组中留出空位来当做一个标记，反正都要占用额外的内存。
当你查找一个key的时候，首先会从起始位置（通过散列函数计算出的数组索引）开始，不断检查当前bucket是否为目标Entry（通过比较key来判断），如果当前bucket不是目标Entry，那么就向后查找（查找的间隔取决于实现），直到碰见一个空位（null），这代表你想要找的key不存在。
如果你想要put一个全新的Entry（Map中没有这个key存在），依然会从起始位置开始进行查找，如果起始位置不是空的，则代表发生了碰撞冲突，只好不断向后查找，直到发现一个空位。
开放寻址法的名字也是来源于此，一个Entry的位置并不是完全由hash值决定的，所以也叫做Closed hashing，相对的，分离链接法也被称为Open hashing或Closed addressing。
根据向后探测（查找）的算法不同，开放寻址法有多种不同的实现，我们介绍一种最简单的算法：线性探测法（Linear probing），在发生碰撞时，简单地将索引加一，如果到达了数组的尾部就折回到数组的头部，直到找到目标或一个空位。
基于线性探测法的查找操作如下：
1
2
3
4
5
6
7
8
9
10
11
privateK[] keys; // 存储key的数组
privateV[] vals; // 存储值的数组
publicV get(K key) {
// m是buckets数组的长度，即keys和vals的长度。
// 当i等于m时，取模运算会得0（折回数组头部）
for(inti = hash(key); keys[i] != null; i = (i + 1) % m) {
if(keys[i].equals(key))
returnvals[i];
}
returnnull;
}
插入操作稍微麻烦一些，需要在插入之前判断当前数组的剩余容量，然后决定是否扩容。数组的剩余容量越多，代表Entry之间的间隔越大以及越早碰见空位（向后探测的次数就越少），效率自然就会变高。代价就是额外消耗的内存较多，这也是在用空间换取时间。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
publicvoidput(K key, V value) {
// n是Entry的数量，如果n超过了数组长度的一半，就扩容一倍
if(n >= m / 2) resize(2* m);
inti;
for(i = hash(key); keys[i] != null; i = (i + 1) % m) {
if(keys[i].equals(key)) {
vals[i] = value;
return;
}
}
// 没有找到目标，那么就插入一对新的Entry
keys[i] = key;
vals[i] = value;
n++;
}
接下来是删除操作，需要注意一点，我们不能简单地把目标key所在的位置（keys和vals数组）设置为null，这样会导致此位置之后的Entry无法被探测到，所以需要将目标右侧的所有Entry重新插入到散列表中：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
publicV delete(K key) {
inti = hash(key);
// 先找到目标的索引
while(!key.equals(keys[i])) {
i = (i + 1) % m;
}
V oldValue = vals[i];
// 删除目标key和value
keys[i] = null;
vals[i] = null;
// 指针移动到下一个索引
i = (i + 1) % m;
while(keys[i] != null) {
// 先删除然后重新插入
K keyToRehash = keys[i];
V valToRehash = vals[i];
keys[i] = null;
vals[i] = null;
n--;
put(keyToRehash, valToRehash);
i = (i + 1) % m;
}
n--;
// 当前Entry小于等于数组长度的八分之一时，进行缩容
if(n > 0&& n <= m / 8) resize(m / 2);
returnoldValue;
}
动态扩容
散列表以数组的形式组织bucket，问题在于数组是静态分配的，为了保证查找的性能，需要在Entry数量大于一个临界值时进行扩容，否则就算散列函数的效果再好，也难免产生碰撞。
所谓扩容，其实就是用一个容量更大（在原容量上乘以二）的数组来替换掉当前的数组，这个过程需要把旧数组中的数据重新hash到新数组，所以扩容也能在一定程度上减缓碰撞。
HashMap通过负载因子（Load Factor）乘以buckets数组的长度来计算出临界值，算法：threshold = load_factor * capacity。比如，HashMap的默认初始容量为16（capacity = 16），默认负载因子为0.75（load_factor = 0.75），那么临界值就为threshold = 0.75 * 16 = 12，只要Entry的数量大于12，就会触发扩容操作。
还可以通过下列的构造函数来自定义负载因子，负载因子越小查找的性能就会越高，但同时额外占用的内存就会越多，如果没有特殊需要不建议修改默认值。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
* 可以发现构造函数中根本就没初始化buckets数组。
* （之前说过buckets数组会推迟到第一次调用put()时进行初始化）
*/
publicHashMap(intinitialCapacity, floatloadFactor) {
if(initialCapacity < 0)
thrownewIllegalArgumentException("Illegal initial capacity: "+
initialCapacity);
if(initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if(loadFactor <= 0|| Float.isNaN(loadFactor))
thrownewIllegalArgumentException("Illegal load factor: "+
loadFactor);
this.loadFactor = loadFactor;
// tableSizeFor()确保initialCapacity必须为一个2的N次方
this.threshold = tableSizeFor(initialCapacity);
}
buckets数组的大小约束对于整个HashMap都至关重要，为了防止传入一个不是2次幂的整数，必须要有所防范。tableSizeFor()函数会尝试修正一个整数，并转换为离该整数最近的2次幂。
1
2
3
4
5
6
7
8
9
10
11
12
/**
* Returns a power of two size for the given target capacity.
*/
staticfinalinttableSizeFor(intcap) {
intn = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return(n < 0) ? 1: (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
还记得数组索引的计算方法吗？index = (table.length - 1) & hash，这其实是一种优化手段，由于数组的大小永远是一个2次幂，在扩容之后，一个元素的新索引要么是在原位置，要么就是在原位置加上扩容前的容量。这个方法的巧妙之处全在于&运算，之前提到过&运算只会关注n – 1（n = 数组长度）的有效位，当扩容之后，n的有效位相比之前会多增加一位（n会变成之前的二倍，所以确保数组长度永远是2次幂很重要），然后只需要判断hash在新增的有效位的位置是0还是1就可以算出新的索引位置，如果是0，那么索引没有发生变化，如果是1，索引就为原索引加上扩容前的容量。
这样在每次扩容时都不用重新计算hash，省去了不少时间，而且新增有效位是0还是1是带有随机性的，之前两个碰撞的Entry又有可能在扩容时再次均匀地散布开。下面是resize()的源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
finalNode<K,V>[] resize() {
Node<K,V>[] oldTab = table; // table就是buckets数组
intoldCap = (oldTab == null) ? 0: oldTab.length;
intoldThr = threshold;
intnewCap, newThr = 0;
// oldCap大于0，进行扩容，设置阈值与新的容量
if(oldCap > 0) {
// 超过最大值不会进行扩容，并且把阈值设置成Interger.MAX_VALUE
if(oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
returnoldTab;
}
// 没超过最大值，扩容为原来的2倍
// 向左移1位等价于乘2
elseif((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// oldCap = 0，oldThr大于0，那么就把阈值做为新容量以进行初始化
// 这种情况发生在用户调用了带有参数的构造函数（会对threshold进行初始化）
elseif(oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// oldCap与oldThr都为0，这种情况发生在用户调用了无参构造函数
// 采用默认值进行初始化
else{ // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 如果newThr还没有被赋值，那么就根据newCap计算出阈值
if(newThr == 0) {
floatft = (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>[])newNode[newCap];
table = newTab;
// 如果oldTab != null，代表这是扩容操作
// 需要将扩容前的数组数据迁移到新数组
if(oldTab != null) {
// 遍历oldTab的每一个bucket，然后移动到newTab
for(intj = 0; j < oldCap; ++j) {
Node<K,V> e;
if((e = oldTab[j]) != null) {
oldTab[j] = null;
// 索引j的bucket只有一个Entry（未发生过碰撞）
// 直接移动到newTab
if(e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果是一个树节点（代表已经转换成红黑树了）
// 那么就将这个节点拆分为lower和upper两棵树
// 首先会对这个节点进行遍历
// 只要当前节点的hash & oldCap == 0就链接到lower树
// 注意这里是与oldCap进行与运算，而不是oldCap - 1(n - 1)
// oldCap就是扩容后新增有效位的掩码
// 比如oldCap=16，二进制10000，n-1 = 1111，扩容后的n-1 = 11111
// 只要hash & oldCap == 0，就代表hash的新增有效位为0
// 否则就链接到upper树（新增有效位为1）
// lower会被放入newTab[原索引j]，upper树会被放到newTab[原索引j + oldCap]
// 如果lower或者upper树的节点少于阈值，会被退化成链表
elseif(e instanceofTreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else{ // preserve order
// 下面操作的逻辑与分裂树节点基本一致
// 只不过split()操作的是TreeNode
// 而且会将两条TreeNode链表组织成红黑树
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;
}
}
}
}
}
returnnewTab;
}
使用HashMap时还需要注意一点，它不会动态地进行缩容，也就是说，你不应该保留一个已经删除过大量Entry的HashMap（如果不打算继续添加元素的话），此时它的buckets数组经过多次扩容已经变得非常大了，这会占用非常多的无用内存，这样做的好处是不用多次对数组进行扩容或缩容操作。不过一般也不会出现这种情况，如果遇见了，请毫不犹豫地丢掉它，或者把数据转移到一个新的HashMap。
添加元素
我们已经了解了HashMap的内部实现与工作原理，它在内部维护了一个数组，每一个key都会经过散列函数得出在数组的索引，如果两个key的索引相同，那么就使用分离链接法解决碰撞冲突，当Entry的数量大于临界值时，对数组进行扩容。
接下来以一个添加元素（put()）的过程为例来梳理一下知识，下图是put()函数的流程图：
然后是源码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
publicV put(K key, V value) {
returnputVal(hash(key), key, value, false, true);
}
finalV putVal(inthash, K key, V value, booleanonlyIfAbsent,
booleanevict) {
Node<K,V>[] tab; Node<K,V> p; intn, i;
// table == null or table.length == 0
// 第一次调用put()，初始化table
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;
// 节点为红黑树
elseif(p instanceofTreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
// 节点为链表
else{
for(intbinCount = 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;
}
}
// 节点已存在，替换value
if(e != null) { // existing mapping for key
V oldValue = e.value;
if(!onlyIfAbsent || oldValue == null)
e.value = value;
// afterNodeXXXXX是提供给LinkedHashMap重写的函数
// 在HashMap中没有意义
afterNodeAccess(e);
returnoldValue;
}
}
++modCount;
// 超过临界值，进行扩容
if(++size > threshold)
resize();
afterNodeInsertion(evict);
returnnull;
}
喜欢的点点关注点点赞
网友评论