HashMap快速理解

参考文章

基本知识：

1.HashMap默认数组长度

 static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 16

2.负载英子默认值

static final float DEFAULT_LOAD_FACTOR = 0.75f;

最重要的是元素插入的位置和key的hash值有关

static final int hash(Object key) {
    int h;
    //扰动函数，确保h的高位和低位都参与hash运算，减少偶发性
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

哈希散列性的体现

当length为2的幂次方时候，（length - 1） & h 即 h % length 位运算的效率高很多

 static final int indexFor(int h, int length){
           return h & (length - 1);
  }

源码分析

Java7源码分析

先决条件:

put操作:

先看上面key为空的情况(上面画图的时候总要在第一格留个空key的键值对)，执行 putForKey 方法单独处理，会把该键值对放在index0，所以HashMap中是允许key为空的情况。再看下主流程：

步骤①.根据键值算出hash值 — > hash(key)

步骤②.根据hash值和当前数组的长度计算在数组中的索引 — > indexFor(hash, table.length)

步骤③情况1.hash值和key值都相同，替换原来的值，并将被替换的值返回。

步骤③情况2.坑位没人或发生hash碰撞 — > addEntry(hash, key, value, i)

如果put的时候超过阀值，会调用 resize 方法将数组大小扩大为原来的2倍，并且根据新表的长度计算在新表中的索引(如之前17%16 =1，现在17%32=17)，看下resize方法

上面的重点是步骤②，看下它具体的转移操作

Java7 put流程图

Java8源码分析

iJava8 put的源码

扩容resize操作

可以看到，Java8把初始化数组和扩容全写在resize方法里了

JDK1.8做了哪些优化

经过观测可以发现，我们使用的是2次幂的扩展(指长度扩为原来2倍)，所以，元素的位置要么是在原位置，要么是在原位置再移动2次幂的位置。看下图可以明白这句话的意思，n为table的长度，图（a）表示扩容前的key1(5)和key2(21)两种key确定索引位置的示例，图（b）表示扩容后key1和key2两种key确定索引位置的示例，其中hash1是key1对应的哈希与高位运算结果。

图a中key1(5)和key(21)计算出来的都是5，元素在重新计算hash之后，因为n变为2倍，那么n-1的mask范围在高位多1bit(红色)，因此新的index就会发生这样的变化：

Java8 put流程图

对比总结

1.发生hash冲突时，Java7会在链表头部插入，Java8会在链表尾部插入

2.扩容后转移数据，Java7转移前后链表顺序会倒置，Java8还是保持原来的顺序

3.引入红黑树的Java8大程度得优化了HashMap的性能