概述

特点

• 键值对存储：HashMap 是基于键值对（Key-Value）存储的数据结构，每个元素都是由键和值组成的一对数据

• 无序：HashMap 中的元素是无序排列的，即元素的存储顺序和插入顺序无关。因此，在遍历 HashMap 时无法保证元素的顺序，如果需要有序性，可以考虑使用 LinkedHashMap

• 哈希表实现：HashMap 内部通常采用哈希表来实现。哈希表通过哈希函数将键映射到存储桶中，从而实现了快速的查找、插入和删除操作。在理想情况下，哈希表可以提供常量时间复杂度的性能，使得 HashMap 在大多数情况下具有高效的操作速度。

  • JDK1.8 之前的数据结构是：链表+数组，JDK 1.8 后是链表+数组+红黑树

  • 当链表长度大于 8 时，才会将链表转化为红黑树，变为红黑树的目的是为了高效的查询

  • 当链表的长度等于大于 8，但是数组的长度小于 64 的时候，此时会选择对数组进行扩容而不是将链表转化为红黑树，这是因为在数据量比较小的情况下，使用红黑树反而会降低查询效率。

• 允许存储 null 键和 null 值：HashMap 允许存储 null 键和 null 值，因此在某些情况下可以简化代码逻辑。但是需要注意的是，由于键的唯一性，如果同时存储了多个 null 键，则只会保留一个。

• 非线程安全：HashMap 是非线程安全的，如果在多线程环境下使用，需要额外的同步措施来确保线程安全性，或者考虑使用 ConcurrentHashMap。

优点

1. 快速的查找操作：由于 HashMap 内部采用哈希表实现，可以在接近常量时间复杂度内进行查找操作，使得查找元素非常高效。
2. 高效的插入和删除操作：HashMap 也能够在接近常量时间复杂度内执行插入和删除操作，这使得对数据的动态修改非常高效。
3. 灵活性：HashMap 允许存储不同类型的数据作为键和值，提供了灵活的数据存储和检索方式。
4. 允许存储 null 键和 null 值：HashMap 允许存储 null 键和 null 值，简化了部分情况下的编程逻辑。

缺点

1. 不保证顺序：HashMap 中的元素是无序排列的，无法保证元素的插入顺序或访问顺序，这在某些场景下可能会造成不便。
2. 空间开销较大：由于哈希表需要维护一定数量的桶和哈希冲突处理机制，因此在存储大量元素时可能会占用较多的内存空间。
3. 线程不安全：HashMap 是非线程安全的，如果在多线程环境下使用，需要额外的同步措施来确保线程安全，或者考虑使用 ConcurrentHashMap。
4. 哈希冲突：即使哈希函数设计良好，仍然可能发生哈希冲突，需要额外的处理机制来解决冲突，影响了部分操作的效率。

看看 HashMap 源码

常用常量和变量

常用常量

//1.序列化版本号常量：
private static final long serialVersionUID = 362498820763181265L;

//2.集合的初始化容量（必须是2的n次幂）：16
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

//3.负载因子常量：0.75
static final float DEFAULT_LOAD_FACTOR = 0.75f;

//注意：当HashMap中元素数超过 容量*加载因子时，HashMap会进行扩容

//4.链表转红黑树时最小链表长度常量：
static final int TREEIFY_THRESHOLD = 8;

//5.链表转红黑树时最小数组长度常量：
static final int MIN_TREEIFY_CAPACITY = 64;

//6.红黑树转为链表的最小数组长度常量
static final int UNTREEIFY_THRESHOLD = 6;

//7.数组阈值（调整下一次扩容的容量值）（容量 * 负载因子）
int threshold;

常用变量

//8.负载因子变量：
final float loadFactor;

//9.存储元素的数组：
transient Node<K,V>[] table;

//10.存放具体元素的集合：
transient Set<Map.Entry<K,V>> entrySet;

//11.实际存储元素的个数：
transient int size;

//12. 记录HashMap的修改次数：
transient int modCount;

存储过程

在 JDK1.8 之前，HashMap 由 数组+链表 数据结构组成。

在 JDK1.8 以后，HashMap 由 数组+链表+红黑树 数据结构组成。

而本文我们只讲讲解基于 数组+链表+红黑树 的 HashMap。我们接下来用一个实例来讲解 HashMap 的存储过程。

public class Demo01 {
    public static void main(String[] args) {


        HashMap hashMap = new HashMap<String, Integer>();
        hashMap.put("a", 1);
        hashMap.put("b", 2);
        hashMap.put("c", 3);

        System.out.println(hashMap);
    }
}

