写点什么

HashMap 源码解析

用户头像
彭阿三
关注
发布于: 2020 年 09 月 24 日

HashMap底层数据结构

  • JDK1.7及之前:数组+链表

  • JDK1.8:数组+链表+红黑树



HashMap的一些重要参数

  • HashMap默认初始容量16 (一定是2的N次幂)

  • HashMap默认加载因子0.75

  • transient int size:表示当前HashMap包含的键值对数量

  • transient int modCount:表示当前HashMap修改次数

  • int threshold:表示当前HashMap能够承受的最多的键值对数量,一旦超过这个数量HashMap就会进行扩容

  • final float loadFactor:负载因子,用于扩容

  • static final int DEFAULT_INITIAL_CAPACITY = 1 << 4:默认的table初始容量

  • static final float DEFAULT_LOAD_FACTOR = 0.75f:默认的负载因子

  • static final int TREEIFY_THRESHOLD = 8: 链表长度大于该参数转红黑树

  • static final int UNTREEIFY_THRESHOLD = 6: 当树的节点数小于等于该参数转成链表



源码:

/**
* Returns a power of two size for the given target capacity.
*
*/
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;
}

当HashMap初始化的时候会调用上面的方法,如果设置了一个非2的N次幂的值M,会取大于M最接近2的N次幂的值X为HashMap初始容量,假设m=11,X=16,HashMap.size=16



以下代码可以观看HashMap的变化:

Map map = new HashMap(11);
map.put("1", "2");
//获取HashMap整个类
Class<?> mapType = map.getClass();
//获取指定属性,也可以调用getDeclaredFields()方法获取属性数组
Field threshold = mapType.getDeclaredField("threshold");
//将目标属性设置为可以访问
threshold.setAccessible(true);
//获取指定方法,因为HashMap没有容量这个属性,但是capacity方法会返回容量值
Method capacity = mapType.getDeclaredMethod("capacity");
//设置目标方法为可访问
capacity.setAccessible(true);
//打印刚初始化的HashMap的容量、阈值和元素数量
System.out.println("容量:"+capacity.invoke(map)+" 阈值:"+threshold.get(map)+" 元素数量:"+map.size());
for (int i = 0;i<17;i++){
map.put(i,i);
//动态监测HashMap的容量、阈值和元素数量
System.out.println("容量:"+capacity.invoke(map)+" 阈值:"+threshold.get(map)+" 元素数量:"+map.size());
}
//执行结果如下:
容量:16 阈值:12 元素数量:1
容量:16 阈值:12 元素数量:2
容量:16 阈值:12 元素数量:3
容量:16 阈值:12 元素数量:4
容量:16 阈值:12 元素数量:5
容量:16 阈值:12 元素数量:6
容量:16 阈值:12 元素数量:7
容量:16 阈值:12 元素数量:8
容量:16 阈值:12 元素数量:9
容量:16 阈值:12 元素数量:10
容量:16 阈值:12 元素数量:11
容量:16 阈值:12 元素数量:12
容量:32 阈值:24 元素数量:13
容量:32 阈值:24 元素数量:14
容量:32 阈值:24 元素数量:15
容量:32 阈值:24 元素数量:16
容量:32 阈值:24 元素数量:17
容量:32 阈值:24 元素数量:18

JDK 1.8中对hash算法和寻址算法是如何优化的

map.put(“张三”, “测试数据”)

“张三”这个key计算他的hash值,是有一定的优化的,hash算法优化如下:

//JDK1.8HashMap的hash()源码
//不是单纯的做了一下hash而是做了位运算
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

比如说:有一个key的hash值

1111 1111 1111 1111 1111 1010 0111 1100

0000 0000 0000 0000 1111 1111 1111 1111 ^

1111 1111 1111 1111 0000 0101 1000 0011 -> int值,32位



主要原因:让低16位具备高16位的特征,减少hash冲突的可能性

寻址算法优化:

