【Java拾遗】JDK源码之集合篇【Java拾遗】JDK源码之集合篇

说明
这里文章大多为复习内容，内容精简干练，为原有基础知识回顾
ArrayList，LinkedList
使用到的工具类 System.arraycopy(srcElements, srcIndex, targetElement, tarIndex, srcLength);
Arrays.copyOf(数组,型数组长度);
位运算复习 x>>1 等价于： x / 2 (2的1次方)
x<<1 等价于： x * 2 (2的1次方)
^ 异或 1 ^ 0 = 1, 1 ^ 1 = 0, 0 ^ 0 = 0
& 与 1 & 1 = 1 其余都为0 所以&结果都趋向0
| 或 0 | 0 为0 其余都为1 所以|结果都趋向1
HashMap
logn、 lgn 数学知识学习一般的，如果a^x = N
那么数x叫做以a为底N的对数，x = logaN，其中a叫做底数
lgn是以10位底n的对数
时间复杂度：Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜Ο(n2)＜Ο(n3)＜O(n!)
JDK8中hash算法 hash算法：return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
h是key的hashcode, 结果为a
h右移16位也就是key的高16位移动到低16位，结果为b
a ^ b 相当于：key的hashcode高16位和低16位异或运算，能够使hashcode低16位更加散乱, 真正计算槽位的算法只有低16位会参与运算
hashMap key值寻找数组位置的方法：(n - 1) & hash n是数组长度
hashMap默认长度为16，这个算法为 15 & hash
几个问题：为什么用右移16位真正计算数组位置的用的是低16位，所以右移可以将高16位起到作用，使得hash更加散乱
为什么用^计算高16位和低16位 &结果趋向0 |结果趋向1 只有^后的结果会更加散乱
& 计算只有两个都为1 才是1，所以结果趋向0
| 计算还有两个都为0才是0，所以结果趋向1
为什么槽位必须是2^n

例如长度是17， 17 - 1 = 16，二进制是 00010000 最后计算&操作时，结果不是1就是16，而16 - 1 = 15, 二进制是00001111, 低4位1111计算会有更多结果
方便位运算：key % (2^n) 等价于 key & (2^n - 1)

put的详细解读