当我们执行存储操作的时候，会发生如下操作：

1. 计算哈希值：当调用 put 方法时，HashMap 会将传入的 key 通过哈希函数（hash function）转换为一个整数，这个整数被称为哈希值。
2. 计算数组索引：HashMap 使用哈希值对数组的长度进行取模运算，得到一个数组索引（即数组的位置），用于确定键值对在数组中的存储位置。
3. 存储链表或红黑树：如果该位置上已经有其他键值对存在，那么新的键值对将会以链表或红黑树的形式插入到该位置的末尾或中间。如果该位置还没有任何键值对，那么直接将键值对存储到该位置。

需要注意的是：

在 JDK8 之前，HashMap 的构造方法就会帮我们创建一个 长度为 16的Entry[] table 用来存储键值数据。

在 JDK8 以后就不是在 HashMap 的构造方法底层来创建数组了，而是在第一次调用 put 方法的时候创建一个 **Node[] table** 来存储键值对数据。

过程

下面将通过源码解读 HashMap 的插入过程：

	//进入put方法
	public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

• hash 方法：计算 key 的 hash 值，相对于直接使用 hashCode()方法的好处在于，可以减少哈希冲突的概率

  将键的哈希值右移 16 位，并与原哈希值进行异或运算，以增加哈希值高位的随机性

  通过将二进制位的高位和低位都参与到哈希值的计算中，可以更好地保持哈希值的随机性和分布性，从而减少不同键的哈希冲突，提高 HashMap 的性能。

• 并且通过这个方法我们也可以看出：HashMap 的 Key 是可以为 null 的。当 Key 为 null 的时候，将位置 0 作为键值对的插入位置。

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

• 计算 hash 值后，进入 putVal 方法

  //进入putVal方法
  final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                 boolean evict) {
      Node<K,V>[] tab; Node<K,V> 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;
  }

哈希表为空

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

• 首先，代码将 table 赋值给变量 tab，并进行判空操作。如果 table 为空，则说明哈希表尚未初始化，此时将 n 设为 0。
• 如果 table 不为空，则 将 table 的长度赋值给变量 n。
• 接下来，通过条件运算符判断 n 是否为 0，如果是 0，则表明哈希表的长度为 0，需要进行扩容操作。在这种情况下，代码会调用 resize()方法进行哈希表的扩容，并将扩容后的哈希表赋值给 tab，并将扩容后的哈希表的长度赋值给 n。
• 最后，返回 n 作为哈希表的长度

总的来说，这段代码的作用是获取哈希表的长度，并在哈希表为 null 或者为空的时候，执行扩容操作 通过检查哈希表的长度是否为 0，可以判断哈希表是否需要进行初始化或者扩容，从而保证 HashMap 的正常使用和性能优化。

找到数组位置

if ((p = tab[i = (n - 1) & hash]) == null)
    tab[i] = newNode(hash, key, value, null);

• 注意：在 n 为 2 的 n 次方的前提条件下，hash%n 等价于(n-1)&hash，后者是是位运算，相对于符号运算，效率更高
• 步骤：
  • 首先，代码计算出要插入的位置 i，通过对 hash 值进行(n-1) & hash 的位与运算得到。这里的 n 是哈希表的长度，通常是 2 的幂，通过这个位与运算可以将 hash 值限定在 0 到 n-1 之间，确保落在哈希表范围内。
  • 然后，代码判断 tab[i]位置是否为空，即当前位置是否已经存在节点。如果为空，则将新节点插入到这个位置。
  • 如果 tab[i]位置不为空，则说明当前位置已经存在节点。这里可能会涉及到链表或者红黑树等数据结构，用于处理哈希冲突的情况，但在这段代码中没有展现出来。

总的来说，这段代码的作用是 根据 hash 值找到对应的位置，然后判断该位置是否已经存在节点，如果不存在则直接插入新节点，如果存在则根据具体的情况进行相应的处理，以保证 HashMap 中的键值对能够正确存储和检索。

数组该位置不为空处理情况

数组该位置不为空处理情况，判断 key 是否相同、判断是否为红黑树、按照链表插入

