HashMap那些事儿

HashMap 在 Java 中是一个使用高频的数据结构，JDK1.8 以后 HashMap 进行了一次翻天覆地的改变。

本文基于 JDK1.8 分析一下 HashMap

存储结构转换

在 JDK1.8 以前 HashMap 采用的是数组+链表的结构，JDK1.8 以后又引入了红黑树的结构，会在链接和红黑树之间转换，结合源码分析一下 HashMap 对数组+链表和数组+红黑树的转换
首先看一下数据的存储结构

1	transient HashMap.Node<K, V>[] table;

HashMap 定义了一个 Node 的数组，Node 的定义

 static class Node<K, V> implements Entry<K, V> {
      final int hash;
      final K key;
      V value;
      HashMap.Node<K, V> next;
      // ....省略
}

Node 中包含了四个属性hash、key、value、next。

key、value是调用 HashMap 的put()方法传进来的。
hash 是判断 key 是否重复的关键
next 用于构建链表

所以 HashMap 默认是一个数组+链表的形式

list

链表是否要转换成红黑树，是在调用put()方法添加数据时判断的，跟着源码分析链表转换成红黑树的过程

put()方法调用的是putVal()方法，

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // ...省略
    while (true) {
        if ((e = ((HashMap.Node) p).next) == null) {
            ((HashMap.Node) p).next = this.newNode(hash, key, value,(HashMap.Node) null);
            //转换成红黑树
            if (binCount >= TREEIFY_THRESHOLD - 1) {
                this.treeifyBin(tab, hash);
            }
            break;
        }
        if ((((HashMap.Node) e).hash == hash) &&
                (((k = ((HashMap.Node) e).key) == key) ||
                ((key != null) && key.equals(k)))) {
            break;
        }
        p = e;
        ++binCount;
    }
    // ...省略
}

无关的部分省略了，while 循环中遍历链表中的数量，如果数量大于等于 8，调用treeifyBin()方法，
在treeifyBin()中有一行

1	hd.treeify(tab);

treeify()方法会将链表转换为红黑树。同时会将链表中所有节点由Node结构转换为TreeNode结构。

TreeNode继承自java.util.LinkedHashMap.Entry，java.util.LinkedHashMap.Entry又继承自Node

那么Node就是TreeNode的父类，所以这样转换是不会有问题的。

经过treeifyBin()后存储结构变为
tree

put 方法的具体逻辑

put方法中可以划分为 4 个部分，看一下方法的执行流程图。
put

结合一下源码
put-source

结合流程图和源码，对 put 的过程做一个描述
①：判断 tab 是否为空，如果为空说明 table 还未初始化，先对数组进行初始化
②：先计算在数组中的位置，并判断该位置是否为空，如果为空，则直接赋值。然后跳转到⑥
③: 判断节点 key 是否存在，如果存在直接额赋值，不存在则执行 ④
④：判断是否是红黑树，如果是则添加到树中，否则进入到⑤
⑤：为链表的情况，判断长度是否大于等于TREEIFY_THRESHOLD - 1，如果是，先将链表转花为红黑树，然后添加到树中。如果不是直接添加到列表中。
⑥：插入成功后，判断实际存在的键值对数量size是否超多了最大容量threshold，如果超过，进行扩容。

扩容

当 HashMap 键值对大于阀值时或者初始化时，会进行扩容。
阀值是threshold的值，是由数组的长度和loadFactor(默认值是0.75)决定的，threshold = length * loadFactor

HashMap 的扩容是在resize()方法里进行的，结合源码分析一下 HashMap 是怎么扩容的，因为 JDk1.8 引入了红黑数，所以代码比较长，就不贴全部的代码了，主要分析一下关键步骤。
先看一下初始化的几个变量

int oldCap = (oldTab == null) ? 0 : oldTab.length; //现在容器的大小
int oldThr = threshold; 现在的阀值
 int newCap  //计算过后，新的容器的大小
     , newThr = 0; //计算后阀值的大小

注意：扩容不只是改变容器的大小，还要改变阀值的大小

1. table 容器不为空的情况

if (oldCap > 0) {
   if (oldCap >=  MAXIMUM_CAPACITY) {
        this.threshold = Integer.MAX_VALUE;
        return oldTab;
   }

   else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
               newThr = oldThr << 1;
}

数量已经大于最大的容量，则将阀值设置为整数最大值，不再扩容
newCap = oldCap << 1 扩容后仍然小于最大容量并且 oldCap 大于默认值 16，双倍扩容阀值 threshold

2. 旧的容量为 0，但 threshold 大于零

1 2	else if (oldThr > 0) newCap = oldThr;

出现这种情况说明有参构造有 initialCapacity 传入，那么 threshold 已经被初始化成最小 2 的 n 次幂，所以直接将该值赋给新的容量

