1.hashmap 的底层数据结构
众所皆知 map 的底层结构是类似邻接表的结构, 但是进入 1.8 之后, 链表模式再一定情况下又会转换为红黑树
在 JDK8 中, 当链表长度达到 8, 并且 hash 桶容量超过 64(MIN_TREEIFY_CAPACITY), 会转化成红黑树, 以提升它的查询, 插入效率底层哈希桶的数据结构是数组, 所以也会涉及到扩容的问题.
当 MyHashMap 的容量达到 threshold 域值时, 就会触发扩容. 扩容前后, 哈希桶的长度一定会是 2 的次方.
1.1 为什么用红黑树
那么为什么用红黑树呢? 之前都是用的链表, 之前的文章有提到链表的随机访问效率是很低的, 因为需要从 head 一个个往后面找, 那么时间复杂度就是 O(n), 但是如果是红黑树因为红黑树是平衡二叉树, 说白了就是可以索引的, 那么时间复杂度只有 O(logn), 这样效率就可以得到很大的提高
也许有人就想问了, 那为什么还搞个链表啊, 直接用红黑树不就完了:
1. 链表比红黑树简单, 构造一个红黑树要比构造链表复杂多了, 所以在链表不多的情况下, 整体性能上来看, 当链表不长的时候红黑树的性能不一定有链表高
2. 还有一个节点的添加和删除的时候, 需要对红黑树进行旋转, 着色等操作, 这个就比链表的操作复杂多了
3. 所以为链表设置一个阈值用来界定什么时候进行树化, 什么时候维持链表, 从中间取得一个均衡是很重要的
1.2 为什么阈值是 64, 链表长度到 8
刚刚讲到红黑树查找效率是 O(logn)那么 8 的 log 是 3, 而使用链表, 我们之前也有提到, 源码会进行折半查找 (参考之前 linkedlist 源码分析) 那就是 8/2 = 4 平均查找长度是 4, 所以在 8 的时候是比较合适的因为 3 比 4 小
再比如链表长度为 6 的时候, 红黑树会退化为链表同理: 6=》log=2~3 和 8 类似, 但是 6/2=3 也很快, 而且红黑树很复杂, 所以是用的链表, 至于其中的数字 7 的作用是缓冲一下, 避免再长度为 7,8 徘徊的时候会频繁修改为红黑树和链表
还有为什么是 64, 参考网上记录是: 再低于 64 的时候容量比较小, hash 碰撞的几率比较大, 这种时候出现长链表的可能性比较大, 这种原因导致的长链表我们应该避免, 而是采用扩容的策略避免不必要的树化
接下来我们观察一下 hashmap 的继承结构, 了解一下
1.3 还有个问题负载因子的作用
0.75f 负载因子过高会导致链表过长, 查找键值对时间复杂度就会增高, 负载因子过低会导致 hash 桶的个数过多, 空间复杂度变高
注意构造函数:
hash 桶没有再构造函数中进行初始化, 而是再第一次存储键值的时候进行初始化, initialCapacity 返回一个大于等于初始化容量大小的最小 2 的幂次方
2.hashmap 的增长策略
2.1 插入数据
1. 插入数据的时候首先会判断 hash 桶是否为空, 如果为空会进行初始化, 这是避免调用构造函数之后没有数据导致, 而且再初始化的时候会调用扩容策略这个后面再讲
通过刚刚的学习我们知道 hashmap 有三种数据存放模式: 数组, 链表, 红黑树
判断是否为空, 如果为空, 直接数组存放
这里有个细节
hash(key)和(n - 1) & hash 的使用
第一个对 key 进行 hash 取值
2.1.1 为什么要用 hash(key), 当然 hash 肯定是必须的, 不然 object 对象怎么定位数组索引但是 hashcode 不行么?
这里是因为 hashcode 是 32 位的数据, 用 hashcode 和 n 相与的时候, 如果 n 比较小, 那么高位的数据基本就没用到(2 的 16 次幂以上的数据), 那么就会导致 hash 碰撞的概率加大
这里 hash(key)的操作是吧 hashcode 右移 16 位在和原来的 hashcode 进行异或操作, 相当于是吧高位的信息合并到低位上, 然后在和 n 做与运算, 这样高位低位的信息全部都有, 综合的话 hash 碰撞的概率相应减低
2.1.2 (n-1)&hash 是什么操作 hash%n 不行么?
------------------------------------------------------------------------------------------------------------------------------------
说明一下, 这两个操作都是取余操作, 之前有人说是取模, 这里科普一下, 取模和取余是不一样的
取模 (百度百科): 取模运算("Module Operation") 和取余运算 ("Complementation") 两个概念有重叠的部分但又不完全一致. 主要的区别在于对负整数进行除法运算时操作不同. 取模主要是用于计算机术语中. 取余则更多是数学概念. 模运算在数论和程序设计中都有着广泛的应用, 从奇偶数的判别到素数的判别, 从模幂运算到最大公约数的求法, 从孙子问题到凯撒密码问题, 无不充斥着模运算的身影. 虽然很多数论教材上对模运算都有一定的介绍, 但多数都是以纯理论为主, 对于模运算在程序设计中的应用涉及不多.
- 7 mod 4 = 3(商 = 1 或 2,1<2, 取商 = 1)
- -7 mod 4 = 1(商 = -1 或 -2,-2<-1, 取商 =-2)
- 7 mod -4 = -1(商 = -1 或 - 2,-2<-1, 取商 =-2)
- -7 mod -4 = -3(商 = 1 或 2,1<2, 取商 = 1)
- R = a -c*b
比如 - 7 mod 4 => -7 = 1 -2 * 4
求模运算和求余运算在第一步不同: 取余运算在取 c 的值时, 向 0 方向舍入 (fix() 函数); 而取模运算在计算 c 的值时, 向负无穷方向舍入 (floor() 函数).
符号相同时, 两者不会冲突. 比如, 7/3=2.3, 产生了两个商 2 和 37=3*2+1 或 7=3*3+(-2). 因此, 7rem3=1,7mod3=1. 符号不同时, 两者会产生冲突. 比如, 7/(-3)=-2.3, 产生了两个商 - 2 和 - 37=(-3)*(-2)+1 或 7=(-3)*(-3)+(-2). 因此, 7rem(-3)=1,7mod(-3)=(-2)
------------------------------------------------------------------------------------------------------------------------------------
好的, 我们继续讨论(n-1)&hash 和 hash%n 的问题
之前也有说到 hashmap 的扩容策略是大于等于初始化容量大小的最小 2 的幂次方, 那么也就是说 n 是 2 的倍数, 转换成 2 进制也就是最低位是 0, 再进行 - 1, 那就是奇数
而且进行 & 操作
这里注意我们的 n 是 2 的多次幂, 那么就是 000100000000 类似这样的二进制, 减一的结果就是除了最高位其余一下都是 1 也就是: 000011111111111
这个时候和原来的数据 hash 做 & 操作, 就会把超出这个 length 范围的数据全部设置为 0, 也就是这个范围以内的数据不会变
Example:
8 =》 0000 0000 0000 1000
8 - 1 =》 0000 0000 0000 0111
然后不论什么数据与 8-1 做 & 操作, 那么范围都在 0111 之内, 也就是 7 以内包含 7 范围再 0~7, 这样懂了吧, 比如 1000000&(7-1)结果就是 0~7
当然出现这种情况有个必要的条件就是长度必须是 2 的 n 次幂, 这样再二进制数列中, 永远只有一个位置是 1, 其余位置是 0,-1 之后, 这个位置一下的数据全包含再里面 & 就是截取低位的数据, 吧高位去掉, 相当于是取余了
因为不论什么数字都是 x = a1*2^(n-1) + a2*2^(n-2) + ... + a(n-1)*2^(1) + a(n)*2^(0), 高位的肯定都是 2 的 y 次幂的倍数, 所以去掉倍数, 剩下的就是余数, 不知道我这么说大家有没有理解...
大家还可以看看我之前的博客: https://www.cnblogs.com/cutter-point/p/11091727.html
如果不为空那么就要进行链表化或者树化了
2.1.3 如何链表化
说白了就是再 hash 桶的数组上获取这个位置上的 node 节点, 然后循环遍历获取到最后一个节点, 然后插入到节点末尾
- // 链表存放
- for (int binCount = 0; ; ++binCount) {
- if ((e = p.next) == null) {
- // 链表尾部插入, p 的 next 判断是否为空
- p.next = newNode(hash, key, value, null);
- // 当链表的长度大于等于树化阀值, 并且 hash 桶的长度大于等于 MIN_TREEIFY_CAPACITY, 链表转化为红黑树
- // 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;
- }
2.1.4 构造红黑树树化
红黑树的变换规则可以参考我之前的博客: https://www.cnblogs.com/cutter-point/p/10976416.html
我们什么时候会进行树化呢???
就是当我们的链表长度超过或等于 8 个的时候
至于如何吧这个链表组建为红黑树, 这个以后单独开章节细细探讨....
2.2 扩容策略 resize
- // 数组扩容
- public Node<K,V>[] resize() {
- Node<K,V>[] oldTab = table;
- int oldCap = (oldTab == null) ? 0 : oldTab.length;
- int oldThr = threshold;
- int newCap, newThr = 0;
- // 如果旧 hash 桶不为空
- if (oldCap> 0) {
- //// 超过 hash 桶的最大长度, 将阀值设为最大值
- if (oldCap>= MAXIMUM_CAPACITY) {
- threshold = Integer.MAX_VALUE;
- return oldTab;
- }
- // 新的 hash 桶的长度 2 被扩容没有超过最大长度, 将新容量阀值扩容为以前的 2 倍
- // 扩大一倍之后, 小于最大值, 并且大于最小值
- else if ((newCap = oldCap <<1) < MAXIMUM_CAPACITY &&
- oldCap>= DEFAULT_INITIAL_CAPACITY)
- // 左移 1 位, 也就是扩大 2 倍
- newThr = oldThr <<1;
- }
- else if (oldThr> 0) // 如果旧的容量为空, 判断阈值是否大于 0, 如果是那么就把容量设置为当前阈值
- newCap = oldThr;
- else { // zero initial threshold signifies using defaults
- newCap = DEFAULT_INITIAL_CAPACITY;
- newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
- }
- // 如果阈值还是 0, 重新计算阈值
- if (newThr == 0) {
- // 当 HashMap 的数据大小>= 容量 * 加载因子时, HashMap 会将容量扩容
- float ft = (float)newCap * loadFactor;
- // 如果容量还没超 MAXIMUM_CAPACITY 的 loadFactor 时候, 那么就返回 ft, 否则就是反馈 int 的最大值
- newThr = (newCap <MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
- (int)ft : Integer.MAX_VALUE);
- }
- //hash 桶的阈值
- threshold = newThr;
- // 初始化 hash 桶
- @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;
- // 如果旧的 hash 桶不为空, 需要将旧的 hash 表里的键值对重新映射到新的 hash 桶中
- 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
- // 如果是多个节点的链表, 将原链表拆分为两个链表, 两个链表的索引位置, 一个为原索引, 一个为原索引加上旧 Hash 桶长度的偏移量
- Node<K,V> loHead = null, loTail = null;
- Node<K,V> hiHead = null, hiTail = null;
- Node<K,V> next;
- do {
- next = e.next;
- // 在遍历原 hash 桶时的一个链表时, 因为扩容后长度为原 hash 表的 2 倍, 假设把扩容后的 hash 表分为两半, 分为低位和高位,
- // 如果能把原链表的键值对, 一半放在低位, 一半放在高位, 这样的索引效率是最高的
- // 这里的方式是 e.hash & oldCap,
- // 经过 rehash 之后, 元素的位置要么是在原位置, 要么是在原位置再移动 2 次幂的位置. 对应的就是下方的 resize 的注释
- // 为什么是移动 2 次幂呢?? 注意我们计算位置的时候是 hash&(length - 1) 那么如果 length * 2 相当于左移了一位
- // 也就是截取的就高了一位, 如果高了一位的那个二进制正好为 1, 那么结果也相当于加了 2 倍
- //hash & (length * 2 - 1) = length & hash + (length - 1) & hash
- if ((e.hash & oldCap) == 0) {
- // 如果这个为 0, 那么就放到 lotail 链表
- if (loTail == null)
- loHead = e;
- else
- loTail.next = e;
- loTail = e;
- }
- else {
- // 如果 length & hash 不为 0, 说明扩容之后位置不一样了
- if (hiTail == null)
- hiHead = e;
- else
- hiTail.next = e;
- hiTail = e;
- }
- } while ((e = next) != null);
- if (loTail != null) {
- loTail.next = null;
- // 而这个 loTail 链表就放在原来的位置上
- newTab[j] = loHead;
- }
- if (hiTail != null) {
- hiTail.next = null;
- // 因为扩容了 2 倍, 那么新位置就可以是原来的位置, 右移一倍原始容量的大小
- newTab[j + oldCap] = hiHead;
- }
- }
- }
- }
- }
- return newTab;
- }
总结就是扩容的时候吧数组大小扩大一倍, 相当于左移 1 位, 并且要重新计算 hash 散列值, 找对应的位置填充
链表也要进行拆分, 链表的拆分主要就体现在:
如果原来 hash 索引的位置就是这里, 那么还是连接再原来的节点上, 如果取余到对应的位置的节点, 数组扩大一倍, 我们原来的计算方式是 hash&(n - 1)
那么如果我们大小扩大一倍结果就是: hash&(2n - 1)=hash&n + hash&(n-1)因为 n 是 2 的 n 次幂, 除了对应的位置为 1 其余位置都为 0
那么这里就可以转换为 hash&(2n - 1)=hash&n + hash&(n-1) => n + hash&(n-1) => oldIndex + oldCap 也就是旧索引位置加上旧的容量大小
3.hashmap 查找数据
查找对于红黑树部分我们略过:
至于其他部分, 也就是跟之前大同小异了, 还是 hash 取位置, 然后取余获取对应的索引下标
首先检查是不是第一个, 如果是那就直接返回了
如果不是循环遍历链表找到对应的 key 为止
- final Node<K,V> getNode(int hash, Object key) {
- Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
- // 注意这一步中(n - 1) & hash 的值 等同于 hash(k)%table.length
- if ((tab = table) != null && (n = tab.length)> 0 &&
- // 这里是计算相当于是取余的索引位置(n - 1) & hash 等价于 hash % n
- // 而且由于 hashmap 中的 length 再 tableSizeFor 的时候, 就把长度设置为 2 的 n 次幂了, 那么 n-1 之后的值, 就是最高位全都是 0, 下面位数全是 1
- // 这个也就是取 hash 的低位的值
- (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;
- }
4.hashmap 删除数据
4.1 树形退化
红黑树, 我们就略过吧, 这里篇幅有限不做探讨....
5. 关于 hashmap 的特殊操作
这里可以讲讲 hashmap 的特殊地方了
1.hashmap 是允许 null 键和值的, 而 hashtable 就不允许了
参考:
- https://juejin.im/post/5a7719456fb9a0633e51ae14
- https://blog.csdn.net/xingfei_work/article/details/79637878
- https://juejin.im/post/5bed97616fb9a049b77fefbf
- https://www.zhihu.com/question/30526656
- https://juejin.im/post/5cb09c85e51d456e3428c0cf
来源: https://www.cnblogs.com/cutter-point/p/11396240.html