• 首先，代码定义了一个 Node 和一个 K 类型的变量 k。然后通过一系列的条件判断来确定如何处理哈希冲突:
  • 首先，判断当前节点 p 的哈希值和键与要插入的哈希值和键是否相等，如果相等，则将当前节点 p 赋值给 e。（即说明键是相同的，更新值即可，这里直接覆盖节点）
  • 如果不相等，且当前节点 p 是 TreeNode 类型，则调用 TreeNode 的 putTreeVal 方法来处理插入。
  • 如果以上两个条件都不满足，则通过遍历链表的方式找到合适的位置插入新节点，同时处理可能出现的树化操作。

总的来说，****这段代码的作用是处理哈希冲突的情况，具体处理方式取决于当前节点的类型以及与要插入节点的哈希值和键的比较结果。****通过合适的处理方式，保证 HashMap 在处理哈希冲突时能够正确地插入新节点，并维护数据结构的完整性。

key 已存在，更新值

• 首先，将已存在节点 e 的值赋给 oldValue，以便在后面返回旧的值。

• 然后会根据 onlyIfAbsent 的取值来判断是否需要覆盖已存在节点 e 的值：

  • 如果 onlyIfAbsent 为 false，或者 oldValue 为 null（即允许替换已有的空值），则将新值 value 赋给节点 e 的值 e.value。

• 接着调用 afterNodeAccess(e)方法来进行相关操作，比如 LinkedHashMap 中重写的方法会将节点移动到链表末尾，以实现 LRU 策略。

• 最后返回旧的值 oldValue，表示已存在键对应的旧值。

• 总的来说，这段代码的作用是在 HashMap 中处理键已存在的情况，根据需要更新节点的值，并在操作后返回旧的值。

判断是否需要扩容

++modCount;
if (++size > threshold)
    resize();
afterNodeInsertion(evict);
return null;

• 首先，对 modCount 进行自增操作，用于在并发情况下对 HashMap 的修改进行控制。
• 然后对 size 进行自增操作，表示当前 HashMap 中键值对的数量增加了 1。接着会检查 size 是否超过了阈值 threshold，如果超过了则需要进行哈希表的扩容操作。
• 如果 size 超过了 threshold，就调用 resize 方法对哈希表进行扩容。哈希表的扩容会重新计算每个键值对的位置，以降低哈希冲突的概率。
• 接着调用 afterNodeInsertion(evict)方法来进行相关操作，其中 evict 参数表示是否需要进行 LRU 策略的节点移除操作。
• 最后返回 null，表示插入操作完成并且不需要返回任何值。

总的来说，这段代码的作用是在 HashMap 中处理插入新节点后更新相关计数器、进行哈希表的扩容操作，并在操作后进行相关处理

小结

其实整个 put 操作的代码逻辑链其实是比较清晰的，我们可以用图表示为：

扩容过程

条件

• 满足以下两个条件，其中一种就可以

1. 当前存储的数量大于等于阈值
2. 当某个链表长度>=8，但是数组存储的结点数 size() < 64 时

特点

先插后判断是否需要扩容（扩容时是尾插法）

缺点

缺点：多线程下，1.8 会有数据覆盖

举例：

• 线程 A：往 index 插，index 此时为空，可以插入，但是此时线程 A 被挂起
• 线程 B：此时，对 index 写入数据，A 恢复后，就把 B 数据覆盖了

扩容之后对 table 的调整

table 容量变为 2 倍，但是不需要像之前一样计算下标，只需要将 hash 值和旧数组长度相与即可确定位置。

1. 如果 Node 桶的数据结构是链表会生成 low 和 high 两条链表，是红黑树则生成 low 和 high 两颗红黑树

2. 依靠 (hash & oldCap) == 0 判断 Node 中的每个结点归属于 low 还是 high。（若为零，则属于 low，若不为零，则属于 high）

   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;
   }

3. 把 low 插入到 新数组中 当前数组下标的位置，把 high 链表插入到 新数组中 [当前数组下标 + 旧数组长度] 的位置

4. 如果生成的 low，high 树中元素个数小于等于 6 退化成链表再插入到新数组的相应下标的位置

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;
}

数组下标位置的确定原因

• 通过 e.hash&oldCap 确定该结点是属于 low 还是 high

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;
}

• 若为 low，则插入到数组原来的位置；若为 high，则插入到（数组原来的位置+原来数组的容量）的位置上

if (loTail != null) {
    loTail.next = null;
    newTab[j] = loHead;
}
if (hiTail != null) {
    hiTail.next = null;
    newTab[j + oldCap] = hiHead;
}

• 通过（hash&oldCap）即可算出扩容后元素在数组下标的位置的原因，请看以下照片举例：（ps，纯用笔手写，后拍照扫描，太久没拿笔了，字体见谅 hhhhhhhh）