hash对n取模的效果 -> hash & (n - 1),效果是一样的,后者的性能更高

1111 1111 1111 1111 1111 1010 0111 1100(没有经过优化的hash值)

0000 0000 0000 0000 0000 0000 0000 1111



相当于,你直接这么搞,高16位之间的与运算,是可以忽略的,核心点在于低16位的与运算,hash值的高16位没有参与到与运算里来啊,所以在hash的时候做了一个^的位运算,让低16位具备高16位的特征。



总结:

hash算法的优化:对每个hash值,在他的低16位中,让高低16位进行了异或,让他的低16位同时保持了高低16位的特征,尽量避免一些hash值后续出现冲突,大家可能会进入数组的同一个位置

寻址算法的优化:用与运算替代取模,提升性能



HashMap如何解决Hash冲突(碰撞)

hash冲突的解决方式

  • JDK1.7及之前:链表

  • JDK1.8:链表+红黑树 O(n)和 O(logn)





两个key,多个key,他们算出来的hash的值,与n-1,与运算之后,发现定位出来的数组的位置还是一样的,hash碰撞,hash冲突

Entry[0]这个位置就如图是一个链表,在添加键值对的时候先判断key是否为null,如果key===null,放置在Entry[0]的存储位置,在判断该位置是否有元素存在,如果已经存在元素,则遍历Entry[0]的单链表,判断是key是否存在如果存在刷新值,如果不存在新生成一个Entry实体添加到链表尾部。



重点:在JDK1.8之前,新插入的元素都是放在了链表的头部位置,但是这种操作在高并发的环境下容易导致死锁,所以JDK1.8之后,新插入的元素都放在了链表的尾部。

链表长度超过阀值8链表会变成红黑树,在性能上会得到一些提升,在链表长度小于6的时候会转为普通链表



public V put(K key, V value) {
//调用putVal()方法完成
return putVal(hash(key), key, value, false, true);
}
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断table是否初始化,否则初始化操作
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) {
p.next = newNode(hash, key, value, null);
//链表长度8,将链表转化为红黑树存储
if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
treeifyBin(tab, hash);
break;
}
//key存在,直接覆盖
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}
}
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
afterNodeAccess(e);
return oldValue;
}
}
//记录修改次数
++modCount;
//判断是否需要扩容
if (++size > threshold)
resize();
//空操作
afterNodeInsertion(evict);
return null;
}

HashMap如何扩容的

n - 1 0000 0000 0000 0000 0000 0000 0000 1111

hash1 1111 1111 1111 1111 0000 1111 0000 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)



n - 1 0000 0000 0000 0000 0000 0000 0000 1111

hash2 1111 1111 1111 1111 0000 1111 0001 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)



在数组长度为16的时候,他们两个hash值的位置是一样的,用链表来处理,出现一个hash冲突的问题



果数组的长度扩容之后 = 32,重新对每个hash值进行寻址,也就是用每个hash值跟新数组的length - 1进行与操作



n-1 0000 0000 0000 0000 0000 0000 0001 1111

hash1 1111 1111 1111 1111 0000 1111 0000 0101

&结果 0000 0000 0000 0000 0000 0000 0000 0101 = 5(index = 5的位置)



n-1 0000 0000 0000 0000 0000 0000 0001 1111

hash2 1111 1111 1111 1111 0000 1111 0001 0101

&结果 0000 0000 0000 0000 0000 0000 0001 0101 = 21(index = 21的位置)



总结:

判断二进制结果中是否多出一个bit的1,如果没多,那么就是原来的index,如果多了出来,那么就是index + oldCap,通过这个方式,就避免了rehash的时候,用每个hash对新数组.length取模,取模性能不高,位运算的性能比较高

发布于: 2020 年 09 月 24 日阅读数: 90
用户头像

彭阿三

关注

java工程师 2019.06.28 加入

一个慵懒的程序员。

评论

发布
暂无评论
HashMap源码解析