3. 旧的容量为 0，threshold 也等于 0

else {
     newCap = DEFAULT_INITIAL_CAPACITY;
     newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }

这种情况说明是通过无参构造函数创建的，也就是Map map = new HashMap()这种格式，那么都被赋予默认的大小（默认 16）和默认的阈值（默认 16 * 0.75）

4、计算新的阈值

 if (newThr == 0) {
    float ft = (float)newCap * loadFactor;
    newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                      (int)ft : Integer.MAX_VALUE);
}

这种情况说明是在有参构造时，默认的loadFactor被重新赋值，如果loadFactor大于 1，那么阈值会比容量大，有可能会超出最大容量，所以要重新计算。
还有一种情况在第一步中newThr = oldThr << 1，左移超出范围后会置0，也要重新计算。

扩容也就这些了，剩下的代码是扩容后，元素重新排列的逻辑了。

注意：扩容的大小（newCap = oldCap << 1） << 相当于乘2,所以HashMap的容量总是2的n次方

确定key在数组中的位置

在调用put()方法添加新数据时，在put()方法内部，调用hash()操作key，得到一个hash值
hash

在putVal()方法中，在第②步的时候确定key在数组中的位置

index

hash()方法的实现

static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

在key等于null的情况下，会直接放到0处，不为null时，获取key的hashCode后，将hashCode的高16位和低16位进行异或。

获取位置的整个过程有两个问题：

(n - 1) & hash 是怎么获取到位置的？
n是table数组的长度，而数据的长度又总是2的n次方，所以(n - 1) & hash正好是对n取模。
( (n - 1) & hash) ) == (hash % n), 这是一个非常巧妙的设计，用&比%具有更高的效率。
将hashCode的高16位和低16位进行异或的作用是什么？
hashCode是一个int类型的数据，占4个字节 32位，而在HashMap中默认的长度是DEFAULT_INITIAL_CAPACITY = 1 << 4（即2的四次方16），要远小于int类型的范围，如果直接用hashCode进行运算，那么hashCode的高位部分对结果来说不会起太大作用，这样会增加hash碰撞的概率。所以用高16位和低16位进行异或来降低hash冲突的概率

使用任意类作为key的情况

HashMap判断key的位置是基于hashCode，如果要使用任意类作为key，必须要考虑是否要重写hashCode方法。默认的hashCode返回对象的是对象地址，直接使用使用可能会有问题。用伪代码举个例子

public class User{
  private String name;
  private int age;
  
  // ...省略get set方法
}
  
  User user1 = new User();
  user1.setName("张三");
  user1.setAge("20");
  
  
  User user2 = new User();
  user2.setName("张三");
  user3.setAge("20");

  Map<User,Stirng> map = new HashMap<>();
  map.put(user1,"张三");
  map.put(user2,"张三");

这种情况下尽管user1和user2的属性都相同，但是user2并不会覆盖user1,因为user1和user2是两个对象，地址不相同，hashCode也不相同。

注意：重写hashCode()方法时，要注意equals() 和 hashCode() 相关的规则

为什么String、Integer等包装类可以作为key

String、Integer内部已重写了equals()、hashCode()等方法。
都是final类型，保证了不可更改性，不会存在获取hash值不同的情况

线程安全问题

在put第①步

1 2	if ((tab = table) == null \|\| (n = tab.length) == 0) n = (tab = resize()).length;

当第一个线程运行到这后已经拿到了数组数据和长度，如果这时让出CPU，而第二个线程进来后把数组数据改变了，那么当第一线程再次拿到CPU后，继续运行的话，会把第二个线程的数据覆盖掉，造成数据丢失。
在put第⑥步

1 2	if (++size > threshold) resize();

++size并不是原子操作，当多个线程都执行这行代码时，会存在丢失数据的情况。

来个例子验证一下：

public class HashMapTreadTest extends Thread{

    private  static Map<Integer,Integer> map = new HashMap<>();
    private static AtomicInteger mapSize = new AtomicInteger();

    @Override
    public void run() {
        while (mapSize.get() < 10000){
            map.put(mapSize.get(),map.get(mapSize));
            mapSize.incrementAndGet();
        }
    }

    public static void main(String[] args) {
        HashThreadTest hashThreadTest = new HashThreadTest();
        Thread[] threads=new Thread[5];
        for (int i = 0; i < 5; i++) {
            threads[i]=new Thread(hashThreadTest,"线程"+i);
            threads[i].start();
        }
        //默认还有个守护线程
        while (Thread.activeCount() > 2) {
            Thread.yield();
        }
        System.out.println("map的数量 = "+ hashThreadTest.map.size());
    }
}