- 1开讲：Windows服务器高并发处理IOCP（完成端口）详细说明 -- 学习自chao哥_iocp只能创建1万连接
- 2ollama集成open-webui本地部署大模型应用_ollama serve env
- 3嵌入式软件笔试常见编程题汇总_嵌入式软件笔试题库
- 4error: RPC failed; curl 56 GnuTLS recv error (-110): The TLS connection was non-properly terminated.
- 5Java | 如何利用AI给编程提效_ai编程java
- 6双向冒泡法，可以只求最大最小值
- 7使用Edge调试 安卓app应用或插件_edge inspect
- 8AI未来十年新范式，生成式人工智能的挑战与机遇_生成式ai+少样本
- 9关系抽取：SemEval2010 Task8数据集_semeval 2010 task 8数据集
- 10使用开源级PXB（Percona Xtrabackup）进行数据库物理备份与恢复
HashMap 1.8 最详细的源码图文解析(附常见问题)_hashmap1.8 数据结构图
赞
踩
/ 前言 /
HashMap是Java开发中最常用的集合之一 , 其独特数据结构使其适用于大部分场景 , 比ArrayList及HashSet有着更广泛的应用空间 , 但是也因为其独特的数据结构使其源码异常复杂 , 尤其是JDK1.8版本后的HashMap,使用了更加复杂的数据结构 , 本文主要讲解的是JDK1.8的HashMap, 本文会涉及到的内容如下所示
| 数据结构分析(红黑树) |
|---|
| 源码解析 |
| JDK1.8中hash碰撞的处理方式 |
| 计算hash值的方式 |
| HashMap的容量长度为什么一定要是2的非零次幂 |
| JDK1.7 和 JDK1.8中HashMap的不同 |
| HashMap最常见的问题 |
/ 1 / 数据结构
在JDK1.7中HashMap的数据结构是数组 + 链表 , 而在JDK1.8中则演化成了数组 + 链表 + 红黑树的结构 , 这也是1.8中最大的更新 , 下面我们来探究一下为何要演化为数组 + 链表 + 红黑树这样的数据结构
我们知道在1.7中当产生了hash碰撞时便会将当前Entry变成链表 , 单向链表查找除了head节点外的时间复杂度都是O(n) , 如果频繁的发生了hash碰撞每次查找元素都是非常耗费时间的 , 所以为了避免这一现象1.8中引入了红黑树
红黑树的插入、查找的时间复杂度都是O(log n) , 假如你的红黑树里面有256个数据 , 此时只需要8次就能找到目标数据 , 即使是65536个数据也只需要16次即可 , 效率相比链表而言提升的非常大
我们来看下HashMap转为红黑树后存储的数据结构图
现在我们知道了为何要引入红黑树 , 但是这就又衍生了一个问题 , 为什么不在一开始就使用红黑树来直接替代链表呢? 这个问题的答案在源码解析的核心参数中会有详细的解释
这篇文章的重点在于HashMap,有关于红黑树的介绍就暂时到此为止了 , 有兴趣的朋友可以网上找找红黑树的资料 , 我的笔记还在整理中…
/ 2 / 源码解析
2 . 1 核心参数
//默认初始化table数组容量16 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 //table最大容量1073741824 static final int MAXIMUM_CAPACITY = 1 << 30; //默认加载因子, 即当现有数组长度达到容量的75%时会进行扩容操作 static final float DEFAULT_LOAD_FACTOR = 0.75f; //1.8新增 当链表的长度 >=8 - 1 时会转换为红黑树, 关于为什么要定义为8的详细解读在下面↓ static final int TREEIFY_THRESHOLD = 8; //1.8新增 当红黑树的长度 <=6 时会转换为链表, 关于为什么红黑树 → 链表的阈值是6的详细解读在下面↓ static final int UNTREEIFY_THRESHOLD = 6; //1.8新增 红黑树的最小容量 static final int MIN_TREEIFY_CAPACITY = 64; //定义一个类型为Node<K,V>的table数组 transient Node<K,V>[] table; //table数组的长度 transient int size; //实际的扩容的阈值 threshold = 容量 * 加载因子 //在构造器中会被初始化为DEFAULT_INITIAL_CAPACITY的值16 //在第一次存储数据时会在inflateTable()方法中再次赋值threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); int threshold; //实际的加载因子, 在构造器中进行初始化 //如果创建HashMap时没有指定loadFactor的大小则会初始化为DEFAULT_INITIAL_CAPACITY的值 final float loadFactor; //HashMap更改的次数 //用来作为并发下判断是否有其它线程修改了该HashMap,抛出ConcurrentModificationException transient int modCount; //在初始化时指定初始长度及加载因子的构造器 public HashMap(int initialCapacity, float loadFactor) { ... } //在初始化时指定初始长度的构造器 public HashMap(int initialCapacity) { //这里调用的其实还是上面的构造器 this(initialCapacity, DEFAULT_LOAD_FACTOR); } //什么也不指定的构造器 , 这里不像1.7中还是去调用了有参构造器 , 具体原因下面会有分析 public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; }
- 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
我们来重点介绍几个核心参数
TREEIFY_THRESHOLD
这个参数是链表转换成红黑树的阈值 , 但是为什么是8呢?以及我们来看一下上面提到的关于为何不在一开始就用红黑树来替代链表
-
问 : 为什么不在一开始就使用红黑树来替代链表?
答 : 我们来看一段HashMao源码中的注解
* Because TreeNodes are about twice the size of regular nodes, we * use them only when bins contain enough nodes to warrant use * (see TREEIFY_THRESHOLD). And when they become too small (due to * removal or resizing) they are converted back to plain bins.- 1
- 2
- 3
- 4
在该注解中详细的说明了相同数据量下红黑树(TreeNode)占用的空间是链表(Node)的俩倍 , 考虑到时间和空间的权衡 , 只有当链表的长度达到阈值时才会将其转成红黑树
-
问 : 为什么链表 → 红黑树的阈值是8呢?
答 : 我们继续来看一段注解
* In usages with well-distributed user hashCodes, tree bins are * rarely used. Ideally, under random hashCodes, the frequency of * nodes in bins follows a Poisson distribution * (http://en.wikipedia.org/wiki/Poisson_distribution) with a * parameter of about 0.5 on average for the default resizing * threshold of 0.75, although with a large variance because of * resizing granularity. Ignoring variance, the expected * occurrences of list size k are (exp(-0.5) * pow(0.5, k) / * factorial(k)). The first values are: * * 0: 0.60653066 * 1: 0.30326533 * 2: 0.07581633 * 3: 0.01263606 * 4: 0.00157952 * 5: 0.00015795 * 6: 0.00001316 * 7: 0.00000094 * 8: 0.00000006 * more: less than 1 in ten million
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
HashMap的作者认为在理想的情况下随机hashCode算法下所有节点的分布频率会遵循泊松分布(Poisson distribution) , 上面也列举了链表长度达到8的概率是0.00000006,也就是说我们几乎不可能会使用到红黑树 , 所以作者使用8作为一个分水岭
UNTREEIFY_THRESHOLD
上面已经解释了为何链表 → 红黑树的阈值是8,这里我们来解释一下为何链表 → 红黑树的阈值却是6
问 : 为何链表 → 红黑树的阈值是6
答 : 假设UNTREEIFY_THRESHOLD的 = 7 , 当我们有频繁的添加和删除操作时 ,
hash碰撞产生的节点数量 一旦在7附件徘徊就会造成红黑树和链表的频繁转
换 , 此时我们大多数的性能就都耗费在了链表 → 红黑树和红黑树 → 链表` ,
这样反而就得不偿失了 , 所以作者将长度为7作为一个缓存地段从而选取了6
作为红黑树 → 链表的阈值
loadFactor
我们通常使用的构造器都是最后一个构造器 , 什么都不会传 , 如果我们需要更改加载因子的话需要注意几个点
- 加载因子并不是越大越好的 , 虽然加载因子越大就意味着HashMap的实际容量越大 , 扩容的次数越少 , 但是因为实际存储的数据大了 , 俩个相同容量的HashMap加载因子越大的那个读取的速度更慢 , 所以我们需要根据自己的实际使用情况来进行判断 , 是要存储更多的数据呢 , 还是要更快的读取速度
- 加载因子是会影响到扩容的次数的 , 如果加载因子太小的话HashMap会频繁的进行扩容 , 导致在存储的时候性能下降
- 如果我们在创建HashMap时就已经知道了要存储的数据量 , 那么我们完全可以通过实际存储数量 ÷ 0.75来计算出我们初始化的HashMap容量 , 这样可以避免HashMap再进行扩容操作 , 提升代码效率
modCount
关于modCount这里做一下解释 , 这个元素是用来干什么的呢?
我们知道HashMap不是线程安全的 , 也就是说你在操作的同时可能会有其它的线程也在操作该map,那样会造成脏数据 , 所以为了避免这种情况发生HashMap、ArrayList等使用了fail-fast策略 , 用modCount来记录修改集合修改次数
我们在边迭代边删除集合元素时会碰到一个异常ConcurrentModificationException , 原因是不管你使用entrySet()方法也好 , keySet()方法也好 , 其实在for循环的时候还是会使用该集合内置的Iterator迭代器中的nextEntry()方法 , 如果你没有使用Iterator内置的remove()方法 , 那么迭代器内部的记录更改次数的值便不会被同步 , 当你下一次循环时调用nextEntry()方法便会抛出异常
//篇幅有限, 这里只贴出了部分源码 private abstract class HashIterator<E> implements Iterator<E> { Entry<K,V> next; // next entry to return int expectedModCount; // For fast-fail int index; // current slot Entry<K,V> current; // current entry HashIterator() { //在构造器中初始化了expectedModCount = modCount expectedModCount = modCount; if (size > 0) { // advance to first entry Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } } final Entry<K,V> nextEntry() { //当迭代器中的修改次数与HashMap中记录的修改次数不相等时抛出异常 if (modCount != expectedModCount) throw new ConcurrentModificationException(); Entry<K,V> e = next; if (e == null) throw new NoSuchElementException(); if ((next = e.next) == null) { Entry[] t = table; while (index < t.length && (next = t[index++]) == null) ; } current = e; return e; } //迭代器内置的删除方法, 每次删除后都会将expectedModCount重置为modCount的值 public void remove() { if (current == null) throw new IllegalStateException(); if (modCount != expectedModCount) throw new ConcurrentModificationException(); Object k = current.key; current = null; HashMap.this.removeEntryForKey(k); expectedModCount = modCount; } }
- 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
2 . 2 存储的流程 - put()方法
我们先看流程图再看源码
源码解析
public V put(K key, V value) { return putVal(hash(key) , key, value, false, true); } //关于onlyIfAbsent,evict的讲解在下面↓ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 判断数组是否为空 , 为空则调用resize()方法进行初始化,resize()方法源码在下面↓ if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; // 如果当前数组索引位置的元素为null则直接创建新的节点并存到该索引位置的数组中 // 和JDK1.7的对比 //1. 其实这里的(n - 1) & hash就是JDK1.7中的indexFor()方法体中的(length - 1) & h,只不过在1.8中做了简化处理 if ((p = tab[i = (n - 1) & hash]) == null) //2. tab[i] = newNode(hash, key, value, null);在JDK1.7中时在createEntry()方法中完成创建Entry的 , 在1.8中该方法也被删除了 tab[i] = newNode(hash, key, value, null); // 走到这个else代码块中说明当前key已经在数组中存在了 || 发生了hash碰撞 else { Node<K,V> e; K k; // 判断当前key在数组中是否存在, 存在则不进行存储操作 // 有朋友好奇这里的p是在哪里初始化的, 其实在上一个if里面就被初始化了 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 判断当前节点类型是否是红黑树节点 else if (p instanceof TreeNode) // 将key、value存储到红黑树节点中 , 如果key已经存在 , 则返回之前的节点 , 源码解析在下面↓ e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 代码进入到这个else代码块就说明发生了hash碰撞 else { // 该代码块中的e的初始化会有俩种情况 // ① e是最后一个节点的next元素,e == null // ② e是和key相同的那个node for (int binCount = 0; ; ++binCount) { // 判断当前节点是否是链表的最后一个节 // ① if ((e = p.next) == null) { // 直接将当前要存储的key、value存储到上一个节点的next元素中 // 在JDK1.7中的会先将之前存储的节点取出来, 然后将之前的节点作为新节点的next元素存储到数组中 // 而在JDK1.8中会直接将新的节点放到之前存储节点的next元素中 // 也就是说JDK1.7中的链表插入顺序是从头部开始插入, 而在1.8中时从尾部开始插入 p.next = newNode(hash, key, value, null); // 因为这个循环是迭代链表的, 所以binCount代表着链表的长度, 如果链表长度超过阈值则会转换为红黑树 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st // 转换红黑树的源码解析在下面↓ treeifyBin(tab, hash); break; } // 当前节点不是最后一个节点, 判断当前节点的key与要存储的key是否相同 // ② if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } // e在只有当前key已经存在时才会完成初始化], 这里是统一处理, 返回key之前对应的value, 并判断是否要替换value,默认是替换 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; // 这里是个空方法体 afterNodeAccess(e); return oldValue; } } ++modCount; // 在JDK1.7中扩容操作是在存储数据之前发生的 // 在JDK1.8中扩容操作是在存储数据之后发生的 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
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
在存储流程中有几个方法和参数我们需要重点看一下
-
onlyIfAbsent、evict在1.8的HashMap中首次出现了这俩个形参 , 接下来我们看一下这俩个形参是做什么的
-
onlyIfAbsent如果为true，则不更改现有值 , 也就是说不会用新的value来替换旧的value
-
evict如果为false,则表处于创建模式 , 这个参数在
putVal()方法中在倒数第三行的afterNodeInsertion(evict);这里被使用到了 , 但是这个方法是一个空方法体 , 所以我们暂时无法探究其后续操作是什么
可能有的朋友会想
put()方法中onlyIfAbsent的值默认给了false,那这个参数又有什么意义呢 , 我们来看一下1.8中新增的一个方法putIfAbsent()public V putIfAbsent(K key, V value) { return putVal(hash(key) , key, value, true, true); }- 1
- 2
- 3
这个方法的功能和
put()是一样的 , 只不过这个方法默认是不替换旧的value,1.8中这样的设计给了开发人员更多的选择 -
-
hash()static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }- 1
- 2
- 3
- 4
这个方法是用来计算当前key的hash值的 , 为了减少hash碰撞发生的概率 , 获取当前key的
hashCode值后再进行一次位运算和一次异或运算 -
resize()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代码块中说明此时table数组已经完成过初始化 if (oldCap > 0) { // 判断当前容量是否已达到最大值 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } // 将新数组的容量设置为旧容量的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) // 这一步的操作等同于 oldThr * 2 newThr = oldThr << 1; // double threshold } // 进入到这个代码块说明在创建HashMap时使用的有参构造器 // 在翻阅代码后我们发现threshold的值会在有参构造器中被初始化 , 此时被初始化了就会使用指定的容量来完成table数组的初始化 else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 进入到这个else代码块中说明数组还未完成初始化 , 进行初始化操作 else { newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 只有调用有参构造器才让newThr == 0,至于为什么不放到上面的else if中 , 可能是为以后扩展做铺垫吧 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 { // loHead和loTail存储的是转移数据后仍然存储在当前索引位置的元素 Node<K,V> loHead = null, loTail = null; // hiHead和hiTail存储的是转移数据后存储到[j + oldCap]索引位置的元素 // 这里看不懂没事 , 接着往下看就明白了 Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; e = 1 e.next = 2 e.next.next = 3 do { // 为了方便讲明白这个循环里面的源码,我们来举个例子,假设此时链表有3个元素a,b,c // 第一次循环进入到① | ② // tail元素肯定为null,所以会将当前e赋值给head元素,并且为tail赋值,以便下次循环 // 此时head元素会含有e的链表关系即next元素指针,此时就是e=a head=a tail=a // 第二次循环进入① | ② // 还是会通过第一次进入时的索引判断 , 所以此时tail元素不会为null, // 此时就是 e=b head=a head.next=b tail=b tail.next=b // 因为在第一次进入的时候head和tail是同时指向e的 // 所以此时tail.next=b也就意味着head.next=b,所以才会先在else代码块中完成tail.next的初始化 // 再完成tail的初始化 // 第三次循环进入① | ② 就是 e=c head=a tail=c tail.next=c head.next.next=c // 以此类推.... next = e.next; // 这里会根据(e.hash & oldCap) == 0来将链表划分为俩部分 , 一部分仍然存储在旧链表的索引位置 , 另一部分存储到新数组的[j + oldCap]索引位置 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); // 将loHead存储到新数组的旧索引位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } // 将hiHead存储到新数组的[j + oldCap]索引位置 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
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
- 107
- 108
- 109
- 110
- 111
- 112
- 113
- 114
- 115
- 116
- 117
- 118
上面的源码解析中我们留了的问题 , 但是这个问题有一个前置的问题需要解决 , 我们一起来看下
-
为什么HashMap的容量一定要是2的非零次方幂而且还要进行
hash & (length - 1)的操作 -
为什么说在1.8中扩容时将旧数组中没有产生hash碰撞和不是红黑树节点的元素放到了新数组中旧元素索引位置?
问 : 为什么HashMap的容量一定要是2的非零次方幂而且还要进行
hash & (length - 1)的操作?答 : 我们来看2的2次方的二进制码
2 : 0010
4 : 0100
8 : 0000 1000
…
length - 1的二进制码
1 : 0001
3 : 0011
7 : 0111
…
我们可以看到如果容量是2的次方 , 那么
length - 1得到的二进制的除了补位外都是1,根据&运算符的规则 , 0&0=0; 0&1=0; 1&1=1;那么也就意味着不论hash的值是什么 , 只要length - 1的二进制码是这样规律的 , 那么就可以保证hash的值只有和length - 1的同位参与了运算, 例如二进制码A(10101011)&B(00001111)的结果就是C(00001011) , C的结果只会受到B二进制码后四位的影响 , 因为b的补位都是0 , 也就是说h & (length - 1)得到的索引不会大于length,也就不会越界问 : 为什么说在1.8中扩容时将旧数组中没有产生hash碰撞和不是红黑树节点的元素放到了新数组中旧元素索引位置?
答 : 因为
hash & (length - 1)操作的结果根本上是受hash的值的影响 ,
和length - 1其实没什么关系 , 所以只要hash的值不发生变化那么
由此计算出来的索引位置也不会改变在
1.7中会改变的,原因是在扩容时又调用了hash()方法 , 导致hash的值
发生了改变 -
treeifyBinfinal void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 断当前table是否为null || table长度是否小于红黑树最小容量(64) 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 { // replacementTreeNode()方法其实就是调用了TreeNode的构造器创建了一个红黑树节点 TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) // 初始化根节点 hd = p; else { // 设置前驱(prev)和后继(next)节点 , 形成双向链表 p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); // 将根节点存放到当前数组中 , 和把链表的head元素放到数组中是一样的原理 if ((tab[index] = hd) != null) // 彻底将table数组发生hash碰撞所产生的链表转换为红黑树 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
2 . 3 读取的流程 - get()方法
还是先看流程图再看源码
源码解析
public V get(Object key) { Node<K,V> e; return (e = getNode(hash(key) , key)) == null ? null : e.value; } 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; // 判断当前元素是否有next元素 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; }
- 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
/ 3 / JDK1.7 和 JDK1.8中HashMap的不同
3 . 1 存储流程
存储流程图的对比
取值流程图的对比
从流程图我们可以看出来1.8的HashMap流程更为复杂 , 逻辑线更多 , 但是性能更加强大 , 我们来看下具体代码中的不同
-
数据结构
- JDK1.7 : 数组 + 链表
- JDK1.8 : 数组 + 链表 + 红黑树
-
存储数据
- JDK1.7
- 有专程用来存储null键的方法
- 单独完成对数组的初始化
- 发生hash碰撞后会生成链表 , 采用头插法
- JDK1.8
- 1.8
没有专程用来存储null键的方法 - 将数组的初始化放到了
resize()方法中 - 发生hash碰撞后会生成链表 , 采用尾插法 , 如果链表存在并且达到转换阈值则会将链表转换为红黑树
- 1.8
- JDK1.7
-
扩容
- JDK1.7
- 会重新计算key的hash值和索引位置
- 转移数据时会颠倒Entry链表的顺序
- 转移数据时
不会将当前链表拆分 , 并且会重新计算索引位置 - 在并发下触发扩容可能会造成死循环
- JDK1.8
不会重新计算key的hash值- 转移数据时
不会颠倒Entry链表的顺序 - 转移数据时会将当前链表拆分成俩个链表 , 一个存放到旧索引位置 , 一个存放到(原位置 + 旧容量)索引位置
- 在并发下触发扩容
不会造成死循环
- JDK1.7
/ 4 / HashMap最常见的问题
-
问 : hash碰撞的处理方式
答 : 当发生hash碰撞时会将之前该索引位置存储的Entry作为新Entry的next元素
从而形成链表 , 并将新的Entry(链表的head元素)存储到该索引位置 -
问 : 为什么不直接使用key的hashCode值作为hash值而且还要进行多次的
扰动运算?答 : 因为hashCode的值作为hash值的话计算索引后可能会造成数组越界 ,
而且既然Java将hashCode与equal的比较作为衡量俩个对象是否相等的标准 ,
那么则意味着hashCode是有可能重复的 , 这样会造成多余的hash碰撞 ,
所以才会对hashCode进行多次的扰动运算 -
问 : 为什么HashMap的容量一定要是2的非零次幂而且计算索引时要进行
h & (length-1)这样运算?答 : 因为HashMap的容量如果是2的次方的话可以保证length - 1得到的二进制的
除了补位外都是1,根据&运算符的规则 , 0&0=0; 0&1=0; 1&1=1;那么也就
意味着不论h的值是什么 , 只要length - 1的二进制码是这样的规律的 , 那么就
可以保证hash的值只有和length - 1的同位参与了运算 , 例如二进制码
A(10101011) & B(00001111)的结果就是C(00001011) , C的结果只会受到
b二进制码后四位的影响 , 因为b的补位都是0 , 也就是说
h & (length - 1)得到的索引不会大于length,也就不会越界 -
问 : HashMap在扩容后容量是多少?
答 : 原有容量的2倍
-
问 : HashMap为什么不在一开始就使用红黑树来存储发生hash碰撞的元素?
答 : 当链表中的元素超过阈值(8)时会进行转换 , 而选择8作为这个阈值是因为相同
数据量下红黑树 (TreeNode)占用的空间是链表(Node)的俩倍 , 考虑到时间和
空间的权衡 , 只有当链表的长度达到阈值时才会将其转成红黑树 -
问 : HashMap什么时候会将链表转换为红黑树 , 为什么是阈值是这个值?
答 : 当链表中的元素超过阈值(8)时会进行转换 , 而选择8作为这个阈值是因为
HashMap的作 者认为在理想的情况下随机hashCode算法下所有节点的分布
频率会遵循泊松分布(Poisson distribution) , 方法的注解也列举了链表长度达
到8的概率是0.00000006,也就是说我们几乎不可能会使用到红黑树 , 所以
作者使用8作为一个分水岭 -
问 : HashMap什么时候会将红黑树转换为链表?
答 : 当红黑树中的元素少于阈值(6)时会将红黑树转换为链表
-
问 : 为什么链表 → 红黑树的阈值是8,红黑树 → 链表的阈值是6?
答 : 假设
UNTREEIFY_THRESHOLD的 = 7, 当我们有频繁的添加和删除操作时 ,
hash碰撞产生的节点数量 一旦在7附件徘徊就会造成红黑树和链表的频繁转
换 , 此时我们大多数的性能就都耗费在了链表 → 红黑树和红黑树 → 链表` ,
这样反而就得不偿失了 , 所以作者将长度为7作为一个缓存地段从而选取了
6作为红黑树 → 链表的阈值 -
问 : HashMap在扩容后之前hash冲突产生的链表的顺序会变吗?
答 : 1.7会颠倒链表顺序 , 1.8不会
-
问 : HashMap的默认加载因子是多少?
答 : 0.75
-
问 : HashMap的默认容量是多少?
答 : 16
-
问 : HashMap的默认实际存储容量是多少?
答 : 12
-
问 : HashMap为什么是线程不安全的?
答 : 因为HashMap没有同步锁
-
问 : 线程不安全会造成什么现象?
答 : 并发情况下会导致取出来的数据并不是想要的数据 , 数据已经被其它线程修改
了 , 而且当多个线程同时触发扩容操作时 , 最后一个线程新生成的table会覆
盖之前所有扩容的table
/ 5 / 结语
关于HashMap的分享我们就暂时告一段落了,HashMap在Java开发中有着广泛的应用场景 , 也是面试绕不过的坎 , 熟悉HashMap的源码可以帮助我们知其然并知其所以然 , 而且jdk经过了这么久的磨炼 , 留下来的都是精华 , 多阅读源码可以帮助我们提高对架构的理解 , 去看看优秀的架构师是怎么去做设计
后续如果我有什么新的理解我会及时回来更新的 , 接下来我们的目标转战ConcurrentHashMap
