HashMap相关
存储结构
HashMap是数组+链表+红黑树(JDK1.8增加了红黑树部分)实现的
数组是 HashMap 的主体,链表是为了解决hash冲突而存在的,采用的是链地址法
当数组table中某个元素的链表长度大于8的时候,开始尝试进行树化,如果此时table.length小于64,则对数组扩容,否则对链表进行树化。(重点哦~)
简单的看完了它的存储结构,接下来看看它比较重要的一些参数
Hashmap的一些默认构造参数
int threshold; // 所能容纳的key-value对的最大值
final float loadFactor; // 负载因子
int modCount; //记录当前集合被修改的次数
int size; //实际存在的键值对的数量
table的初始化长度length(默认值是16),Load factor为负载因子(默认值是0.75),threshold是HashMap所能容纳键值对的最大值。threshold = length * Load factor。当存在的键值对达到threshold后,进行扩容,扩容成员来的两倍。
索引计算
了解完了存储结构的一些知识点后,我们再来看看hashmap是如何确定即将添加元素应该放在数组table的哪个节点(索引)的。
首先根据node的key的值计算出hashcode的值,然后根据hashcode计算出hash值,最后通过hash&(length-1)计算得到存储的位置。看看源码的实现:
// jdk1.8
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
/*
h = key.hashCode() 为第一步:取hashCode值
h ^ (h >>> 16) 为第二步:高位参与运算
*/
}
//取key的 hashCode 值、根据 hashcode 计算出hash值、通过取模计算下标。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
为什么要 hashcode 异或其右移十六位的值?
可以在数组 table 长度比较小的时候,也能保证考虑到高低Bit都参与到Hash的计算中,同时不会有太大的开销
为什么 hash 值要与length-1相与?
这里的计算和用hash值对数组长度取模的运算时一样的,但是取模运算比与运算慢很多。
put方法
简要流程如下:
- 首先根据 key 的值计算 hash 值,找到该元素在数组中存储的下标;
- 如果数组是空的,则调用 resize 进行初始化;(第一次put的时候进行初始化)
- 如果没有哈希冲突直接放在对应的数组下标里;
- 如果冲突了,且 key 已经存在,就覆盖掉 value;
- 如果冲突后,发现该节点是红黑树,就将这个节点挂在树上;
- 如果冲突后是链表,判断该链表是否大于 8 ,如果大于 8 并且数组容量小于 64,就对数组进行扩容(resize);如果链表节点大于 8 并且数组的容量大于 64,则将当前节点的链表转换为红黑树;
jdk1.7和1.8put方法有什么不同
①解决哈希冲突时,JDK1.7 只使用链表,JDK1.8 使用链表+红黑树,当满足一定条件,链表会转换为红黑树。
②链表插入元素时,JDK1.7 使用头插法插入元素,在多线程的环境下有可能导致环形链表的出现,扩容的时候会导致死循环。
扩容机制
JDK1.7
使用一个容量更大的数组来代替已有的容量小的数组,transfer()方法将原有Entry数组的元素拷贝到新的Entry数组里,并且需要重新计算数组的下标。
newTable[i] 的引用赋给了 e.next ,也就是使用了单链表的头插入方式,同一位置上新元素总会被放在链表的头部位置;这样先放在一个索引上的元素终会被放到 Entry 链的尾部(如果发生了 hash 冲突的话)
JDK1.8
对比JDK1.7的优化
第一点:
resize 之后,元素的位置在原来的位置,或者原来的位置 +oldCap (原来哈希表的长度)。不需要像 JDK1.7 的实现那样重新计算所有元素的hash 。
只需要看看原来的 hash 值新增的那个bit是1还是0就好了(因为扩容是乘以2,并且是与运算,所以看新增的bit即可),如果新增的Bit是0的话索引不变,是1的话索引变成“原索引 + oldCap ”。省去了重新计算 hash 值的时间。
JDK1.7 中 rehash 的时候,旧链表迁移新链表的时候,如果在新表的数组索引位置相同,则链表元素会倒置(头插法)。JDK1.8 不会倒置,使用尾插法。
相关问题
为什么用在长度为8的时候转换成红黑树呢?
红黑树需要进行左旋,右旋,变色这些操作来保持平衡,而单链表不需要。
当元素小于 8 个的时候,此时做查询操作,链表结构已经能保证查询性能,超过8了以后,红黑树查询平均时间复杂度为o(nlogn),查询效率更加快,所以转换成红黑树。
如果一开始就用红黑树结构,元素太少,新增效率又比较慢,浪费性能。
为什么要用红黑树呢,可以用二叉搜索树嘛?
二叉搜索树是一种节点值之间具有一定数量级次序的二叉树,对于树中每个节点:
- 若其左子树存在,则其左子树中每个节点的值都不大于该节点值;
- 若其右子树存在,则其右子树中每个节点的值都不小于该节点值。
二叉搜索树在极端情况下会变成线性结构,查找效率会退化的和链表一样o(n).
table数组扩容
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;
}
/* 会取大于或等于这个数的 且最近的2次幂作为 table 数组的初始容量
解释:位或( | )
int n = cap - 1; 让cap-1再赋值给n的目的是另找到的目标值大于或等于原值。例如二进制1000,十进制数值为8。如果不对它减1而直接操作,将得到答案10000,即16。显然不是结果。减1后二进制为111,再进行操作则会得到原来的数值1000,即8。
*/
用可变类当 HashMap 的 key 有什么问题?
hashcode 可能发生改变,导致 put 进去的值,无法 get 到元素。
为什么hashmap的初始长度是16
为了方便通过hash算法计算key值对应的数组下标。
**Hashmap比较基础的相关知识点就是这些了,后续再补充Currenth