记一次1.8的hashmap源码学习
jdk1.8 HashMap
-
hashmap初始化后设定初始阈值，并不初始化。threshold 计算2的n次幂。
比如构造3的hashmap，最终初始化容量为4，threshold为3。没有设置初始构造容量，那么在初始化的时候默认为16。
- 构造
public HashMap(int initialCapacity, float loadFactor) {
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
//初始化加载因子 loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity);
}
tableSizeFor
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;
}
- 第一次putval时候，如果表为空的话resize方法()初始化initCap = threshold的hash数组，threshold=loadFactor*initCap； 然后oldhash表不为空就， rehash。
- 初次初始化的时候。
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
newCap = oldThr;
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;
return newTab;
//oldTab不为空 rehash 元素移动
resize方法，其中包含rehash，将oldTab数据转移到新的hash表。
- HashMap的初始化是在第一次put的时候完成的。
rehash是在需要扩容时机才执行的，一次rehash完。
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
//如果oldCap不为空的话，就是hash桶数组不为空
if (oldCap > 0) {
//如果大于最大容量了，就赋值为整数最大的阀值 threshold = Integer.MAX_VALUE;
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
//如果当前hash桶数组的长度在扩容后仍然小于最大容量 并且oldCap大于默认值16
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 旧的容量为0，但threshold大于零，代表有参构造有cap传入，threshold已经被初始化 成最小2的n次幂
// 直接将该值赋给新的容量
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 无参构造创建的map，给出默认容量和threshold 16, 16*0.75
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 新的threshold = 新的cap * 0.75
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;
//如果old表有数据 需要数据迁移
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 旧数组的桶下标赋给临时变量e，并且解除旧数组中的引用，否则就数组无 法被GC回收
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 如果e是TreeNode并且e.next!=null，那么处理树中元素的重排
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 链表头节点
else { // preserve order
// loHead,loTail 代表扩容后不用变换下标，见注1
Node<K,V> loHead = null, loTail = null;
// hiHead,hiTail 代表扩容后变换下标，见注1
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;
//j原有的hash索引，oldcap+j = 新的hash索引
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
putval过程。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
if ((tab = table) == null || (n = tab.length) == 0)
n = (tab = resize()).length;
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
Node<K,V> e; K k;
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) {
//链表尾部插入 node
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
// 判断是否需要转换为红黑树 8
treeifyBin(tab, hash);
break;
}
// 判断hashcode、key是否相等，相等覆盖返回该node 即后面的e
// ((k = e.key) == key 普通类类型 判断直接
// (key != null && key.equals(k)) 则用于判断复杂类类型
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
//判断是否有返回的Node 即有key相等情况 需要覆盖value
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//访问后的回调方法 子类实现
afterNodeAccess(e);
// 返回old value
return oldValue;
}
}
// put完 modCount++ 保证线程安全的 fast-fail机制
++modCount;
if (++size > threshold)
resize();
// 调用插入完成的后置方法 子类实现
afterNodeInsertion(evict);
return null;
}
当我们put的时候，首先计算 key 的 hash 值，这里调用了 hash 方法， hash 方法实际是让key.hashCode() 与 key.hashCode()>>>16 进行异或操作，高16bit补0，一个数和0异或不变，所以 hash 函数大概的作用就是：高16bit不变，低16bit和高16bit做了一个异或，目的是减少碰撞。按照函数注释，因为bucket数组大小是2的幂，计算下标 index = (table.length - 1) & hash ，如果不做 hash 处理，相当于散列生效的只有几个低 bit 位，为了减少散列的碰撞，设计者综合考虑了速度、作用、质量之后，使用高16bit和低16bit异或来简单处理减少碰撞，而且JDK8中用了复杂度 O（logn）的树结构来提升碰撞下的性能。
putval大致流程：
-
判断键值对数组table[i]是否为空或为null，否则执行resize()进行扩容；
-
根据键值key计算hash值得到插入的数组索引i，如果table[i]==null，直接新建节点添加，转向⑥，如果table[i]不为空，转向③；
-
判断table[i]的首个元素是否和key一样，如果相同直接覆盖value，否则转向④，这里的相同指的是hashCode以及equals；
-
判断table[i] 是否为treeNode，即table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对，否则转向5；
-
遍历table[i]，判断链表长度是否大于8，大于8的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现key已经存在直接覆盖value即可；
-
插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。
hash函数
就算hashcode分布的再松散，要是只取最后几位的话，碰撞也会很严重。进一步降低hash碰撞的概率，使得数据分布更平均，这样的操作被称为扰动。
static final int hash(Object key) {
// 与自己 右移16位进行异或运算（高低位异或）
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
常见问题
HashMap 为什么使用链表还要红黑树
- 链表查询效率低，插入删除效率高
- 红黑树查询效率高，插入删除效率低
HashMap 为什么使用红黑树么不使用平衡二叉树
红黑树的平衡调整开销相比于AVL的多次旋转要小，效率更高。
为什么要设计大于阈值8转红黑树，小于6才转链表？
主要是7作为缓冲，如果直接设计为大于8红黑树，小于8链表的话，如果插入较为频繁的话，就有可能造成频繁的链表和红黑树之间的切换，开销更大。
为什么选择0.75作为默认的负载因子
过大造成 hash冲突的可能性更高，put效率降低；如果过小的话，那就造成过大的空间浪费。而取0.75是综合考虑时间和空间的结果。
22.jdk7的HashMap为什么采用头插法？
HashMap的开发者认为后面被插入的对象，被查找的可能性更大，而链表查找元素从头遍历，所以采用头插法往往能够提升查找效率。
23.jdk8相比之前的版本，解决了HashMap哪些线程安全问题？
jdk8的HashMap在处理hash冲突时，采用尾插法代替头插法，扩容时避免了翻转链表的发生，也就是解决了循环链表的问题。
25.链表转化为红黑树的阈值为啥是8呢？
如果 hashCode的分布离散良好的话，那么红黑树是很少会被用到的，因为各个值都均匀分布，很少出现链表很长的情况。在理想情况下，链表长度符合泊松分布，各个长度的命中概率依次递减，当长度为8的时候，概率概率仅为十万分之6，这么小的概率，HashMap的红黑树转换几乎不会发生。
- 大于8的链表查询速度很慢，而在实际使用中，hashCode设计的好，很小的概率会发生转换为红黑树。
String最适合作为Key
因为字符串是不可变的，所以在它创建的时候hashcode就被缓存了，不需要重新计算。这就使得字符串很适合作为Map中的键，字符串的处理速度要快过其它的键对象。这就是HashMap中的键往往都使用字符串。
在java的对象头部有一个8byte的markword字段会在无锁状态下缓存该对象的一个hashcode信息。
30.除了链表尾插和红黑树，HashMap在jdk1.8和jdk1.7还有哪些差异？
1）JDK1.7是先扩容后插入，jdk1.8是先插入后扩容。
2）JDK1.7扩容需要重新hash来定位每个元素在桶中的位置，jdk1.8不需要
你说说红黑树的特点？
1）每个节点非红即黑
2）根节点总是黑色的
3）如果节点是红色的，则它的子节点必须是黑色的（反之不一定）
4）每个叶子节点都是黑色的空节点（NIL节点）
5）从根节点到叶节点或空子节点的每条路径，必须包含相同数目的黑色节点（即相同的黑色高度）
linkedHashMap
LinkedHashMap 需要重写实现的方法
// Callbacks to allow LinkedHashMap post-actions
void afterNodeAccess(Node<K,V> p) { }
void afterNodeInsertion(boolean evict) { }
void afterNodeRemoval(Node<K,V> p) { }
LinkedHashMap
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-bY9rUbOX-1657099033314)(/Users/skybox/Library/Application%20Support/typora-user-images/image-20220705115130424.png)]
阿里巴巴规范
首先先放出结论，根据阿里巴巴java开发规范中，第一章第五节第9点；
【推荐】集合初始化时，指定集合初始值大小。
说明：HashMap 使用 HashMap(int initialCapacity) 初始化， 正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子（即 loader
factor）默认为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）。
反例：HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被迫扩大，resize 需要重建 hash 表，严重影响性能。
所以实际开发过程中能确定hashmap的容量就尽量按照以上公式确定初始容量，否则默认16。
也就是公式：
n ----- 需要存储的元素个数
c ----- 建议设置容量大小
c = （n * 4 / 3） + 1
如果我们需要存3个，按这个公式应该设置为5，而不是4，其实它的容量也不是5，而是8。
扫一扫
4496
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
