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取模，取模性能不高，位运算的性能比较高

HashMap底层原理