【数据结构】8.java源码关于HashMap
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了【数据结构】8.java源码关于HashMap，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含11491字，纯文字阅读大概需要17分钟。
内容图文
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
内容总结
以上是互联网集市为您收集整理的【数据结构】8.java源码关于HashMap全部内容，希望文章能够帮你解决【数据结构】8.java源码关于HashMap所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。