1final V putVal(int hash, K key, V value, boolean onlyIfAbsent, 2boolean evict) { 3Node[] tab; Node p; int n, i; 4// 如果table没有初始化，那么则先使用resize，newCap = DEFAULT_INITIAL_CAPACITY; 这里初始化数组大小的意思默认为1<<4=16 5if ((tab = table) == null || (n = tab.length) == 0) 6n = (tab = resize()).length; 7// tab[i=(n-1)&hash] 意思是计算数组的槽位，n-1&hash 等价于 hash%n 8// p就是这个通过hash计算的槽位的Node信息 9if ((p = tab[i = (n - 1) & hash]) == null) 10tab[i] = newNode(hash, key, value, null); 11else { 12Node e; K k; 13// p.hash == hash说明通过hash计算的槽位已经有值了 14// (k = p.key) == key说明传入的key值和当前槽位的值地址相同 15// key.equals(k) 说明传入的key值和当前槽位的值相同 16// 如果hash值和key都相等那么则将传入的value替换成当前槽位的值 17if (p.hash == hash && 18((k = p.key) == key || (key != null && key.equals(k)))) 19e = p; 20else if (p instanceof TreeNode) 21// 如果是树结构 22e = ((TreeNode)p).putTreeVal(this, tab, hash, key, value); 23else { 24// 此时说明hash冲突，且链表还没有转化成树 25for (int binCount = 0; ; ++binCount) { 26// 判断当前槽位的next是否为空 27if ((e = p.next) == null) { 28// 如果为空，则新建一个Node，p.Next = newNode 29p.next = newNode(hash, key, value, null); 30// 如果当前链表的长度，大于等于TREEIFY_THRESHOLD - 1 = 7 转化为红黑树 31// bincount 从0开始的, 所以当bincount为7时，链表长度为8（算上数组槽位开始的那个节点，总长度为9） 32if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st 33treeifyBin(tab, hash); 34break; 35} 36// 和上面判断一致，判断hash和e=p.next的key值是否一致 37// 如果一致则直接退出，此时e=p.next 下面判断e!= null，则e.value=https://www.it610.com/article/value替换 38if (e.hash == hash && 39((k = e.key) == key || (key != null && key.equals(k)))) 40break; 41// p = e = p.next 然后继续for循环 42p = e; 43} 44} 45if (e != null) { // existing mapping for key 46V oldValue = https://www.it610.com/article/e.value; 47if (!onlyIfAbsent || oldValue =https://www.it610.com/article/= null) 48// 将value值覆盖当前槽位的值 49e.value = https://www.it610.com/article/value; 50afterNodeAccess(e); 51return oldValue; 52} 53} 54++modCount; 55// 判断是否需要扩容，size 是hashMap中key-value键值对的数量 56// threshold = 数组长度(模拟了16) * 负载因子(默认0.75) = 12 57if (++size > threshold) 58resize(); 59afterNodeInsertion(evict); 60return null; 61}

hashmap扩容原理扩容之桶计算规则 【【Java拾遗】JDK源码之集合篇】n = 16：
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash1 1111 1111 1111 1111 0000 1111 0000 0101
&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5（index = 5的位置）
扩容后n = 32：
n-1 0000 0000 0000 0000 0000 0000 0001 1111
hash2 1111 1111 1111 1111 0000 1111 0001 0101
&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21（index = 21的位置）
JDK 1.8，扩容一定是2的倍数，从16到32到64到128
就可以保证说，每次扩容之后，你的每个hash值要么是停留在原来的那个index的地方，要么是变成了原来的index（5） + oldCap（16） = 21
因此，我们在扩充HashMap的时候，不需要像JDK1.7的实现那样重新计算hash，只需要看看原来的hash值新增的那个bit是1还是0就好了，是0的话索引没变，是1的话索引变成“原索引+oldCap”。
扩容之桶计算规则图解

文章图片
01_JDK1.8 HashMap resize原理.jpg
扩容核心算法：

1final Node[] resize() { 2// 核心源码，省略了其他代码 3// 遍历就数组元素 4for (int j = 0; j < oldCap; ++j) { 5Node e; 6// e等于当前j位置头结点元素 7if ((e = oldTab[j]) != null) { 8// 已经赋值给e了，这里可以直接设置为null，方便gc 9oldTab[j] = null; 10// 如果该处next元素为null，说明没有链表结构，直接做类似rehash操作 11if (e.next == null) 12newTab[e.hash & (newCap - 1)] = e; 13else if (e instanceof TreeNode) 14// 红黑树特殊处理 15((TreeNode)e).split(this, newTab, j, oldCap); 16else { // preserve order 17// 扩容后的节点不在j位置就在j+oldCap(原始数组大小)位置 18// loHead为j处位置节点低位node，loTail为j处节点最末端node 19// hiHead为j+oldCap处位置节点低位node，hiTail为j+oldCap处节点最末端node 20Node loHead = null, loTail = null; 21Node hiHead = null, hiTail = null; 22Node next; 23do { 24next = e.next; 25// 如果为0，说明扩容后的元素还在j这个节点位置 26// 如果不为0，说明扩容后的元素会在j + oldCap节点位置 27if ((e.hash & oldCap) == 0) { 28// 如果j处尾节点为null，说明第一次设置。则设置e为头结点 29if (loTail == null) 30loHead = e; 31else 32// 设置头结点的next为e 33loTail.next = e; 34// e设置为尾结点，这就是尾插法 35loTail = e; 36} 37else { 38// 这个else分支就说明扩容后这些节点会散落到j+oldCap数组的桶上 39// 同上，如果j+oldCap的尾节点为空说明第一次设置，设置头结点为e 40if (hiTail == null) 41hiHead = e; 42else 43hiTail.next = e; 44hiTail = e; 45} 46// 这里while循环是将j对应的桶上面所有的链表或者红黑树的Node全都rehash完 47} while ((e = next) != null); 48// 这里已经设置好一个完整的链表结构了，这里是设置j和j+oldCap桶位置数据 49if (loTail != null) { 50loTail.next = null; 51newTab[j] = loHead; 52} 53if (hiTail != null) { 54hiTail.next = null; 55newTab[j + oldCap] = hiHead; 56} 57} 58} 59} 60return newTab; 61}

hashmap jdk1.8相对于1.7 优化了什么

数据结构改变
数组+链表改为：数组+链表+红黑树
hash算法改变
1.8中hash算法改为： (h = key.hashCode) ^ (h>>>16) 高低16位混合运算
扩容方式改变
头插法变成尾插法，并发情况下不会形成死锁

参考文章：

品HashMap（java8）： https://juejin.im/post/5dec684e6fb9a016227786c0
HashMap中的hash算法中的几个疑问：https://www.cnblogs.com/zxporz/p/11204233.html
Java源码分析：HashMap 1.8 相对于1.7 到底更新了什么？：https://www.jianshu.com/p/8324a34577a0

LinkedHashMap
数据结构 LinkedHashMap 继承自 HashMap，在 HashMap 基础上，通过维护一条双向链表，解决了 HashMap 不能随时保持遍历顺序和插入顺序一致的问题。除此之外，LinkedHashMap 对访问顺序也提供了相关支持。在一些场景下，该特性很有用，比如缓存。
数据结构如图：（原图地址:http://www.tianxiaobo.com/2018/01/24/LinkedHashMap-源码详细分析（JDK1-8）/）

文章图片
image.png
插入数据

1// HashMap 中实现 2Node newNode(int hash, K key, V value, Node next) { 3return new Node<>(hash, key, value, next); 4} 5 6// LinkedHashMap 中覆写 7Node newNode(int hash, K key, V value, Node e) { 8LinkedHashMap.Entry p = 9new LinkedHashMap.Entry(hash, key, value, e); 10// 将 Entry 接在双向链表的尾部 11linkNodeLast(p); 12return p; 13} 14 15// LinkedHashMap 中实现 16private void linkNodeLast(LinkedHashMap.Entry p) { 17LinkedHashMap.Entry last = tail; 18tail = p; 19// last 为 null，表明链表还未建立 20if (last == null) 21head = p; 22else { 23// 将新节点 p 接在链表尾部 24p.before = last; 25last.after = p; 26} 27}

LinkedHashMap维护访问顺序

1// 如果accessOrder为true 2// 调用get/getOrDefault/replace方法会将这些方法访问的节点移动到链表的尾部 3void afterNodeAccess(Node p) { } 4// putValue的时候对调用 5void afterNodeInsertion(boolean evict) { } 6// remove时候调用 7void afterNodeRemoval(Node p) { }

通过回调的方式，让 LinkedHashMap 有机会做一些后置操作。上述三个方法的具体实现在 LinkedHashMap中。

1// LinkedHashMap 中覆写 2public V get(Object key) { 3Node e; 4if ((e = getNode(hash(key), key)) == null) 5return null; 6// 如果 accessOrder 为 true，则调用 afterNodeAccess 将被访问节点移动到链表最后 7if (accessOrder) 8afterNodeAccess(e); 9return e.value; 10} 11 12// LinkedHashMap 中覆写 13void afterNodeAccess(Node e) { // move node to last 14LinkedHashMap.Entry last; 15if (accessOrder && (last = tail) != e) { 16LinkedHashMap.Entry p = 17(LinkedHashMap.Entry)e, b = p.before, a = p.after; 18p.after = null; 19// 如果 b 为 null，表明 p 为头节点 20if (b == null) 21// 将p的后置节点设置为head节点 22head = a; 23else 24// 如果b不为空，说明p前置存在节点 25// 那么将p的后置节点设置为b的后置节点 26b.after = a; 27 28// 判断p的后置节点，如果不为空 29if (a != null) 30设置a的前置节点为b 31a.before = b; 32 33// 如果p的后置节点为空, 这说明p为尾节点 34// 这种情况会将p的前置节点设置为尾节点 35else 36last = b; 37 38// 如果last为空，这说明链表没有元素，所以head = p 39if (last == null) 40head = p; 41else { 42// 将 p 接在链表的最后 43p.before = last; 44last.after = p; 45} 46tail = p; 47++modCount; 48} 49}

LinkedHashMap实现LRU算法上面已经知道，如果accessOrder是true，那么get等操作都会将tail指正指向该元素
HashMap putValue的时候对调用：afterNodeInsertion(evict) -> removeEldestEntry()
我们需要复写removeEldestEntry() 方法指定移除策略，然后会移除first元素
代码实现可参考我的demo：https://github.com/barrywangmeng/java-learning/tree/master/java-learning/src/main/java/cn/barrywangmeng/cache/lru