HashMap源码解析
2022-09-17 本文已影响0人
天还下着毛毛雨
数据结构
//一个Node数组,Node是一个单向链表
transient Node<K,V>[] table;
//Node内部类
static class Node<K,V> implements Map.Entry<K,V> {
// hash值
final int hash;
// key
final K key;
// value
V value;
// 下一个节点,形成单向链表
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
image.png
1.hash算法
put操作时,会先计算key的hash值
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
static final int hash(Object key) {
int h;
// 如果key是null，那么hash值就为0，所以为null的key只能存在一个。
// 否则, 取key的hashCode 按位异或(位不同 结果为1，其余为0) hashCode 无符号右移16位
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
经典问题1：为什么hashCode 要无符号右移 16位后 再与hashCode进行 异或操作？
image.png
将h无符号右移16为相当于将高区16位移动到了低区的16位，再与原hashcode做异或运算。
从上文可知高区的16位与原hashcode相比没有发生变化，低区的16位发生了变化
我们可知通过上面(h = key.hashCode()) ^ (h >>> 16)进行运算可以把高区与低区的二进制特征混合到低区，那么为什么要这么做呢？
因为 重新计算出的新哈希值在后面将会参与hashmap中数组槽位的计算。
计算公式：(n - 1) & hash，假如这时数组槽位有16个，则槽位计算如下：
image.png
可以看到 高区的16位很有可能会被数组槽位数的二进制码锁屏蔽，并没有参与到 槽位的计算中,也就是在计算槽位时将丢失高区特征。高位不同，低位相同的hashCode 出现哈希碰撞的 概率增大。
2. 计算槽位
// n为数组长度
(n - 1) & hash
经典问题2：为什么槽位数必须使用2^n
因为 a %b,当b等于2的n次方时， 等价于 a & (b - 1)，也就是 a % (2^n) 等价于 a & (2^n - 1) ，可以直接转化为 按位与 ，位运算的运算效率高于算术运算。
image.png
2^n -1 比较特殊 ， 倒数第n位以及它之前的全部是0，后面全部是1，与其他数做&运算时，刚好可以把 表示 2^n倍数的位全部 抹成0,剩下的就是 取余后的结果。
3. put操作�
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//获取hash值
static final int hash(Object key) {
int h;
//获取key的hashcode,并亦或哈希值的右移16位之后的值,再返回
//为什么要右移16位？
//加入高16位特征，减少哈希冲突
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
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;
//首先根据(n-1)&hash === n%hash,这个运算可以获取一个0到数组长度-1的值(不会超出数组),来获取在数组的下表位置,如果没值,创建一个新的链表(node头节点)
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值与要put的值相等，那就把头结点p赋值给e
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
e = p;
// 如果node节点已经 进化成 红黑树了
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
else {
// 如果还是链表的话，一直往下循环
for (int binCount = 0; ; ++binCount) {
// 如果当前值是null，说明已经到达了链表的尾部，仍然没有找到之前存在的key
if ((e = p.next) == null) {
// 就在链表尾部 新建并加入一个node节点，
p.next = newNode(hash, key, value, null);
// 如果遍历次数达到7，也就是链表长度到达8（加上了上面新加入的节点）, 进化成 红黑树
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
// 加入节点 或者长度达到8时进化成红黑树之后, 退出for循环
break;
}
// 如果当前节点e不等于null,判断当前Node key是不是与要加入的k相等,相等就返回,到下面 替换当前节点的e.value为新值
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
// 如果e有值,说明这个key之前是存在的,
if (e != null) { // existing mapping for key
V oldValue = e.value;
// 替换e.value 为新值
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
// 并返回
return oldValue;
}
}
++modCount;
// 如果当前占用槽位的数量> 长度*负载因子0.75
if (++size > threshold)
// 扩容
resize();
afterNodeInsertion(evict);
return null;
}
看完以上HashMap的put操作我们就可以这样一个疑问
为什么重写一个类的equals方法，需要重写类的hashcode方法。
在hashSet和hashMap等根据Hash值进行判断的几个中,假设你重写了equals方法,改变了对象的比较逻辑,但未重写hashcode方法,即使你put了两个内容相等的对象,但hashMap还是认为你是不同的key，因为你判断的是hashcode，导致都插入成功.
4. 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;
// "tab[(1)&hash]"取出该key计算哈希之后对应数据下标的头结点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 判断头结点的hash值是否与传入的Hash值相等并且（头结点的Key是否与传入的key 地址相等 或者内容相等）
// 为什么要先判断一下((k = first.key) == key || (key!= null && key.equals(k)))呢？
// 其实hashMap的链表存的只是hashCode相同的一个集合,有可能key值的内容是不同的，但计算出的哈希一样,这样hashMap还是会把他们放入同一个节点中.
//这个操作其实就是找到链表中key与传入key相等的节点
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;
}
5. 扩容resize
当数组被占用的数量 > 数组长度 * 加载因子 0.75，就会扩容，容量*2。 扩容后会把所有值的 node节点 重新计算hash槽位，再设置到扩容后的数组中。
问题三 ：为什么要扩容？
当HashMap中元素越来越多时，由于槽位数固定，碰撞的几率越来越高,为提高效率，进行扩容，增加槽位。
增大取模之后值的范围,减少哈希冲突,减缓链表长度越来越长的原因
加载因子 0.75(默认)
static final float DEFAULT_LOAD_FACTOR = 0.75f;
总结
应尽量避免resize，如果预支元素的个数,可以指定hashmap的容量,比如1000，应制定为 2048（2000的话hashMap会自动设置为2的n次方）,因为 2048*0.75>1000，既避免了碰撞几率过大的风险，又规避了resize操作。
