Java中HashMap详解：hash原理、扩容机制、线程不安全及源码分析 ...

前言

       HashMap 是 Java 中常用的数据结构之一，用于存储键值对。在 HashMap 中，每个键都映射到一个唯一的值，可以通过键来快速访问对应的值，算法时间复杂度可以到达 O(1)。
        HashMap 的实现原理是基于哈希表的，它的底层是一个数组，数组的每个位置可能是一个链表或红黑树，也可能只是一个键值对。当添加一个键值对时，HashMap 会根据键的哈希值计算出该键对应的数组下标（索引），然后将键值对插入到对应的位置。
        当通过键查找值时，HashMap 也会根据键的哈希值计算出数组下标，并查找对应的值。
       在现实应用中，HashMap 可以用于缓存、索引等场景。比方，可以将用户 ID 作为键，用户信息作为值，将用户信息缓存到 HashMap 中，以便快速查找。又如，可以将关键字作为键，文档 ID 列表作为值，将文档索引缓存到 HashMap 中，以便快速搜索文档。
hash原理

        来看一下 hash 方法的源码（JDK 8 中的 HashMap）：

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

复制代码

        将 key 的 hashCode 值进行处理，得到最终的哈希值。
怎么理解这句话呢？
        我们来 new 一个 HashMap，并通过 put 方法添加一个元素。

1. HashMap<String, String> map = new HashMap<>();
2. map.put("chenmo", "沉默");

复制代码

        来看一下 put 方法的源码

1. public V put(K key, V value) {
2.     return putVal(hash(key), key, value, false, true);
3. }

复制代码

hash 方法的作用
        hashMap 的底层是通过数组的情势实现的，初始巨细是 16，HashMap 在添加第一个元素的时候，需要通过键的哈希码在巨细为 16 的数组中确定一个位置（索引）
        16 个方格子（可以把它想象成一个一个桶），每个格子都有一个编号，对应巨细为 16 的数组下标（索引）

        现在，我们要把 key 为 “chenmo”，value 为“沉默”的键值对放到这 16 个格子中的一个。
怎么确定位置（索引）呢？
        通过与运算 (n - 1) & hash(现实就是对数组长度求余)，其中变量 n 为数组的长度，变量 hash 就是通过 hash() 方法计算后的结果
        chenmo”这个 key 计算后的位置（索引）是8，也就是说 map.put("chenmo", "沉默") 会把 key 为 “chenmo”，value 为“沉默”的键值对放到下标为 8 的位置上（也就是索引为 8 的桶上）

 回到 hash 方法：

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

复制代码

下面是对该方法的一些解释：

• 参数 key：需要计算哈希码的键值。
  
• key == null ? 0 : (h = key.hashCode()) ^ (h >>> 16)：这是一个三目运算符，假如键值为 null，则哈希码为 0（依旧是说假如键为 null，则存放在第一个位置）；否则，通过调用hashCode()方法获取键的哈希码，并将其与右移 16 位的哈希码进行异或运算。
  
• ^ 运算符：异或运算符是 Java 中的一种位运算符，它用于将两个数的二进制位进行比力，假如相同则为 0，差别则为 1。
  
• h >>> 16：将哈希码向右移动 16 位，相当于将原来的哈希码分成了两个 16 位的部门。
  
• 最终返回的是颠末异或运算后得到的哈希码值
  

        理论上，哈希值（哈希码）是一个 int 类型，范围从-2147483648 到 2147483648，但问题是一个 40 亿长度的数组，内存是放不下的。HashMap 扩容之前的数组初始巨细只有 16，以是这个哈希值是不能直接拿来用的，用之前要和数组的长度做与运算（前文提到的 (n - 1) & hash取余运算），用得到的值来访问数组下标才行。（当数组的长度是 2 的 n 次方，大概 n 次幂，大概 n 的整数倍时，取模运算/取余运算可以用位运算来代替，效率更高）
小结
        hash 方法的主要作用是将 key 的 hashCode 值进行处理，得到最终的哈希值。由于 key 的 hashCode 值是不确定的，可能会出现哈希辩说，因此需要将哈希值通过一定的算法映射到 HashMap 的现实存储位置上。
        hash 方法的原理是，先获取 key 对象的 hashCode 值，然后将其高位与低位进行异或操纵，得到一个新的哈希值。为什么要进行异或操纵呢？因为对于 hashCode 的高位和低位，它们的分布是比力匀称的，假如只是简朴地将它们加起来大概进行位运算，容易出现哈希辩说，而异或操纵可以克制这个问题。
        然后将新的哈希值取模（mod），得到一个现实的存储位置。这个取模操纵的目的是将哈希值映射到桶（Bucket）的索引上，桶是 HashMap 中的一个数组，每个桶中会存储着一个链表（大概红黑树），装载哈希值相同的键值对（没有相同哈希值的话就只存储一个键值对）。
        总的来说，HashMap 的 hash 方法就是将 key 对象的 hashCode 值进行处理，得到最终的哈希值，并通过一定的算法映射到现实的存储位置上。这个过程决定了 HashMap 内部键值对的查找效率。
