Java 集合 - HashMap 详解 - 《Blog》

概述
- 底层结构
重要成员变量
主要方法实现
一些问题

概述

HashMap继承自AbstractMap，并且实现了Cloneable、Serializable接口

底层结构

JDK 1.7：数组 + 链表
JDK 1.8：数组 + 链表 / 红黑树
重要成员变量

loadFactor（负载因子）：默认为 0.75 f，表示HashMap中存储的键值对个数达到容量的 0.75 时就需要进行扩容
size：HashMap中当前存储的节点数（键值对个数，元素个数）
capacity：初始化时默认为 16，表示HashMap的容量（_MAXIMUM_CAPACITY _= 1 << 30）
threshold：门限，threshold = capacity * loadFactor，当size达到门限大小就需要进行扩容
Node<K, V>：Node 节点，实现了Map.Entry<K,V>。键值对就是以Node节点的方式存储在HashMap中的，Node节点中包含了key、value、hash值、next指针

主要方法实现

hash 方法（扰动函数）

为什么需要使用扰动函数呢
虽然已经通过 hashCode 方法算出 hashCode 值了，但是如果只有低位参与之后的对数组长度的取余运算，那么哈希碰撞的概率还是非常大的，所以通过扰动函数让高位也参与运算，这样能让哈希分布得更均匀，减少哈希冲突

