-
面试查漏补缺--java基础-容器源码解读
前言：
本文主要是通过源码来解读一些自己还不懂的地方，一些数据结构上的东西，不做过多的解读。
文章目录
- 一、容器体系
- 二、List容器
- 三、Set容器
- 四、Map容器
- 4.1 Map容器简介
- 4.2 HashMap（HashSet中讲过，这里介绍忽略，自己跟一下源码会更清楚，这一小节主要跟一下树化的源码）
- 4.3 HashMap最变态的面试题
- 1、HashMap的数据结构
- 2、1.8 为什么要改成“数组+链表+红黑树”？
- 3、那在什么时候用链表？什么时候用红黑树？
- 4、为什么链表转红黑树的阈值是8？
- 5、那为什么转回链表节点是用的6而不是复用8？
- 6、HashMap 有哪些重要属性？分别用于做什么的（看源码）？
- 7、HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
- 8、2次幂是怎么算的
- 9、ashMap 的容量必须是 2 的 N 次方，这是为什么？
- 10、你说 HashMap 的默认初始容量是 16，为什么是16而不是其他的？
- 11、负载因子为什么是0.75，达到数组的扩容条件
- 12、HashMap 的插入流程是怎么样的？
- 13、计算 key 的 hash 值，是怎么设计的？
- 14、为什么要将 hashCode 的高16位参与运算？（其实我在在手写hash表的时候是直接用hashcode%数组的长度的，这里通过hashcode的高16位和低16位进行了异或运算）
- 15、扩容（resize）流程介绍下？
- 16、HashMap 是线程安全的吗
- 17、介绍一下死循环问题？
- 18、那总结下 JDK 1.8 主要进行了哪些优化？
一、容器体系
容器总的来说分为两大类：
1、Collection:
存放的是单建元素（就是单个元素）2、Map
存放的键值对（以Key-Value的方式存在）- 1、Collection下的两大接口，List 和 Set
- Map下的三大容器（都是以建值对的方式向Map中存放值）
二、List容器
List定义的模板方法如下：
2.1 ArrayList源码
底层的数据结构是数组，所以使用idx
学习重点在于扩容（add方法中很重要）：
// 测试代码 public class ListTest { public static void main(String[] args) { List<Object> list = new ArrayList<>(); for (int i = 0; i < 10; i++) { list.add(i); } list.add(20000); } }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
1、使用默认的构造函数
2、调用add方法
- （1）先确认是否需要扩容
-（2）这就是默认容量为10的代码
-（3）明确容量（判断是否扩容）
1、modCount这是一个全局变量，每次添加值都会对其++，
2、判断现有的数组长度是否已经不能容下新元素了
3、在我的测试代码中，前十个是不会扩容的，到第11个才会进入if
-（4）扩容
将原来的数组扩容原来的1.5倍得到一个新的数组，将原来的值copy到新数组。
2.2 Vector 源码
其实看了源码可以知道：
Vector底层也一个数组，基本上和ArrayList一直通过看源码，我们可以知道Vector是通过对每个方法添加synchronized关键字来保证这是一个线程安全的容器。
那么这样会使我们再使用这些方法时效率不高。
所以我们再日常开发中，很少使用他，但是再有竞争的情况下可以使用一下【其实使用也不是特别多，我们都是通过自己去完成的多】
2.3 LinkedList
1、底层是一个双向链表的数据结构
源码是定义了一个node节点，来存放前驱、后驱和元素
他的CRUD也是比较简单，主要就是基于双向链表的CRUD，要考虑好前驱指针和后驱指针指向的地址，就能弄明白。
- List下ArrayList和LinkedList的比较
三、Set容器
3.1 简介：
不可重复，无序（其实是按运算出来的hash值排序的【这里不是hashCode】）- 1
3.2 HashSet（底层同HashMap）
总体add流程如下图：
==》下图来自安琪拉大佬的流程图
- 测试代码
HashSet<Object> objects1 = new HashSet<>(); for (int i = 0; i < 3; i++) { objects1.add(i); } // 重复（看比较） objects1.add(2);- 1
- 2
- 3
- 4
- 5
- 6
2、HashSet源码解读（关键注释点【其实就是hashMap的源码】）
1）构造方法
构造方法也很清楚就是，hashMap
2）add方法-
2.1 向hashMap中put数据，key就是我们add进来的值，Value是共享的一个填充对象
填充对像
===========>这里往下就是HashMap的东西咯，小东西真面目流露了 -
2.2 再往下面调用Map中的put方法了
-
2.3 将hashCode进行运算
将hashcode进行高16位和低16位进行异或运算（这样做的目的就是尽量的避免哈希冲突）==》得到hash值
- 2.4 put的核心代码注释
第一段代码：
/** * 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; // 当定义的属性，数组位null 或者长队为0时调用resize方法进行长度的重置（下面的第二段代码注释） if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 使用n-1&hash计算下标值（数组长度&hash） if ((p = tab[i = (n - 1) & hash]) == null) // 当前下标为null，就放到对应的下标位置（放hash【方便做比较】，key，和value） tab[i] = newNode(hash, key, value, null); else { // 如果对应的下标位置不为null，那就是发生了hash碰撞 Node<K,V> e; K k; // 辅助局部变量 // 判断hash值是否相同（只要内存地址和equals一个比较为true，直接覆盖） 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); // 每次都会曲判断链表的长度是不是大于8，=》准备转红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 转为红黑树（这里面还必须判断数组长度是不是等于64）【下一段代码】 treeifyBin(tab, hash); break; } // 判断链表中的每个节点是否k相同 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; }- 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
第二段代码：
//注意：1、阈值 2、为什么数组的长度是2次幂的/** * 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) { // 必须是二次幂，判断是不是二次幂，是的话就赋值，不是的话将他改成二次幂的数 // 二次幂也是为了避免hash碰撞，在hash表中完成散列。 //（n-1）&hash这个是原因，如果不是二次幂，那n-1之后个位一定是0，那0和&任何数都是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 // 这里是初次使用的默认值是16 newCap = DEFAULT_INITIAL_CAPACITY; // 这是给扩容值进行计算（阈值是0.75*默认长度） //【这里之所以使用阈值计算扩容值，是为了防止并情况下扩容的问题假设你到满了才扩容，比如还剩4个位置，刚好同时来了5个，那怎么办呢】 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; }- 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
第三段代码（怎么转为红黑树还需要再看一下）
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 判断长度是否等于64（小于的话，先resize（）方法扩容数组【第二段代码】） if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((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); } }- 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
3.4 LinkedHashSet（底层同LinkHashMap）
1、LinkedHashSet简介
底层是由LinkHashMap来实现的
底层的数据结构是：数组+双向链表- 1、LinkedHashMap继承图（继承hashSet）
2、LinkedHashMap继承图（继承hashMap）
2、LinkedHashSet源码
总体来说和HashSet差不多，我们主要关注的就是双向链表
如图是LinkedHashMap中Entry是一个双向链表的节点，在原来hashMap的Node中添加了一个头指针和尾指针
四、Map容器
4.1 Map容器简介
-
1、Map容器主要是存放Key-Value的键值对
-
2、继承图
4.2 HashMap（HashSet中讲过，这里介绍忽略，自己跟一下源码会更清楚，这一小节主要跟一下树化的源码）
1、HashMap简介
2、树化源码解读
- （1）变成双向链表的树形节点
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 先判断数组是否=64，否的话就先扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); // 判断数组的当前位置是不是已经是node节点了，是的话下面的树化操作就不进行 else if ((e = tab[index = (n - 1) & hash]) != null) { // 辅助变量（大神的代码永远是要用到辅助变量的话才会去定义） TreeNode<K,V> hd = null, tl = null; // 使用 do-while循环，将每个节点树化 do { // 将节点树化 TreeNode<K,V> p = replacementTreeNode(e, null); // 判读辅助变量（那么第一个节点一定是null） if (tl == null) // null的时候走这个节点（辅助变量赋值） hd = p; else { // 当有值的时候，就将其前驱指针和后驱指针指向对应的位置 p.prev = tl; tl.next = p; } // 将没吃树化完成的节点就赋值给tl这个辅助变量 tl = p; } while ((e = e.next) != null); // 这时候table是一个链表，但是这时候是一个每个节点树形节点的双向链表 if ((tab[index] = hd) != null) // 将树形节点的双向链表正在的树化 hd.treeify(tab); } }- 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
（2）真正的树化(
红黑树这块是摘抄的需要深入的学习一下红黑树 https://blog.csdn.net/Saintmm/article/details/121582015)
1、遍历TreeNode双向链表，确定待插入节点x在其父节点的左边还是右边，然后将其插入节点到红黑树中；2、插入节点之后树结构发生变化，需要通过变色和旋转操作维护红黑树的平衡；
3、因为调整了红黑树，root节点可能发生了变化，所以需要把最新的root节点放到双向链表的头部，并插⼊到table数组中。
/** * Forms tree of the nodes linked from this node. * @return root of tree */ final void treeify(Node<K,V>[] tab) { TreeNode<K,V> root = null; // 最开始的x表示TreeNode双向链表的头结点 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) { x.parent = null; x.red = false; root = x; } else { // 第一部分 K k = x.key; int h = x.hash; Class<?> kc = null; // p 表示parent节点 for (TreeNode<K,V> p = root;;) { // dir表示x节点在parent节点的左侧还是右侧 int dir, ph; // ph表示parent节点的hash值 K pk = p.key; // pk表示parent节点的key值 // x节点在parent节点的左侧 if ((ph = p.hash) > h) dir = -1; // x节点在parent节点的右侧 else if (ph < h) dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) dir = tieBreakOrder(k, pk); // 第二部分 TreeNode<K,V> xp = p; // xp表示x的父节点 // 如果p节点的左节点/右节点不为空，则令p = p.left/p.right，继续循环 // 直到p.left/p.right为空 if ((p = (dir <= 0) ? p.left : p.right) == null) { // 令待插入节点x的父节点为xp, 即p x.parent = xp; // 根据dir判断插入到xp的左子树(<0)还是右子树(>0) if (dir <= 0) xp.left = x; else xp.right = x; // 往红黑树中插入节点后，进行树的平衡操作 root = balanceInsertion(root, x); break; } } } } // 将root节点插入到table数组中 moveRootToFront(tab, root); }- 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
-
红黑树的引入原因：
线性查找 —性能低—>二分查找— 二查叉树会出现退化成链表的问题—>出现AVL平衡二叉树—数据变化有频繁更新节点问题—>出现红黑树 -
红黑树视频链接
https://www.bilibili.com/video/BV1Tb4y197Fe/?spm_id_from=333.337.search-card.all.click&vd_source=3f506dfd7b2a19c74f99363591d70f4c
4.3 HashMap最变态的面试题
（总结+拓展于囧辉大神 囧辉大神链接）
1、HashMap的数据结构
JDK1.8底层是由“数组+链表+红黑树”组成
JDK1.7的时候是数组+链表2、1.8 为什么要改成“数组+链表+红黑树”？
- 1、最主要的是为了提高查找效率，因为当有大量的哈希碰撞时，如果是链表的话查询效率太低了。链表的时间复杂度是 O(n)；红黑树的时间复杂度是O(logn)
3、那在什么时候用链表？什么时候用红黑树？
这个源码里解释过
- 1、当数组的长度=64并且链表的长度大于8时转为红黑树
- 2、对于移除，当同一个索引位置的节点在移除后达到 6 个，并且该索引位置的节点为红黑树节点，会触发红黑树节点转链表节点（untreeify）。
如下图：
1、树形节点每次会调用split方法进行修剪树形结构
2、当树的节点小于6的时候转化为链表
3、调用untreeify方法，转为链表/** * Returns a list of non-TreeNodes replacing those linked from * this node. */ final Node<K,V> untreeify(HashMap<K,V> map) { Node<K,V> hd = null, tl = null; for (Node<K,V> q = this; q != null; q = q.next) { Node<K,V> p = map.replacementNode(q, null); if (tl == null) hd = p; else tl.next = p; tl = p; } return hd; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
4、为什么链表转红黑树的阈值是8？
- 1、是对于时间和空间上的权衡
- 红黑树的节点大小是链表节点的两倍
- 在数据少的情况下就不需要需要通过浪费空间来换取查询效率了，少的时候链表的查询速度是可以接受的
- 2、也是为了避免频繁转化为红黑树，影响效率
- 节点的分布频率会遵循泊松分布，链表长度达到8个元素的概率为0.00000006，几乎是不可能事件.（因此可以发现，链表的长度几乎不会达到8的长度，很少进行扩容，影响效率）
5、那为什么转回链表节点是用的6而不是复用8？
由上面一问，可以知道，我们做的这么多，其实很多都要尽量的避免链表和树之间的转换，因为转换的太频繁开销太大了。
那么选择6而不是8就是为了避免在一个值周围来回的徘徊，导致一直转换
6、HashMap 有哪些重要属性？分别用于做什么的（看源码）？
看注释就行
除了用来存储我们的节点 table 数组外，HashMap 还有以下几个重要属性：
1）size：HashMap 已经存储的节点个数；
2）threshold：扩容阈值，当 HashMap 的个数达到该值，触发扩容。
3）loadFactor：负载因子，扩容阈值 = 容量 * 负载因子。7、HashMap 的默认初始容量是多少？HashMap 的容量有什么限制吗？
- 初始的话：16
- 限制：长度必须是2次幂，原因上文见源码解读中
8、2次幂是怎么算的
HashMap 会根据我们传入的容量计算一个大于等于该容量的最小的2的N次方，例如传 9，容量为16。
static final int tableSizeFor(int cap) { int n = 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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
9、ashMap 的容量必须是 2 的 N 次方，这是为什么？
上文有
10、你说 HashMap 的默认初始容量是 16，为什么是16而不是其他的？
答：
我认为是16的原因主要是：16是2的N次方，并且是一个较合理的大小。如果用8或32，我觉得也是OK的。实际上，我们在新建 HashMap 时，最好是根据自己使用情况设置初始容量，这才是最合理的方案。11、负载因子为什么是0.75，达到数组的扩容条件
这个也是在时间和空间上权衡的结果。
如果值较高，例如1，此时会减少空间开销，但是 hash 冲突的概率会增大，增加查找成本；而如果值较低，例如 0.5 ，此时 hash 冲突会降低，但是有一半的空间会被浪费，所以折衷考虑 0.75 似乎是一个合理的值。12、HashMap 的插入流程是怎么样的？
见源码
13、计算 key 的 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. */ static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
14、为什么要将 hashCode 的高16位参与运算？（其实我在在手写hash表的时候是直接用hashcode%数组的长度的，这里通过hashcode的高16位和低16位进行了异或运算）
- 主要是为了在 table 的长度较小的时候，让高位也参与运算，并且不会有太大的开销
- 详细见辉哥博客
15、扩容（resize）流程介绍下？
16、HashMap 是线程安全的吗
不是。HashMap 在并发下存在数据覆盖、遍历的同时进行修改会抛出 ConcurrentModificationException 异常等问题，JDK 1.8 之前还存在死循环问题。
17、介绍一下死循环问题？
导致死循环的根本原因是 JDK 1.7 扩容采用的是“头插法”，会导致同一索引位置的节点在扩容后顺序反掉。而 JDK 1.8 之后采用的是“尾插法”，扩容后节点顺序不会反掉，不存在死循环问题。
待跑一下流程18、那总结下 JDK 1.8 主要进行了哪些优化？
1）底层数据结构从“数组+链表”改成“数组+链表+红黑树”，主要是优化了 hash 冲突较严重时，链表过长的查找性能：O(n) -> O(logn)。
2）计算 table 初始容量的方式发生了改变，老的方式是从1开始不断向左进行移位运算，直到找到大于等于入参容量的值；新的方式则是通过“5个移位+或等于运算”来计算。
// JDK 1.7.0 public HashMap(int initialCapacity, float loadFactor) { // 省略 // Find a power of 2 >= initialCapacity int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; // ... 省略 }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
// JDK 1.8.0_191 static final int tableSizeFor(int cap) { int n = 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; }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
3）优化了 hash 值的计算方式，老的通过一顿瞎JB操作，新的只是简单的让高16位参与了运算。
// JDK 1.7.0 static int hash(int h) { h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } // JDK 1.8.0_191 static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
4）扩容时插入方式从“头插法”改成“尾插法”，避免了并发下的死循环。
5）扩容时计算节点在新表的索引位置方式从“h & (length-1)”改成“hash & oldCap”，性能可能提升不大，但设计更巧妙、更优雅。
-
相关阅读:
Mybatis框架的缓存
Matlab匿名函数教程
【Redis入门笔记 04】事务的基本操作
Secrets
JWT+shiro+redis整合
单片机中的 _nop_() 延时以及其相关的基础扩展
VulnHub Alice
关于qt模型视图 QStandardItemModel 的通俗讲解
Vue--》计算属性与监视(侦听)属性的使用
Spring高手之路14——深入浅出：SPI机制在JDK与Spring Boot中的应用
- 原文地址：https://blog.csdn.net/weixin_46643875/article/details/127521649