扩容机制

        HashMap 的底层用的是数组。向 HashMap 里不停地添加元素，当数组无法装载更多元素时，就需要对数组进行扩容，以便装入更多的元素；除此之外，容量的提升也会相应地进步查询效率，因为“桶（坑）”更多了嘛，原来需要通过链表存储的（查询的时候需要遍历），扩容后可能就有本身专属的“坑位”了（直接就能查出来）。
        数组是无法自动扩容的，以是假如要扩容的话，就需要新建一个大的数组，然后把之前小的数组的元素复制过去，并且要重新计算哈希值和重新分配桶（重新散列），这个过程也是挺耗时的。
        HashMap 的扩容是通过 resize 方法来实现的，JDK 8 中融入了红黑树（链表长度超过 8 的时候，会将链表转化为红黑树来进步查询效率），以下是jdk7的方法

1. // newCapacity为新的容量
2. void resize(int newCapacity) {
3.     // 小数组，临时过度下
4.     Entry[] oldTable = table;
5.     // 扩容前的容量
6.     int oldCapacity = oldTable.length;
7.     // MAXIMUM_CAPACITY 为最大容量，2 的 30 次方 = 1<<30
8.     if (oldCapacity == MAXIMUM_CAPACITY) {
9.         // 容量调整为 Integer 的最大值 0x7fffffff（十六进制）=2 的 31 次方-1
10.         threshold = Integer.MAX_VALUE;
11.         return;
12.     }
14.     // 初始化一个新的数组（大容量）
15.     Entry[] newTable = new Entry[newCapacity];
16.     // 把小数组的元素转移到大数组中
17.     transfer(newTable, initHashSeedAsNeeded(newCapacity));
18.     // 引用新的大数组
19.     table = newTable;
20.     // 重新计算阈值
21.     threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
22. }

复制代码

        该方法吸取一个新的容量 newCapacity，然后将 HashMap 的容量扩大到 newCapacity。
        起首，方法获取当前 HashMap 的旧数组 oldTable 和旧容量 oldCapacity。假如旧容量已经到达 HashMap 支持的最大容量 MAXIMUM_CAPACITY（ 2 的 30 次方），就将新的阈值threshold 调解为 Integer.MAX_VALUE（2 的 31 次方 - 1），这是因为 HashMap 的容量不能超过 MAXIMUM_CAPACITY。
        接着，方法创建一个新的数组 newTable，并将旧数组 oldTable 中的元素转移到新数组 newTable 中。转移过程是通过调用 transfer 方法来实现的。该方法遍历旧数组中的每个桶，并将每个桶中的键值对重新计算哈希值后，将其插入到新数组对应的桶中。
        转移完成后，方法将 HashMap 内部的数组引用 table 指向新数组 newTable，并重新计算阈值 threshold。新的阈值是新容量 newCapacity 乘以负载因子 loadFactor 的结果，但假如计算结果超过了 HashMap 支持的最大容量 MAXIMUM_CAPACITY，则将阈值设置为 MAXIMUM_CAPACITY + 1，这是因为 HashMap 的元素数目不能超过 MAXIMUM_CAPACITY。
那 newCapacity 是怎样计算的呢？

1. int newCapacity = oldCapacity << 1;
2. if (newCapacity >= DEFAULT_INITIAL_CAPACITY && oldCapacity >= DEFAULT_INITIAL_CAPACITY) {
3.     if (newCapacity > MAXIMUM_CAPACITY)
4.         newCapacity = MAXIMUM_CAPACITY;
5. } else {
6.     if (newCapacity < DEFAULT_INITIAL_CAPACITY)
7.         newCapacity = DEFAULT_INITIAL_CAPACITY;
8. }

复制代码

                新容量 newCapacity 被初始化为原容量 oldCapacity 的两倍。然后，假如 newCapacity 超过了 HashMap 的容量限定 MAXIMUM_CAPACITY（2^30），就将 newCapacity 设置为 MAXIMUM_CAPACITY。假如 newCapacity 小于默认初始容量 DEFAULT_INITIAL_CAPACITY（16），就将 newCapacity 设置为 DEFAULT_INITIAL_CAPACITY。如许可以克制新容量太小或太大导致哈希辩说过多大概浪费空间。
