HashMap底层原理
HashMap
HashMap底层数据结构
- JDK1.7及之前：数组+链表
- JDK1.8:数组+链表+红黑树
HashMap 底层原理.png
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());
}
JDK 1.8中对hash算法和寻址算法是如何优化的？
map.put(“张三”, “测试数据”)
“张三”这个key计算他的hash值，是有一定的优化的，hash算法优化如下：
//JDK1.8HashMap的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位
hash值一样 -> 他们其实都会在数组里放在一个位置，进行复杂的hash冲突的处理
[16个元素] -> hash值对数组长度取模，定位到数组的一个位置，塞进去就ok了
寻址算法优化：
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）
[图片上传失败...(image-4a0921-1600908715333)]
两个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取模，取模性能不高，位运算的性能比较高
