HashMap

HashMap底层原理

jdk 7

  1. HashMap map = new HashMap();
    • 实例化以后，底层创建了长度是16的一维数组 Entry[] table。
  1. put() 方法，插入的时候，会根据 key 的hash计算一个 index 值，hash存在概率性，后面插入值得 hash 有一定概率会相同，此时两个值都占有一个位置，就会形成链表
    • 如果插入位置的数据为 Null，则在数组上插入
    • 如果插入的 key2 与 key1 哈希值不相同，则在数组上插入
    • 如果插入的 key2 与 key1 哈希值相同，则此位置形成链表，同时使用 equals 比较 key
      • 如果 equals() 返回 false，即 key 不同：此时在链表上插入（JDK 7 头插法）
      • 如果 equals() 返回 true，即 key 相同：value2 替换 value1

jdk 8与 jdk 7在底层方面的不同

  1. new HashMap()：底层没有创建一个长度为16的数组
  2. jdk 8 底层的数组是：Node[]， jdk 7 的底层数组是：Entry[]
  3. 首次调用 put() 方法时，底层创建长度为16的数组
  4. jdk 7 底层结构：数组 + 链表。jdk 8 底层结构： 数组 + 链表 + 红黑树
    • 当数组的某一个索引位置上的元素以链表形式存在的数据个数 >= 8 且 当前数组长度 > 64 时，此索引位置上的所有数组改位红黑树存储
  1. JDK 8 链表插入使用尾插法，JDK7 使用头插法

HashMap 的 put() 方法（JDK 8）

HashMap - 图1

put 扩容

JDK 8 中，HashMap 是首次进行 put() 操作后才会在底层创建一个长度为16的数组。

首先调用 putVal() 方法来实现插入

  1. public V put(K key, V value) {
  2.     // hash(key)实现了hash索引的创建
  3.     return putVal(hash(key), key, value, false, true);
  4. }

这里是定义了一个 Node 节点和一些变量，如果创建的 Node 为空，则会进行扩容机制，即 resize()

  1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
  2.                boolean evict) {
  3.     Node<K,V>[] tab; Node<K,V> p; int n, i;
  5.     // 判断Node节点是否为空，是，就进行扩容
  6.     if ((tab = table) == null || (n = tab.length) == 0)    
  7.         n = (tab = resize()).length;

resize()：扩容方法

  1. final Node<K,V>[] resize() {
  2.     Node<K,V>[] oldTab = table;
  3.     int oldCap = (oldTab == null) ? 0 : oldTab.length;
  4.     int oldThr = threshold;
  5.     int newCap, newThr = 0;
  6.     if (oldCap > 0) {
  7.         if (oldCap >= MAXIMUM_CAPACITY) {
  8.             threshold = Integer.MAX_VALUE;
  9.             return oldTab;
  10.         }
  11.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
  12.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
  13.             newThr = oldThr << 1; // double threshold
  14.     }
  15.     else if (oldThr > 0) // 初始容量被置于阈值中
  16.         newCap = oldThr;
  17.     else {               // 初始阈值为0，则使用默认值
  18.         newCap = DEFAULT_INITIAL_CAPACITY;    // 给newCap赋值默认初始容量16
  19.         // newThr是负载因子*默认初始容量=12
  20.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
  21.     }
  22.     if (newThr == 0) {
  23.         float ft = (float)newCap * loadFactor;
  24.         newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
  25.                   (int)ft : Integer.MAX_VALUE);
  26.     }
  27.     threshold = newThr;    // 扩容临界值赋值为12
  28.     @SuppressWarnings({"rawtypes","unchecked"})
  29.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];    // 创建一个底层为16的数组
  30.     table = newTab;
  32.     ...
  34.     return newTab;
  35. }

普通扩容

当 hash 桶也就是数组空间大于临界值 12 的时候，hashmap 会扩容


  • 判断是否需要扩容

    1. final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    2.   ...
    3.   ++modCount;
    4.   if (++size > threshold)    // 数组长度大于临界值
    5.       resize();
    6.   ...


  • 扩容方法

    1. final Node<K,V>[] resize() {
    2.   Node<K,V>[] oldTab = table;
    3.   int oldCap = (oldTab == null) ? 0 : oldTab.length;
    4.   int oldThr = threshold;
    5.   int newCap, newThr = 0;
    6.   if (oldCap > 0) {
    7.       if (oldCap >= MAXIMUM_CAPACITY) {
    8.           threshold = Integer.MAX_VALUE;
    9.           return oldTab;
    10.       }
    11.       else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
    12.                oldCap >= DEFAULT_INITIAL_CAPACITY)
    13.           newThr = oldThr << 1; // 扩容为原来的2倍
    14.   }