transfer 方法
        该方法用来转移，将旧的小数组元素拷贝到新的大数组中。

1. void transfer(Entry[] newTable, boolean rehash) {
2.     // 新的容量
3.     int newCapacity = newTable.length;
4.     // 遍历小数组
5.     for (Entry<K,V> e : table) {
6.         while(null != e) {
7.             // 拉链法，相同 key 上的不同值
8.             Entry<K,V> next = e.next;
9.             // 是否需要重新计算 hash
10.             if (rehash) {
11.                 e.hash = null == e.key ? 0 : hash(e.key);
12.             }
13.             // 根据大数组的容量，和键的 hash 计算元素在数组中的下标
14.             int i = indexFor(e.hash, newCapacity);
16.             // 同一位置上的新元素被放在链表的头部
17.             e.next = newTable[i];
19.             // 放在新的数组上
20.             newTable[i] = e;
22.             // 链表上的下一个元素
23.             e = next;
24.         }
25.     }
26. }

复制代码

        该方法接受一个新的 Entry 数组 newTable 和一个布尔值 rehash 作为参数，其中 newTable 表示新的哈希表，rehash 表示是否需要重新计算键的哈希值。
        在方法中，起首获取新哈希表（数组）的长度 newCapacity，然后遍历旧哈希表中的每个 Entry。对于每个 Entry，使用拉链法将相同 key 值的差别 value 值存储在同一个链表中。假如 rehash 为 true，则需要重新计算键的哈希值，并将新的哈希值存储在 Entry 的 hash 属性中。
        接着，根据新哈希表的长度和键的哈希值，计算 Entry 在新数组中的位置 i，然后将该 Entry 添加到新数组的 i 位置上。由于新元素需要被放在链表的头部，因此将新元素的下一个元素设置为当前数组位置上的元素。
        最后，遍历完旧哈希表中的所有元素后，转移工作完成，新的哈希表 newTable 已经包罗了旧哈希表中的所有元素。
 JDK 8 的扩容源代码：

1. final Node<K,V>[] resize() {
2.     Node<K,V>[] oldTab = table; // 获取原来的数组 table
3.     int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCap
4.     int oldThr = threshold; // 获取阈值 oldThr
5.     int newCap, newThr = 0;
6.     if (oldCap > 0) { // 如果原来的数组 table 不为空
7.         if (oldCap >= MAXIMUM_CAPACITY) { // 超过最大值就不再扩充了，就只好随你碰撞去吧
8.             threshold = Integer.MAX_VALUE;
9.             return oldTab;
10.         }
11.         else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 没超过最大值，就扩充为原来的2倍
12.                  oldCap >= DEFAULT_INITIAL_CAPACITY)
13.             newThr = oldThr << 1; // double threshold
14.     }
15.     else if (oldThr > 0) // initial capacity was placed in threshold
16.         newCap = oldThr;
17.     else { // zero initial threshold signifies using defaults
18.         newCap = DEFAULT_INITIAL_CAPACITY;
19.         newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
20.     }
21.     // 计算新的 resize 上限
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; // 将新阈值赋值给成员变量 threshold
28.     @SuppressWarnings({"rawtypes","unchecked"})
29.         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新数组 newTab
30.     table = newTab; // 将新数组 newTab 赋值给成员变量 table
31.     if (oldTab != null) { // 如果旧数组 oldTab 不为空
32.         for (int j = 0; j < oldCap; ++j) { // 遍历旧数组的每个元素
33.             Node<K,V> e;
34.             if ((e = oldTab[j]) != null) { // 如果该元素不为空
35.                 oldTab[j] = null; // 将旧数组中该位置的元素置为 null，以便垃圾回收
36.                 if (e.next == null) // 如果该元素没有冲突
37.                     newTab[e.hash & (newCap - 1)] = e; // 直接将该元素放入新数组
38.                 else if (e instanceof TreeNode) // 如果该元素是树节点
39.                     ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 将该树节点分裂成两个链表
40.                 else { // 如果该元素是链表
41.                     Node<K,V> loHead = null, loTail = null; // 低位链表的头结点和尾结点
42.                     Node<K,V> hiHead = null, hiTail = null; // 高位链表的头结点和尾结点
43.                     Node<K,V> next;
44.                     do { // 遍历该链表
45.                         next = e.next;
46.                         if ((e.hash & oldCap) == 0) { // 如果该元素在低位链表中
47.                             if (loTail == null) // 如果低位链表还没有结点
48.                                 loHead = e; // 将该元素作为低位链表的头结点
49.                             else
50.                                 loTail.next = e; // 如果低位链表已经有结点，将该元素加入低位链表的尾部
51.                             loTail = e; // 更新低位链表的尾结点
52.                         }
53.                         else { // 如果该元素在高位链表中
54.                             if (hiTail == null) // 如果高位链表还没有结点
55.                                 hiHead = e; // 将该元素作为高位链表的头结点
56.                             else
57.                                 hiTail.next = e; // 如果高位链表已经有结点，将该元素加入高位链表的尾部
58.                             hiTail = e; // 更新高位链表的尾结点
59.                         }
60.                     } while ((e = next) != null); //
61.                     if (loTail != null) { // 如果低位链表不为空
62.                         loTail.next = null; // 将低位链表的尾结点指向 null，以便垃圾回收
63.                         newTab[j] = loHead; // 将低位链表作为新数组对应位置的元素
64.                     }
65.                     if (hiTail != null) { // 如果高位链表不为空
66.                         hiTail.next = null; // 将高位链表的尾结点指向 null，以便垃圾回收
67.                         newTab[j + oldCap] = hiHead; // 将高位链表作为新数组对应位置的元素
68.                     }
69.                 }
70.             }
71.         }
72.     }
73.     return newTab; // 返回新数组
74. }