JDK 1.7
经过了四次右移
```
static int hash(int h) {
 // >>> ：无符号右移，忽略符号位，空位都以0补齐
 h ^= (h >>> 20) ^ (h >>> 12);
 return h ^ (h >>> 7) ^ (h >>> 4);
}
```
JDK 1.8
通过key.hashCode()计算出 hashCode 值，然后对 hashCode 右移 16 位，再与原 hashCode 异或计算出最终的 hash 值
右移 16 位的原因：16 位正好为 32 位的一半，让高半区和低半区按位异或，这样能更好的地让高位参与运算，增大低位的随机性
```
static final int hash(Object key) {
 int h;
 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
put 方法

JDK 1.7
put()添加元素的过程如下：
先得到 key 的 hashCode 值，然后再通过hash()，得到 hash 值
检查散列数组是否为空，如果为空，则初始化数组

计算出元素要存放的位置，遍历链表，判断节点的 key 和 hash 值是够与要插入的节点相同，如果相同就直接覆盖，如果都不相同，那么就用 头插法 插入链表

public V put(K key, V value)
 if (table == EMPTY_TABLE) {
     inflateTable(threshold);
 }
 if (key == null)
     return putForNullKey(value);
 int hash = hash(key);
 int i = indexFor(hash, table.length);
 for (Entry<K,V> e = table[i]; e != null; e = e.next) { // 先遍历
     Object k;
     if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
         V oldValue = e.value;
         e.value = value;
         e.recordAccess(this);
         return oldValue;
     }
 }
 modCount++;
 addEntry(hash, key, value, i);  // 再插入
 return null;
}

`JDK 1.8`

put()内部实际调用的是putVal()
put()添加元素的过程如下：

通过hash()，先得到 key 的 hashCode 值，然后再将 hashCode 值右移 16 位并与原 hashCode 值按位异或，得到 hash 值
检查散列数组是否为空，如果为空，则初始化数组，数组容量将被初始化为 16（默认初始容量）
通过(n - 1) & hash计算出元素要存放的位置，判断当前位置是否为空，如果为空，就直接将新节点插入
如果不为空，就比较当前位置链表的头节点的 hash 和 key 是否与要插入的节点相同，如果相同，则直接覆盖，如果不相同，就判断头节点是否为树节点
如果为树节点，则调用putTreeVal()，按照红黑树的逻辑来插入；如果不是树节点，那么就遍历链表，判断节点的 key 和 hash 值是够与要插入的节点相同，如果相同就直接覆盖，如果都不相同，那么就插入链表的尾部
如果节点作为新节点插入，就要判断当前链表的节点数是否大于等于阈值TREEIFY_THRESHOLD（默认为 8），如果大于等于，那么就调用treeifyBin()，这个方法会判断数组大小是否>=64，如果>=，那么就将链表转换成红黑树，如果小于 64，那么就先进行扩容
最后判断 size 是否大于 threshold，如果大于的话，那么就进行扩容
```
public V put(K key, V value) {
 return putVal(hash(key), key, value, false, true);
}
```
```java /**

Implements Map.put and related methods. *
@param hash hash for key
@param key the key
@param value the value to put
@param onlyIfAbsent if true, don’t change existing value
@param evict if false, the table is in creation mode.

@return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent,

         boolean evict) {

Node[] tab; Node p; int n, i; 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);
              if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                  treeifyBin(tab, hash);
              break;
          }
          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; } ```

为什么`JDK 1.7及之前`都采用头插法插入链表呢

采用头插法是由于计算机的局部性原理，一个最近被访问过的对象很有可能很快再被访问到，基于这一层时间局部性，选择插入链表的头部可以有效的提高查询效率

get 方法（`JDK 1.8`）

get(Object key)内部实际调用的是getNode(int hash, Object key)

先通过(n - 1) & hash计算出要查找的元素存放的位置
判断存放的位置的第一个节点与要查找的元素的 key 和 hash 值是否相同，如果相同，则返回这个节点
如果不同且桶中不止一个节点，那么就判断第一个节点是否为树节点，如果为树节点，就调用getTreeNode()在树中查找，如果不是树节点，就遍历链表，查找是否有链表节点的 key 和 hash 值与要查找的元素相同，如果有，则直接返回，如果没有，就返回null
resize 方法（JDK 1.8）
如果 map 的 size > threshold 时，就会进行扩容
HashMap 的默认初始容量是 16，并且每次扩容会将原数组长度 2 扩容时将容量 2 的原因

让 HashMap 的长度保持为 2 的幂次方，这样就可以用与运算的方式进行取余运算，效率更高
在扩容移动链表节点时，节点在新数组中的位置只可能是原位置 i 或 i + oldCap，扩容时效率更高

扩容的大致过程：

先对旧容量和旧门限进行判断
创建新的散列数组，并将旧的散列数组中的链表的头节点拷贝至新数组中，在移动时，将节点的 hash 与 oldCap 进行 与运算 ，若结果为 0，表示在新数组中位置不变，若不为 0，表示在新数组中位置为 i + oldCap

在移动节点时，会使用loHead、loTail分别指向新数组位置 i 的链表（低位链表）的头尾节点，用hiHead、hiTail分别指向新数组中位置 i + oldCap 的链表（高位链表）的头尾节点，用一个 next 指针指向当前正在移动节点的下一个节点

final Node<K,V>[] resize() {
 Node<K,V>[] oldTab = table;
 int oldCap = (oldTab == null) ? 0 : oldTab.length;
 int oldThr = threshold;
 int newCap, newThr = 0;
 if (oldCap > 0) {
     if (oldCap >= MAXIMUM_CAPACITY) {
         threshold = Integer.MAX_VALUE;
         return oldTab;
     }
     else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
              oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // double threshold
 }
 else if (oldThr > 0) // initial capacity was placed in threshold
     newCap = oldThr;
 else {               // zero initial threshold signifies using defaults
     newCap = DEFAULT_INITIAL_CAPACITY;
     newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
 }
 if (newThr == 0) {
     float ft = (float)newCap * loadFactor;
     newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
               (int)ft : Integer.MAX_VALUE);
 }
 threshold = newThr;
 @SuppressWarnings({"rawtypes","unchecked"})
 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
 table = newTab;
 if (oldTab != null) {
     for (int j = 0; j < oldCap; ++j) {
         Node<K,V> e;
         if ((e = oldTab[j]) != null) {
             oldTab[j] = null;
             if (e.next == null)
                 newTab[e.hash & (newCap - 1)] = e;
             else if (e instanceof TreeNode)
                 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
             else { // preserve order
                 Node<K,V> loHead = null, loTail = null;
                 Node<K,V> hiHead = null, hiTail = null;
                 Node<K,V> next;
                 do {
                     next = e.next;
                     if ((e.hash & oldCap) == 0) {
                         if (loTail == null)
                             loHead = e;
                         else
                             loTail.next = e;
                         loTail = e;
                     }
                     else {
                         if (hiTail == null)
                             hiHead = e;
                         else
                             hiTail.next = e;
                         hiTail = e;
                     }
                 } while ((e = next) != null);
                 if (loTail != null) {
                     loTail.next = null;
                     newTab[j] = loHead;
                 }
                 if (hiTail != null) {
                     hiTail.next = null;
                     newTab[j + oldCap] = hiHead;
                 }
             }
         }
     }
 }
 return newTab;
}

一些问题

1. 为什么 HashMap 的长度为 2 的幂次方

为了让哈希分布得均匀点，hash 值的范围非常大（-2147483648 ~ 2147483647），内存中是无法放入如此大的数组的，所以需要将 hash 值对数组大小进行取余运算：hash % n，当除数为 2 的幂次方时，hash % n=hash & (n - 1)，与运算的效率比取余运算高，所以就让 HashMap 的长度保持为 2 的幂次方

2. 为什么 HashMap 线程不安全

在多线程操作情况下，JDK 1.7 及之前会出现扩容死链（死循环）、数据丢失问题，而JDK 1.8中虽然解决了死循环问题，但仍然还是存在数据丢失、数据覆盖问题

扩容死链（死循环）问题

```java void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; //如果当前的容量已经达到允许的容量最大值（1 << 30），则将负载门槛设置为Integer.MAX_VALUE，并且不再进行扩容 if (oldCapacity == MAXIMUM_CAPACITY) {

 threshold = Integer.MAX_VALUE;
 return;

} Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }

void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry e : table) { while(null != e) { Entry next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; } } } `` ![](https://cdn.nlark.com/yuque/0/2022/jpeg/22396700/1654572857654-809c30cb-a551-4b35-84ad-62874f0cc2b4.jpeg) 在多线程操作的情况下，假设线程1执行到 transfer 方法中newTable[i] = e这一句时，被挂起了，那么对于线程1来说，e 指向[3, A]，next 指向[7, B] 接着线程2完成了正常的扩容流程，如上图扩容后的结果，[7, B]的 next 指针指向[3, A] 然后线程1继续执行扩容，过程如下： ![](https://cdn.nlark.com/yuque/0/2022/jpeg/22396700/1654581820591-138427fc-ae89-4c14-bbf9-81ca2f613289.jpeg) JDK 1.8`解决扩容死链问题的方法：尾插法及高低位链表法
尾插法保证了节点指针的顺序与原来相同，高低位链表法让扩容过程不再是一边遍历一边插入，而是先将一条链表分成高位链表和低位链表，然后将这两条链表分别插入 i + oldCap 和 i 的位置

数据丢失、数据覆盖问题

线程1在执行put()时，当执行到下面红框的语句时，判断当前位置没有节点，也就是没有哈希冲突，判断完之后就被挂起了，这时线程2也在添加新元素，并且通过计算得出的存放位置一模一样，于是线程2就在同样的位置添加了新元素，等到后面线程1再执行的时候，由于之前已经判断过了，所以就会直接在同样的位置添加元素，导致线程2添加的元素被覆盖了

当线程1在执行put()添加新元素时，由于链表的节点个数达到了阈值，所以触发了扩容，与此同时，线程2也在添加新元素，也触发了扩容，这时线程1和线程2都分别创建了一个扩容后的新数组，线程1先将旧数组替换成新数组，线程2随后又用新数组替换了旧数组，这样就会导致线程1之前添加的新元素丢失，被覆盖了
由于size等变量并没有被volatile修饰，所以在进行++size操作时，线程用的可能还是自己本地的变量，就会导致两个线程同时进行++size操作，最后size的值只增加了 1
3. 什么时候链表会转化成红黑树，什么时候红黑树会转化成链表
默认当链表长度达到_TREEIFY_THRESHOLD _= 8的时候会转化成红黑树，当红黑树节点数 <= _UNTREEIFY_THRESHOLD _= 6 时会转化为链表

转化成红黑树是为了提高查询效率
退化成链表是由于红黑树的每个节点大小大约是正常节点的 2 倍，占用空间大，并且插入和删除节点时维护红黑树的平衡性需要额外的开销

红黑树的特点

每个节点不是黑色就是红色，根节点是黑色
红色节点的子节点必须是黑色
从一个节点到每一个子孙节点的路径上的黑色节点数必须相同

Blog

HashMap 详解

概述

底层结构

重要成员变量

主要方法实现

hash 方法（扰动函数）

为什么需要使用扰动函数呢

`JDK 1.7`

`JDK 1.8`

put 方法

`JDK 1.7`

`JDK 1.8`

为什么`JDK 1.7及之前`都采用头插法插入链表呢

get 方法（`JDK 1.8`）

resize 方法（`JDK 1.8`）

一些问题

1. 为什么 HashMap 的长度为 2 的幂次方

2. 为什么 HashMap 线程不安全

扩容死链（死循环）问题

数据丢失、数据覆盖问题

3. 什么时候链表会转化成红黑树，什么时候红黑树会转化成链表

HashMap 详解

概述

底层结构

重要成员变量

主要方法实现

hash 方法（扰动函数）

为什么需要使用扰动函数呢

JDK 1.7

JDK 1.8

put 方法

JDK 1.7

JDK 1.8

为什么JDK 1.7及之前都采用头插法插入链表呢

get 方法（JDK 1.8）

resize 方法（JDK 1.8）

一些问题

1. 为什么 HashMap 的长度为 2 的幂次方

2. 为什么 HashMap 线程不安全

扩容死链（死循环）问题

数据丢失、数据覆盖问题

3. 什么时候链表会转化成红黑树，什么时候红黑树会转化成链表

`JDK 1.7`

`JDK 1.8`

`JDK 1.7`

`JDK 1.8`

为什么`JDK 1.7及之前`都采用头插法插入链表呢

get 方法（`JDK 1.8`）

resize 方法（`JDK 1.8`）