总结：也就是说实际上扩容后，从二进制来看，数组的下标位置只有最高位发生了变化，如果元素的二进制最高位为 0，那么就是原位置，如果二进制最高是 1，那么就会变为 1，也就是原位置+旧容量；这种方法可以极大提高运行效率

HashMap 的初始化

我们不讲 HashMap 的自动初始化，源码比较简单，大家可以自己看一看。而在这里要着重讲一下 HashMap 的手动扩容过程：

我们都知道：HashMap 的扩容过程是一个比较浪费时间的过程。因此我们如果想要提高代码运行的效率，就要手动设置初始大小，避免自动扩容。但有的人会在这里陷入一个误区，我们通过一个实际问题来引出：

当我们要存放七个元素的时候，我们应该手动初始化大小为多少呢？

很多同学肯定下意识的回答 8 。 但 其实是错误 的！让我们来思考一下：

如果设置为 8 的话， 负载系数默认是 0.75。那么 8 * 0.75 =6，也就是说数组中 实际元素达到 6 个就要扩容，我们如果存放七个元素，手动设置大小为 8 的话，还是避免不了扩容。

因此：我们应该 手动设置为 （需要存储的元素个数/负载因子）+1。这是计算手动设置容量 的通用方法。

注意：不可以修改负载系数，0.75 是官方大量数据统计出来的一个比较均衡的负载因子，我们基本不会对其做修改！

小结

1.为什么集合的初始化容量必须是 2 的 n 次幂？

首先，当我们尝试向 HashMap 中添加一个元素的时候，需要根据 Key 的 hash 值得到数组中的具体位置。而我们 不可以直接使用 Key 的 hash 值。这是因为 Key 的 hash 值不一定就在数组下标范围内，因此我们要对 Key 的 hash 值再次进行操作，使其满足值的范围在数组下标范围内。

这里的第一个思路就是取余。我们让 hash%n(数组长度)，这样就可以控制得到的值始终在数组下标范围内。

但是这里又有一个问题：如果是取余的话，效率是很低的，不如使用位运算。而我们的代码在实际中也是用位运算来代替取余操作。

而我们在实际中也是这么做的，但是 hash % n 和 （n - 1）& hash 的值相等的前提是 n 是 2 的 x 次幂

而除此之外，返回到使用这个方法的最外层，我们的目的还是为了让数据能够均匀分布，减少 Hash 冲突。

如果创建 HashMap 的时候，输入的数组长度不是 2 的幂，那么 HashMap 就会通过位运算得到一个比我们输入的数组长度大的，离我们输入数组长度最近的一个 2 的幂。

2.hash 方法为什么要右移 16 位异或？（(h = key.hashCode()) ^ (h >>> 16)）

其中 h = key.hashCode() ^ (h >>> 16) 的目的是为了 增加哈希值的随机性，使得节点在哈希表中分布更均匀，减少哈希冲突，提高查找效率。

具体来说：

• 首先，通过 key.hashCode() 获取键的哈希码。
• 接着，通过 h >>> 16 将 h 右移 16 位，然后将结果与 h 进行异或操作 ^。这样做是为了让高位的信息参与到低位的计算中，增加低位的随机性。

通过这样的运算，可以让原始的哈希值的高位和低位进行混合，并且引入了一定程度的随机性，使得最终的哈希值分布更加均匀，减少了哈希冲突的概率。这种处理方式有助于提高 HashMap 的性能，特别是在处理大量数据时，能够更有效地分散数据，减少链表长度，提高查找效率。

如果当哈希值的高位变化很大，低位变化很小，这样就很容易造成哈希冲突了，所以这里把高低位都利用起来，从而解决了这个问题。

3.HashMap 将链表转化为红黑树的链表边界长度为什么是 8

这个问题其实在 HashMap 的源码中就给了解释：

简要的意思就是：由于树节点的大小是链表节点的两倍，因此我们轻易不会将链表转化为红黑树，这会对内存造成浪费。而在大量的实际数据插入的情况下，我们统计发现：箱子中的节点的频率服从泊松分布。

当连续插到链表的第八个节点的时候，实际上概率已经很小了，已经达到了 0.00000006。也就是说我们将链表的长度设置为 8，就已经可以应对大多数的 HashMap 的 Hash 碰撞了 。当节点大于 8 的时候，我们再考虑查询的效率问题，将其转化为红黑树。

总结来讲，将链表转换红黑树的链表长度边界设置为 8，是综合时间和空间的结果。

4.红黑树退化成链表的条件？