复制代码

• 获取原来的数组 table、数组长度 oldCap 和阈值 oldThr。
  
• 假如原来的数组 table 不为空，则根据扩容规则计算新数组长度 newCap 和新阈值 newThr，然后将原数组中的元素复制到新数组中。
  
• 假如原来的数组 table 为空但阈值 oldThr 不为零，则说明是通过带参数构造方法创建的 HashMap，此时将阈值作为新数组长度 newCap。
  
• 假如原来的数组 table 和阈值 oldThr 都为零，则说明是通过无参数构造方法创建的 HashMap，此时将默认初始容量 DEFAULT_INITIAL_CAPACITY（16）和默认负载因子 DEFAULT_LOAD_FACTOR（0.75）计算出新数组长度 newCap 和新阈值 newThr。
  
• 计算新阈值 threshold，并将其赋值给成员变量 threshold。
  
• 创建新数组 newTab，并将其赋值给成员变量 table。
  
• 假如旧数组 oldTab 不为空，则遍历旧数组的每个元素，将其复制到新数组中。
  
• 返回新数组 newTab。
  

        在 JDK 8 的新 hash 算法下，数组扩容后的索引位置，要么就是原来的索引位置，要么就是“原索引+原来的容量”，遵循一定的规律

小结 
        当我们往 HashMap 中不停添加元素时，HashMap 会自动进行扩容操纵（条件是元素数目到达负载因子（load factor）乘以数组长度时），以包管其存储的元素数目不会超出其容量限定。
        在进行扩容操纵时，HashMap 会先将数组的长度扩大一倍，然后将原来的元素重新散列到新的数组中。
        由于元素的位置是通过 key 的 hash 和数组长度进行与运算得到的，因此在数组长度扩大后，元素的位置也会发生一些改变。一部门索引不变，另一部门索引为“原索引+旧容量”。
线程不安全

多线程下 put 会导致元素丢失
        多线程同时执行 put 操纵时，假如计算出来的索引位置是相同的，那会造成前一个 key 被后一个 key 覆盖，从而导致元素的丢失。
put 和 get 并发时会导致 get 到 null
        线程 1 执行 put 时，因为元素个数超出阈值而导致出现扩容，线程 2 此时执行 get，就有可能出现这个问题。

        因为线程 1 执行完 table = newTab 之后，线程 2 中的 table 此时也发生了变化，此时去 get 的时候当然会 get 到 null 了，因为元素还没有转移。
小结
        HashMap 是线程不安全的主要是因为它在进行插入、删除和扩容等操纵时可能会导致链表的结构发生变化，从而破坏了 HashMap 的不变性。具体来说，假如在一个线程正在遍历 HashMap 的链表时，另外一个线程对该链表进行了修改（比如添加了一个节点），那么就会导致链表的结构发生变化，从而破坏了当火线程正在进行的遍历操纵，可能导致遍历失败大概出现死循环等问题。
        为了解决这个问题，Java 提供了线程安全的 HashMap 实现类ConcurrentHashMap 。ConcurrentHashMap 内部接纳了分段锁（Segment），将整个 Map 拆分为多个小的 HashMap，每个小的 HashMap 都有本身的锁，差别的线程可以同时访问差别的小 Map，从而实现了线程安全。在进行插入、删除和扩容等操纵时，只需要锁住当前小 Map，不会对整个 Map 进行锁定，进步了并发访问的效率


免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。