HashMap

约 6747 字大约 22 分钟

2025-01-15

1.HashMap简介

1.1 特点

键值对存储：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.2 优点

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

1.3 缺点

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

2.看看HashMap源码

2.1 常用常量和变量

2.2.1 常用常量

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

2.2.2常用变量

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

2.2 存储过程

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

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

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

需要注意的是：
在JDK8之前，HashMap的构造方法就会帮我们创建一个 长度为16的Entry[] table 用来存储键值数据。
在JDK8以后就不是在HashMap的构造方法底层来创建数组了，而是在第一次调用put方法的时候创建一个 *Node[] table* 来存储键值对数据。

2.2.1 过程

下面将通过源码解读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;
}

2.2.2 哈希表为空

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的正常使用和性能优化。

2.2.3 找到数组位置

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中的键值对能够正确存储和检索。

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

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

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

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

2.2.5 key已存在，更新值

首先，将已存在节点e的值赋给oldValue，以便在后面返回旧的值。
然后会根据onlyIfAbsent的取值来判断是否需要覆盖已存在节点e的值：
- 如果onlyIfAbsent为false，或者oldValue为null（即允许替换已有的空值），则将新值value赋给节点e的值e.value。
接着调用afterNodeAccess(e)方法来进行相关操作，比如LinkedHashMap中重写的方法会将节点移动到链表末尾，以实现LRU策略。
最后返回旧的值oldValue，表示已存在键对应的旧值。
总的来说，这段代码的作用是在HashMap中处理键已存在的情况，根据需要更新节点的值，并在操作后返回旧的值。

2.2.6 判断是否需要扩容

++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中处理插入新节点后更新相关计数器、进行哈希表的扩容操作，并在操作后进行相关处理。*

2.2.7 小结

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

2.3 扩容过程

2.3.1 条件

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

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

2.3.2 特点

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

2.3.3 缺点

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

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

2.3.4 扩容之后对table的调整

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

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

依靠 (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;
}

把 low 插入到新数组中当前数组下标的位置，把 high 链表插入到新数组中 [当前数组下标 + 旧数组长度] 的位置
如果生成的 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;
}

2.3.5数组下标位置的确定原因

通过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，也就是原位置+旧容量；这种方法可以极大提高运行效率

2.4HashMap的初始化

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

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

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

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

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

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

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

3.思考小结

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.红黑树退化成链表的条件？

扩容 resize( ) 时，红黑树拆分成的树的结点数小于等于临界值6个，则退化成链表。
删除元素 remove( ) 时，在 removeTreeNode( ) 方法会检查红黑树是否满足退化条件，与结点数无关。如果红黑树根 root 为空，或者 root 的左子树/右子树为空，root.left.left 根的左子树的左子树为空，都会发生红黑树退化成链表。

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

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

4.HashMap线程不安全原因

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

在JDK1.7中，HashMap会出现以下三个问题：
1. 多线程扩容，头插法扩容，引起的死循环问题
2. 多线程put的时候可能导致元素丢失
3. put非null元素后get出来的却是null
在JDK1.8，改用尾插法，避免产生死循环问题，但是可能会出现数据覆盖问题

4.1 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，产生死锁问题和数据丢失问题

4.2 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 之所以发生数据覆盖的问题，最主要的原因在于它没有加锁，所以在多线程环境下会发生数据覆盖问题

5.HashMap的遍历方式

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

版权所有

本文链接：/Java/Java%E9%9B%86%E5%90%88/6lgmbqf9/

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