1. 扩容 resize( ) 时，红黑树拆分成的 树的结点数小于等于临界值 6 个，则退化成链表。

2. 删除元素 remove( ) 时，在 removeTreeNode( ) 方法会检查红黑树是否满足退化条件，与结点数无关。如果红黑树根 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，都会发生红黑树退化成链表。

5.HashMap 是怎么解决哈希冲突的？

1. 使用 链地址法（使用散列表）来链接拥有相同下标的数据；
2. 使用 2 次扰动函数（hash 函数）来降低哈希冲突的概率，使得数据分布更平均；
3. 引入 红黑树 进一步降低遍历的时间复杂度，使得遍历更快；

HashMap 线程不安全原因

首先给出结论，HashMap 在 JDK1.7、1.8 下，扩容均会出现线程不安全问题

1. 在 JDK1.7 中，HashMap 会出现以下三个问题：

   1. 多线程扩容，头插法扩容，引起的死循环问题
   2. 多线程 put 的时候可能导致元素丢失
   3. put 非 null 元素后 get 出来的却是 null

2. 在 JDK1.8，改用尾插法，避免产生死循环问题，但是可能会出现数据覆盖问题

JDK1.7 扩容引发的死循环和数据丢失

当前 jdk1.7 版本的 HashMap 线程不安全主要是发生在扩容函数中，其中调用了 HshMap 的 transfer()方法

//jdk 1.7的transfer方法，HashMap的扩容操作
public void transfer(Entry[] newTable, boolean rehash) {
    int newCapacity = newTable.length;
    for (Entry<K,V> e : table) {
        while(null != e) {
            Entry<K,V> 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;								// 得到下一个节点
        }
    }
}

• 举例：
  • 假设现在有两个线程 A、B 同时对下面这个 HashMap 进行扩容操作
  • 假设 HashMap 的寻址函数为（ key%数组长度 ）

正常扩容后结果

假设当线程 A 执行到上面 transfer 函数的第 11 行代码时，CPU 时间片耗尽，线程 A 被挂起。即如下图中位置所示：

此时线程 A 中：e=3、e.next=null、next=7

当线程 A 的时间片耗尽后，CPU 开始执行线程 B，并在线程 B 中成功的完成了数据迁移

根据 JMM 得出，线程 B 执行完数据迁移后，此时主内存中 newTable 和 table 都是最新的，也就是说：7.next=3、3.next=null（改变了线程 A 中的状态）

随后线程 A 再次获得 CPU 时间片继续执行 newTable[i] = e，将 3 放入新数组对应的位置

执行第一轮循环后线程 A 的情况如下：

接着继续执行下一轮循环，此时 e=7，从主内存中读取 e.next 时发现主内存中 7.next=3，此时 next=3

并将 7 采用头插法的方式放入新数组中，并继续执行第二轮循环，结果如下：

执行第三次循环，插入数据 3，产生死锁问题和数据丢失问题

JDK1.8 扩容引发的数据覆盖问题

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)     // 如果没有 hash 碰撞，则直接插入
        tab[i] = newNode(hash, key, value, null);
}

源码只是判断了 hash 是否有碰撞，如果没有就不再做别的检查进行插入操作

在多线程环境下，如果线程 1 检查完了 hash 没有碰撞，要进行插入时， CPU 时间片使用完毕，此时它被挂起

线程 2 开始跑，无巧不成书嘛，此时线程 2 经过 hash 之后得到的值和线程 1 的 hash 值一样，线程 2 将值插入进去，线程 1 恢复运行，因为前面检查了 hash 碰撞，此时插入时不再做任何检查，直接将值插入

那么线程 2 插入的值就被覆盖掉了

HashMap 之所以发生数据覆盖的问题，最主要的原因在于它没有加锁，所以在多线程环境下会发生数据覆盖问题

HashMap 的遍历方式

1. 使用 Iterator 遍历 HashMap 的 EntrySet：使用 entrySet()获取 map 的 entryset 集合，再使用 interator()获取 Iterator，最后根据 hashNext()和 next()遍历 entry
2. 使用 Iterator 遍历 HashMap 的 KeySet：keySet()，获取的是 key 集合
3. 使用 for each 遍历 HashMap：for(Entry entry:map)
4. 使用 lambda 表达式：map.forEach(entry->{})
5. 使用 stream 流：map.entryset().stream().forEach((entry)->{})

版权所有

版权归属：haipeng-lin

许可证：署名 4.0 国际 (CC-BY-4.0)