跳至主要內容

Java集合常见知识点总结(下)

JavaJuiceJavaJava集合约 12004 字大约 40 分钟

一、Map（重要）

HashMap 和 Hashtable 的区别

HashMap 和 Hashtable 都是基于哈希表的实现，但它们在多个方面有所不同，下面是这两者的详细对比：

  1. 线程安全性

    • HashMap：是非线程安全的。多个线程同时访问 HashMap，并且其中一个线程修改了 Map，需要外部进行同步控制来保证线程安全。
    • Hashtable：是线程安全的。Hashtable 的方法大多都使用 synchronized 关键字进行了同步，从而确保在多线程环境下访问时是安全的。但这种同步机制会影响性能，导致 Hashtable 在大多数情况下比 HashMap 慢。

  2. 效率

    • HashMap：由于没有内置的同步机制，HashMap 的性能通常比 Hashtable 更高。HashMap 更适合在单线程环境下使用，或者在外部有明确同步控制的多线程环境下使用。
    • Hashtable：由于使用了 synchronized 进行同步，其性能相对较低，因此 Hashtable 在现代 Java 开发中不再推荐使用。

  3. 对 null 键和值的支持

    • HashMap：可以存储一个 null 键和多个 null 值。即，null 可以作为键，也可以作为值。
    • Hashtable：不允许存储 null 键或 null 值。如果尝试存储 null 键或 null 值，Hashtable 会抛出 NullPointerException。

  4. 初始容量和扩容策略

    • HashMap：默认初始容量为 16，每次扩容为原来容量的 2 倍。可以通过构造函数传入自定义的初始容量和负载因子（默认为 0.75）。
    • Hashtable：默认初始容量为 11，每次扩容时容量变为原来的 2n + 1，即不是 2 的幂次方。

    例如，HashMap 的构造函数：

    public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

    tableSizeFor 方法确保了 HashMap 使用 2 的幂作为哈希表的容量：

    static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

  5. 底层数据结构

    • HashMap：JDK 1.8 之后，当哈希冲突的链表长度超过 8 时，HashMap 会将链表转换为红黑树，以提高查找效率。此举减少了在哈希冲突严重时的时间复杂度，从 O(n) 降低至 O(log n)。
    • Hashtable：Hashtable 没有使用红黑树来优化哈希冲突，它依然使用链表进行冲突处理，因此查找性能较低，尤其在哈希冲突严重时。

  6. 哈希函数的实现

    • HashMap：对键的哈希值进行了扰动处理（即通过对高位和低位进行混合扰动），以减少哈希冲突，提升性能。
    • Hashtable：直接使用键的 hashCode() 值，没有额外的扰动处理，可能导致更多的哈希冲突，影响性能。
总结
特性HashMapHashtable
线程安全非线程安全线程安全
效率较高较低（由于使用 synchronized）
对 null 的支持允许一个 null 键和多个 null 值不允许 null 键和值
初始容量默认 16，扩容时为 2 的幂次方默认 11，扩容时为 2n+1
底层数据结构数组 + 链表（转为红黑树）数组 + 链表
哈希函数高位和低位扰动处理直接使用 hashCode()
推荐使用
  • HashMap：适用于大多数场景，尤其是当你不需要线程安全时。如果需要线程安全，可以使用 ConcurrentHashMap。
  • Hashtable：基本已被淘汰，不再推荐使用。对于需要线程安全的映射，建议使用 ConcurrentHashMap，它提供了更好的性能和扩展性。

HashMap 和 HashSet 的区别是什么？

虽然 HashSet 是基于 HashMap 实现的，但它们在功能和行为上有所不同。下面是它们之间的区别：

特性HashMapHashSet
实现的接口实现了 Map 接口实现了 Set 接口
存储的内容存储键值对 (Key-Value pairs)仅存储元素（对象）
添加元素的方法通过 put(K key, V value) 方法添加元素通过 add(E e) 方法添加元素
哈希值的计算HashMap 使用键 (Key) 计算 hashCode 值HashSet 使用成员对象的 hashCode 值计算。对于两个对象来说，hashCode 可能相同，因此需要使用 equals() 方法判断对象是否相等。
是否允许重复元素HashMap 允许键值对中有重复的值，但键 (Key) 不允许重复；对于相同的键，后插入的值会覆盖前一个值。HashSet 不允许重复的元素；如果尝试添加重复元素，add() 方法会返回 false。
底层实现基于哈希表，使用 Key-Value 存储基于 HashMap 的键部分实现，值部分总是 const 值（通常是 PRESENT）
存储的值类型存储的是键和值两个对象只存储对象，没有对应的值
小结
  • HashMap 用于存储键值对数据，支持通过键来快速查找和修改对应的值。
  • HashSet 是基于 HashMap 来实现的，它只是简化了 HashMap，不需要存储值（只有键），因此值部分统一为一个常量值，功能上提供了一个无重复元素的集合。

HashMap 和 TreeMap 的区别

HashMap 和 TreeMap 都实现了 Map 接口，提供了键值对存储功能，但它们之间有一些显著的区别：

特性HashMapTreeMap
底层数据结构基于哈希表实现，元素存储无序基于红黑树实现，元素存储有序
是否排序不保证元素的顺序，插入顺序和迭代顺序无关按照键的自然顺序或指定的比较器对元素进行排序
实现接口实现了 Map 接口实现了 Map、NavigableMap 和 SortedMap 接口
键的排序不排序按照键的自然顺序或指定的比较器排序
对元素排序的能力无支持根据键排序，提供了 ceilingEntry()、floorEntry()、higherEntry() 等方法支持定向搜索
时间复杂度插入、删除、查询平均时间复杂度为 O(1)插入、删除、查询时间复杂度为 O(log n)
空键和空值允许 null 键和 null 值不允许 null 键，但允许 null 值
是否线程安全非线程安全非线程安全
常用的构造方法new HashMap()new TreeMap()，也可以传入 Comparator 对象进行自定义排序

主要区别

  1. 排序与有序性：

    • HashMap 存储的元素无序，迭代顺序与插入顺序无关。
    • TreeMap 会根据键的自然顺序（或提供的比较器）对元素进行排序。

  2. 性能差异：

    • HashMap 在插入、删除、查询元素时平均时间复杂度为 O(1)，适用于不需要排序的场景。
    • TreeMap 在插入、删除、查询时时间复杂度为 O(log n)，适用于需要排序或者需要定向搜索的场景。

  3. 支持的接口与功能：

    • TreeMap 实现了 NavigableMap 和 SortedMap 接口，提供了更多对元素排序和范围搜索的支持。
    • HashMap 只是实现了 Map 接口，功能较为简单，不能直接支持定向搜索、子集操作等功能。

  4. 空键和空值：

    • HashMap 允许 null 作为键或值。
    • TreeMap 不允许 null 键，但允许 null 值。

适用场景

  • HashMap 适用于需要快速查找、插入和删除元素，但不关心元素顺序的场景。
  • TreeMap 适用于需要按照自然顺序或自定义顺序对元素排序，并且需要高效进行范围查询、定向搜索等操作的场景。

HashSet 如何检查重复？

HashSet 通过 hashCode() 和 equals() 方法来判断元素是否重复。当你向 HashSet 添加元素时，底层首先会计算该元素的 hashCode 值，然后根据这个值来确定该元素应该存放的位置。接下来，它会根据 hashCode 值与其他元素进行比较，如果没有相同的 hashCode，那么 HashSet 假设该元素是唯一的。

但是，如果在 hashCode 相同的桶中发现了其他元素，HashSet 会进一步调用 equals() 方法来判断两个对象是否真的相等。如果 equals() 返回 true，那么 HashSet 就认为该元素已经存在，不会插入重复的元素。

HashSet 的 add() 方法源码解析

在 JDK1.8 及以后的版本中，HashSet 的 add() 方法实际上是依赖于 HashMap 来实现的。HashSet 的 add() 方法调用了 HashMap 的 put() 方法，并通过返回值判断该元素是否已存在于集合中。

public boolean add(E e) {
    return map.put(e, PRESENT) == null;
}

在这段代码中：

  • map 是 HashSet 内部使用的 HashMap。
  • PRESENT 是一个常量值，表示我们为每个 HashSet 的元素存储的值。在 HashMap 中，键是我们要存储的元素，值是 PRESENT。
  • map.put(e, PRESENT) 返回 null 表示该元素在 HashSet 中是唯一的，因为 put() 只会插入新元素，如果键已经存在则不会改变值。

HashMap 的 putVal() 方法

HashMap 的 put() 方法会调用 putVal() 方法来执行实际的插入操作。具体实现如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {
    // 判断键是否已存在
    if (existing != null) {
        // 如果键相同，调用 equals() 判断是否相同
        if (!equals(key, existing)) {
            // 有不同的对象就插入新值
        } else {
            // 已经存在就跳过
        }
    }
    // 插入新元素
}

在 putVal() 方法中，首先会比较键的 hash 值，如果 hash 值相同，才会调用 equals() 来进一步判断对象是否重复。

总结
  • HashSet 在判断是否有重复元素时，首先通过 hashCode() 判断位置，如果两个元素的 hashCode 不同，则认为它们不重复。
  • 如果 hashCode 相同，HashSet 会使用 equals() 方法进一步判断两个元素是否相等，只有当 equals() 返回 false 时，才会将元素添加到集合中。
  • 在 JDK1.8 中，HashSet 是通过 HashMap 实现的，add() 方法会调用 HashMap 的 put() 方法，利用 put() 的返回值来判断是否存在重复元素。

HashMap 的底层实现

JDK1.8 之前

在 JDK 1.8 之前，HashMap 的底层实现采用了 数组和链表 结合的方式，即 链表散列。HashMap 通过 key 的 hashCode 值生成 hash 值，再通过 (n - 1) & hash 来确定存放位置（其中 n 为数组长度）。如果当前位置已经有元素，则通过链表（拉链法）解决哈希冲突。

扰动函数（hash 方法）：为了优化哈希值的分布，HashMap 在使用 key.hashCode() 时进行了额外的扰动处理。这个处理通过按位异或和无符号右移操作来减少哈希碰撞的几率。

JDK 1.8 hash 方法源码：

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

与 JDK 1.7 的实现对比，JDK 1.8 的 hash 方法较为简洁，性能也更好（少了几次扰动）。

JDK 1.7 hash 方法源码：

static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

拉链法：即通过将链表和数组结合，每个数组元素就是一个链表。当发生哈希冲突时，新元素就会被添加到对应数组位置的链表中。

JDK1.8 之后

在 JDK 1.8 之后，HashMap 的底层实现做出了重要改进。当链表长度大于 8 时，链表会被转换为红黑树。红黑树是一种自平衡的二叉搜索树，其查询时间复杂度为 O(log n)，相比链表的 O(n)，性能大大提高。

链表转红黑树的阈值：

  • 链表长度大于 8 时，尝试将链表转为红黑树。
  • 如果当前数组长度小于 64，则优先扩容数组，而不是直接将链表转为红黑树。扩容可以有效降低哈希冲突的概率，提升性能。

为什么设置阈值为 8 和 64？

  • 8：链表长度达到 8 的概率较低，阈值设置为 8 可以保证绝大多数情况下，链表长度不会过长，因此不必过早引入红黑树。
  • 64：数组长度达到 64 时，哈希冲突的概率较高，这时使用红黑树会显著提高性能。

链表到红黑树转换的源码分析：

  1. putVal 方法中的链表转红黑树判断：
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        p.next = newNode(hash, key, value, null);
        if (binCount >= TREEIFY_THRESHOLD - 1)
            treeifyBin(tab, hash); // 链表长度大于8时，转换为红黑树
        break;
    }
    if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}
  1. treeifyBin 方法中的红黑树转换：
final void treeifyBin(Node<K,V>[] tab, int hash) {
    int n, index; Node<K,V> e;
    if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY)
        resize(); // 扩容数组
    else if ((e = tab[index = (n - 1) & hash]) != null) {
        TreeNode<K,V> hd = null, tl = null;
        do {
            TreeNode<K,V> p = replacementTreeNode(e, null);
            if (tl == null)
                hd = p;
            else {
                p.prev = tl;
                tl.next = p;
            }
            tl = p;
        } while ((e = e.next) != null);
        if ((tab[index] = hd) != null)
            hd.treeify(tab); // 转换成红黑树
    }
}
总结

JDK 1.8 之后，HashMap 的底层实现增加了红黑树机制，以优化链表在哈希冲突严重时的性能。通过判断链表长度和数组容量的条件，HashMap 会选择扩容或转换成红黑树，保证了在高并发情况下性能的平衡。

HashMap 的长度为什么是 2 的幂次方？

HashMap 的数组长度之所以是 2 的幂次方，主要是为了提高存取效率，并减少哈希碰撞。下面是详细的解释：

1. 位运算比取余运算更高效

当我们需要计算某个元素应该存放在 HashMap 数组的哪个位置时，我们通常会使用哈希值与数组长度的关系。在 JDK 中，为了提高效率，使用的是按位与操作 (&) 而非取余 (%) 操作。具体来说，当数组长度是 2 的幂次方时，hash % length 可以通过 hash & (length - 1) 来代替。这是因为：

  • 2 的幂次方的二进制表示形如 10000...0000，例如 8、16、32、64 等。
  • length - 1 的二进制表示形如 01111...1111，例如 7、15、31、63 等。

通过位运算 (&)，可以快速确定数组的下标，避免了昂贵的除法运算。由于位运算的处理速度远高于取余运算，因此采用位运算能够显著提高效率。

例如：

int index = hash & (length - 1);

等同于：

int index = hash % length;

在 length 是 2 的幂次方时，使用 & 操作会更高效。

2. 哈希值的均匀分布

当数组长度是 2 的幂次方时，哈希值的高位（最左边的一些二进制位）决定了元素的存储位置。因为数组的索引是根据二进制位进行计算的，所以：

  • 当元素扩容时，新数组的容量是原来的两倍，旧数组的元素根据高位二进制位的变化来决定是否移动位置。
  • 如果哈希值的高位变化（例如高位为 1 时，元素将移动到新数组的后半部分），那么新数组的元素可以更加均匀地分布。

3. 扩容机制简化和高效

当数组容量是 2 的幂次方时，扩容机制变得非常简单。具体来说：

  • 当 HashMap 扩容时，新数组的大小是旧数组的两倍，扩容后的元素位置计算非常直观。
  • 通过查看哈希值的高位（在 length 是 2 的幂次方时，length - 1 是一串连续的 1），我们可以轻松地判断某个元素是否应该留在原来的位置，或者应该移动到新数组的后半部分。

例如，假设元素的哈希值为 10101100：

  1. 在容量为 8 时，length - 1 = 7，即 0111，通过 hash & 7 计算得到下标。
  2. 在扩容后，容量变为 16，length - 1 = 15，即 1111，通过 hash & 15 计算得到下标。

通过对比两者，可以看到数组的重新分布会依据哈希值的高位进行，确保新数组的元素分布更加均匀。

4. 总结

HashMap 的数组长度选择 2 的幂次方，主要有以下几个原因：

  1. 位运算效率更高：位运算（&）比取余（%）运算要高效得多。
  2. 哈希值均匀分布：通过使用哈希值的高位，可以更好地将元素均匀地分配到扩容后的数组中，减少冲突。
  3. 扩容机制简化：扩容时可以仅通过检查哈希值高位的变化来决定元素的新位置，使扩容过程更加高效且简单。

HashMap 多线程操作导致死循环问题

1. 问题背景

在 JDK 1.7 及之前版本的 HashMap 中，多线程环境下进行扩容操作时，可能会出现 死循环 的问题。这是由于多个线程同时对一个桶（链表）中的元素进行操作时，链表的结构可能被破坏，最终形成 环形链表，导致在遍历链表时陷入死循环。

2. 死循环的原因

JDK 1.7 中，HashMap 在扩容时会将旧数组中的元素重新分配到新的数组位置（rehash）。这一过程中，使用的是 头插法（新节点插入到链表头部）。头插法的实现过程如下：

  1. 遍历旧数组中的每个链表。
  2. 将链表中的每个元素根据新的数组容量重新计算索引位置。
  3. 将这些元素插入到新数组中相应的链表头部。

由于头插法会改变链表中节点的顺序，如果多个线程同时对链表进行操作，可能导致链表反转，甚至形成环形链表。最终，当另一个线程试图遍历这个链表时，就会因为环形链表陷入死循环。

示意图：

  • 线程 A 和线程 B 同时执行扩容操作。
  • 线程 A 把链表节点倒置为 3 -> 2 -> 1。
  • 线程 B 继续倒置链表，导致链表形成环形结构。

3. JDK 1.8 的改进

为了解决死循环的问题，JDK 1.8 对 HashMap 的底层实现做了以下改进：

  1. 尾插法替代头插法：在重新分配链表中的元素时，采用尾插法而非头插法。尾插法保证了链表中节点的顺序不变，避免了链表倒置导致的环形链表问题。
  2. 引入红黑树：当链表长度超过一定阈值（默认为 8）时，将链表转换为红黑树，进一步优化哈希冲突的处理。

尽管如此，HashMap 在多线程环境下依然 不是线程安全的，可能会发生数据覆盖或其他问题，因此仍然不建议在并发场景中使用。

4. 并发环境下的替代方案

在多线程环境下，可以使用以下替代方案：

  • ConcurrentHashMap：一种线程安全的哈希表，使用分段锁机制或 CAS 操作来保证线程安全。
  • Collections.synchronizedMap：对 HashMap 进行包装，使其具备线程安全特性（性能较差）。
  • Hashtable：JDK 提供的线程安全版本的哈希表（已过时，性能较差）。

5. 总结

  • JDK 1.7 及之前的 HashMap 在多线程环境下可能出现死循环问题，其原因是 头插法 在扩容时导致链表倒置，最终形成环形链表。
  • JDK 1.8 引入 尾插法 和 红黑树 解决了死循环问题，但仍不建议在多线程环境下使用 HashMap。
  • 多线程环境下推荐使用 ConcurrentHashMap，避免数据覆盖和死锁问题。

HashMap 为什么线程不安全？

HashMap 在多线程环境下存在线程不安全的问题，特别是在扩容和插入操作时，由于没有适当的同步机制，导致可能发生数据丢失或数据覆盖的情况。以下是一些主要原因：

1. 扩容时的死循环（JDK 1.7 和之前版本）

在 JDK 1.7 及之前的版本中，HashMap 在扩容时使用头插法（将新节点插入到链表的头部）。如果多个线程同时对同一个桶中的链表进行操作，会导致链表结构被破坏，最终可能形成环形链表。当程序遍历该链表时，可能陷入死循环。

2. 数据覆盖问题（JDK 1.8 及之后版本）

即使在 JDK 1.8 中，HashMap 通过尾插法避免了死循环问题，但在多线程环境下，仍然存在数据覆盖和数据丢失的问题。具体原因可以归结为以下几点：

  • 哈希冲突的处理： 在多线程环境中，如果两个线程同时插入相同哈希值的键值对，且都计算出相同的桶位索引，则会导致哈希冲突。此时，如果一个线程先判断了冲突并开始插入，而另一个线程插入了数据，可能导致第一个线程插入的数据被第二个线程覆盖。

    例如：

    • 线程 1 执行 put 操作时发现发生哈希冲突并判断链表中已经有元素，等待 CPU 时间片切换。
    • 线程 2 先执行插入操作，插入了数据。
    • 线程 1 重新执行插入操作，插入时并没有重新判断哈希冲突，从而导致线程 2 插入的数据被覆盖。
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // 判断是否发生哈希碰撞
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 处理哈希冲突
        // ...
    }
}

  • size 属性的更新： HashMap 内部维护了 size 属性，表示当前元素的数量。在多线程环境下，两个线程可能会同时读取 size 并进行自增操作，导致更新时的竞争条件，使得 size 的值不准确，从而导致扩容时判断不准确，可能导致数据覆盖。

    例如：

    • 线程 1 执行 if (++size > threshold) 时，假设 size 为 10。
    • 线程 2 也执行了 if (++size > threshold)，并将 size 更新为 11，同时插入了新的数据。
    • 线程 1 继续执行，认为 size 还小于阈值，继续插入数据，导致 size 最终被错误地更新为 11，但实际上插入了两个元素。
public V put(K key, V value) {
    return putVal(hash(key), key, value, false, true);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                   boolean evict) {
    // 执行扩容检查
    if (++size > threshold)
        resize();
    // 插入元素后进行回调
    afterNodeInsertion(evict);
    return null;
}

3. 线程不安全的根本原因

HashMap 在多线程下不具备内建的同步机制，导致对同一数据的并发操作没有加锁保护，多个线程可能同时修改 HashMap，从而引发数据丢失或覆盖的问题。特别是在扩容和插入的关键操作上，缺乏同步会导致线程安全问题。

4. 并发环境下的替代方案

由于 HashMap 不适合用于多线程环境，尤其是高并发场景下，可以考虑以下线程安全的替代方案：

  • ConcurrentHashMap：这是一个线程安全的哈希表，采用分段锁机制来保证并发访问时不会发生竞争，能够确保高并发环境下的正确性。

  • Collections.synchronizedMap：将 HashMap 包装为同步版本，保证线程安全，但会导致性能瓶颈，尤其是在高并发情况下，性能较差。

  • Hashtable：JDK 中提供的旧版本线程安全的哈希表（不推荐使用，已过时且性能较差）。

总结
  • JDK 1.8 及之前的 HashMap 在多线程环境下由于缺乏同步机制，导致并发写入时可能发生数据丢失或覆盖的问题。
  • 哈希冲突和 size 更新 是导致 HashMap 线程不安全的关键原因。
  • 多线程下使用 ConcurrentHashMap 是推荐的解决方案，它能够提供更好的性能和线程安全保障。

HashMap 常见的遍历方式

HashMap 提供了几种常见的遍历方式，每种方式在不同场景下有不同的性能表现。以下是几种常见的遍历方式及其性能分析：

1. 使用 entrySet() 遍历

entrySet() 返回的是一个包含 Map.Entry<K, V> 对象的集合。每个 Map.Entry 包含了一个键值对。使用这种方式遍历时，可以同时获取到键和值，性能较高。

Map<String, Integer> map = new HashMap<>();
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    String key = entry.getKey();
    Integer value = entry.getValue();
}

性能： 性能较好，通常是 HashMap 遍历的首选方法，因为直接获取了键值对，避免了重复查找键和值。

2. 使用 keySet() 遍历

keySet() 返回的是 HashMap 中所有键的集合，通过遍历键集，再通过 get(key) 方法获取对应的值。

Map<String, Integer> map = new HashMap<>();
for (String key : map.keySet()) {
    Integer value = map.get(key);
}

性能： 相比 entrySet()，这种方法性能稍差，因为每次通过键获取值都需要进行一次哈希查找，导致时间复杂度较高。

3. 使用 values() 遍历

values() 返回的是 HashMap 中所有值的集合。如果只关心值而不关心键，可以使用这种方法。

Map<String, Integer> map = new HashMap<>();
for (Integer value : map.values()) {
    // 处理 value
}

性能： 性能与 keySet() 类似，但这种方法只能遍历值，不能获取键。如果你只需要值，这种方法是最简单的。

4. 使用 Lambda 表达式遍历

在 Java 8 之后，可以使用 Lambda 表达式进行遍历。通常通过 forEach 方法遍历 entrySet() 或 keySet()。

map.forEach((key, value) -> {
    // 处理 key 和 value
});

性能： 这种方式比传统的 for 循环略慢，因为 forEach 使用了函数式接口的调用。但它提供了更简洁的代码，适合函数式编程风格。

5. 使用 parallelStream() 遍历

parallelStream() 通过并行流来遍历 HashMap，这在处理大数据时可以提高性能。它会将数据分割成多个线程并行处理。

map.entrySet().parallelStream().forEach(entry -> {
    // 处理 entry
});

性能：

  • 在没有阻塞的情况下，parallelStream() 性能最差，因为线程间的开销会导致性能下降。
  • 在存在阻塞操作（如 I/O 操作或网络请求）时，parallelStream() 的性能会显著提升，因为可以通过并行执行来减少整体的等待时间。

6. 使用 forEach() 遍历

forEach() 是 Java 8 提供的 Map 的一个方法，用于对每个元素执行操作。

map.forEach((key, value) -> {
    // 处理 key 和 value
});

性能： 与 Lambda 表达式类似，forEach() 也带来一定的性能开销，适合在操作较少的情况下使用。

性能分析总结

根据测试结果的分析：

  1. entrySet() 是最有效的遍历方式，尤其是在不涉及并发的情况下，它的性能通常最好。
  2. keySet() 在性能上略逊色于 entrySet()，因为每次访问值时需要额外的 get(key) 操作。
  3. lambda 和 forEach 的性能开销较大，特别是在较小的数据量下，差距会比较明显。
  4. parallelStream() 在没有阻塞操作时性能最差，但如果有阻塞操作（如 I/O 或线程等待），它能够通过并行处理提高性能。
结论
  • 一般情况下，entrySet() 是最优的遍历方式。
  • 如果并发操作较多且存在阻塞，parallelStream() 可以提升性能。
  • 在性能至上的场景中，尽量避免使用 forEach() 和 lambda，而优先选择 entrySet() 或 keySet()。

ConcurrentHashMap 和 Hashtable 的区别

ConcurrentHashMap 和 Hashtable 都是线程安全的哈希表实现，但是它们在设计和实现上有显著的差异。以下是两者的主要区别：

1. 底层数据结构

  • Hashtable：
    • 使用 数组 + 链表 的结构。
    • 所有操作（如 put、get 等）都使用 同一把锁，无论是读取还是写入。
  • ConcurrentHashMap：
    • JDK 1.7：使用 Segment 数组 + HashEntry 数组 结构，每个 Segment 类似一个独立的哈希表，每个段都有自己的锁，这样可以在不同段之间并行操作。
    • JDK 1.8：不再使用 Segment，而是采用了与 HashMap 相似的 Node 数组 + 链表 / 红黑树 结构。并发控制通过 synchronized 和 CAS（Compare-And-Swap） 来实现，避免了全表锁。

2. 线程安全的实现方式

  • Hashtable：

    • 使用 synchronized 锁来保证线程安全，这意味着每次只有一个线程能访问哈希表的某个元素。对于写操作和读操作，都会获取同一把锁，因此在多线程环境下性能非常差，尤其是在并发量大时，锁竞争严重，效率低下。

  • ConcurrentHashMap：

    • JDK 1.7：采用了 分段锁（Segment）。将整个哈希表分为多个段（Segment），每个段有一个独立的锁。这样，当不同线程操作不同段的数据时，不会发生锁竞争，提高了并发性。
    • JDK 1.8：摒弃了分段锁的概念，改为使用 synchronized 和 CAS 来保证线程安全，且采用了更灵活的锁策略。对于小范围的锁控制和无锁读写操作，它提供了更好的并发性能。

3. 扩容机制

  • Hashtable：
    • Hashtable 使用的是 线性扩容，每次扩容时会重新计算整个表的大小，并对所有的键值对重新计算哈希值，这会造成性能下降。
  • ConcurrentHashMap：
    • JDK 1.7：采用 分段扩容，每个段独立扩容，避免了全表扩容的性能瓶颈。
    • JDK 1.8：采用了动态扩容方式，基于 链表/红黑树 的结构进行扩容，性能更高并且避免了扩容时全表锁的问题。

4. 性能差异

  • Hashtable：
    • 由于每个操作都必须获取同一把锁，导致在多线程环境下表现出极差的并发性能。即使只有一个线程在执行操作，锁的管理和获取也是有开销的。
  • ConcurrentHashMap：
    • 采用了分段锁（在 JDK 1.7 中）或更灵活的锁策略（在 JDK 1.8 中），允许多个线程并发地读取不同段或桶的数据，从而显著提高了并发性能。
    • 在读多写少的场景下表现优越，因为它采用了较少的锁来控制并发，能有效减少线程间的竞争。

5. 可伸缩性

  • Hashtable：

    • Hashtable 在多线程下的可伸缩性差，因为所有线程在进行操作时都需要竞争同一把锁。

  • ConcurrentHashMap：

    • 由于采用分段锁和其他并发控制策略，ConcurrentHashMap 提供了更好的可伸缩性，特别是在高并发场景下。

6. 线程安全级别

  • Hashtable：

    • 通过 synchronized 保证线程安全，确保操作的原子性，但由于锁的粒度较大，容易发生线程竞争，影响性能。

  • ConcurrentHashMap：

    • 在 JDK 1.7 中，通过 分段锁 实现了更细粒度的锁控制，在 JDK 1.8 中，采用了更优化的 synchronized 和 CAS 来提供高效的并发支持。

7. 其他特点

  • Hashtable：

    • Hashtable 继承自 Dictionary 类，已经过时，不推荐使用。
    • Hashtable 的所有方法都是同步的，所以它是线程安全的，但非常低效。

  • ConcurrentHashMap：

    • ConcurrentHashMap 是在 java.util.concurrent 包下的类，专为并发环境设计，推荐用于多线程下的哈希表。
    • 支持更高效的并发操作，且允许 null 键和 null 值的使用（不同于 Hashtable）。
总结
特性HashtableConcurrentHashMap
底层数据结构数组 + 链表数组 + 链表 / 红黑树
线程安全实现方式使用 synchronized分段锁（JDK 1.7）/ CAS + synchronized（JDK 1.8）
性能性能低下，锁竞争严重高并发，较少锁竞争
扩容方式线性扩容分段扩容（JDK 1.7），动态扩容（JDK 1.8）
读操作读写操作都有锁读操作无锁，写操作使用小范围锁
null 键/值不支持 null 键和值支持 null 键和值

总体来说，ConcurrentHashMap 是专为多线程设计的高效并发集合类，而 Hashtable 已经过时，且由于其低效的同步机制，不建议在现代应用中使用。

ConcurrentHashMap 线程安全的具体实现方式与底层具体实现

JDK 1.8 之前（基于分段锁的实现）

数据结构
  • Segment：ConcurrentHashMap 的核心部分，每个 Segment 类似于一个独立的小型哈希表，同时继承了 ReentrantLock，用来实现分段锁。
  • HashEntry：每个 Segment 内部维护一个数组，数组中的每个元素是一个链表（HashEntry）。
工作原理

  1. 分段锁：整个 ConcurrentHashMap 被分为多个 Segment，每个 Segment 可以看作一个独立的小型哈希表，每个 Segment 有自己的锁。

    • 在写操作时，仅锁住对应的 Segment，其他 Segment 可以被其他线程并发访问。
    • 默认 Segment 数组的大小为 16，也就是说，默认支持最多 16 个线程同时写操作。

  2. 读操作：ConcurrentHashMap 的读操作是无锁的。通过 volatile 保证可见性，可以直接读取 HashEntry 数据而无需加锁。

  3. 写操作：

    • 写操作需要先定位到对应的 Segment，再对 Segment 加锁，防止其他线程同时修改同一个 Segment 的数据。
    • 操作完成后，释放锁。
缺点
  • Segment 的数量在初始化时固定，无法动态调整。如果并发度需求变化，可能会影响性能。
  • 分段锁的粒度较粗，不够灵活。

JDK 1.8 之后（取消分段锁，基于 CAS 和 synchronized 的实现）

数据结构
  • Node：每个桶位置使用 Node 对象存储键值对。
  • 链表 / 红黑树：当发生哈希冲突时，初始使用链表存储。当链表长度超过阈值（默认 8）时，链表会转化为红黑树以提高查询效率。
  • 数组：Node 对象的数组用于存储数据。
工作原理

  1. 无分段锁

    • ConcurrentHashMap 取消了 Segment，直接使用一个全局的数组 Node[] table。
    • 每个桶位置可以单独加锁，不影响其他桶的并发操作。

  2. CAS 操作

    • 插入和更新操作使用 CAS（Compare-And-Swap）机制实现线程安全。通过 CAS 保证并发情况下的原子性操作，避免全局加锁。
    • 例如，在新增元素时，如果发现桶位置为空，则使用 CAS 插入新节点。
    if (casTabAt(tab, i, null, new Node<>(hash, key, value, null))) {
    return null;
}

  3. 链表与红黑树

    • 当链表长度超过阈值（默认 8）时，会将链表转换为红黑树，以提高查询效率。
    • 红黑树的插入和删除操作会加锁，防止结构不一致。

  4. synchronized 锁

    • 如果多个线程同时操作同一个桶（如链表或红黑树），会退化为加锁操作。
    • 由于锁的粒度仅限于一个桶（一个链表或红黑树），相较于 JDK 1.7 的分段锁，粒度更细，并发性能更高。
优化点
  • 锁粒度更细：只锁定当前桶的链表或红黑树，减少锁的范围。
  • 读写分离：读取操作完全无锁，依赖 volatile 和 CAS 机制。
  • 动态扩容：当元素数量超过容量的负载因子（默认 0.75）时，触发扩容。扩容时采用分布式的方式，多个线程可以并行完成扩容任务。

主要差异对比

特性JDK 1.7JDK 1.8
锁机制分段锁（Segment）CAS + synchronized
数据结构Segment + HashEntryNode + 链表 / 红黑树
锁粒度分段级别单个桶级别
读操作无锁无锁
写操作锁住对应的 Segment锁住单个桶或使用 CAS
扩容分段扩容分布式扩容
总结
  • JDK 1.8 中，ConcurrentHashMap 的实现比 JDK 1.7 更加灵活，性能更高，适合高并发场景。
  • 它取消了 Segment 分段锁，改用更细粒度的锁和 CAS 操作，进一步优化了并发性能。
  • 在设计上更接近于线程安全的 HashMap，通过引入红黑树解决哈希冲突导致的性能问题。

JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现区别

1. 线程安全实现方式

  • JDK 1.7：

    • 使用 Segment 分段锁 实现线程安全，Segment 继承自 ReentrantLock。
    • 每个 Segment 是一个独立的小型哈希表，只有线程操作同一个 Segment 时才会竞争锁，不同 Segment 之间可以并发访问。

  • JDK 1.8：

    • 取消了 Segment 分段锁的设计，直接使用 Node + CAS + synchronized。
    • 锁粒度更细，synchronized 只锁定当前链表或红黑树的首节点，从而减少锁竞争。
    • 使用 CAS（Compare-And-Swap） 保证并发操作的原子性，如插入节点时用 CAS 方式更新。

2. Hash 碰撞解决方式

  • JDK 1.7：

    • 使用 拉链法 解决哈希冲突，每个桶存储一个链表。
    • 当链表过长时，查询性能会退化为 O(n)。

  • JDK 1.8：

    • 使用 拉链法结合红黑树：
      • 初始情况下仍采用链表，当链表长度超过阈值（默认为 8）时，将链表转换为红黑树。
      • 红黑树的查找性能为 O(log n)，显著提升了查询效率。

3. 并发度

  • JDK 1.7：

    • 最大并发度等于 Segment 的数量，默认为 16，即最多支持 16 个线程同时写入。
    • 并发度受限于分段锁的数量。

  • JDK 1.8：

    • 最大并发度等于 Node 数组的大小，理论上支持更高的并发度。
    • 不同桶（Node）的位置可以被不同线程同时操作，进一步提升了并发性能。

4. 扩容机制

  • JDK 1.7：

    • 采用 分段扩容：扩容时只对某个 Segment 进行重新哈希。
    • 由于只扩容一个 Segment，其他 Segment 可以正常读写，性能相对较好。

  • JDK 1.8：

    • 采用 全局扩容：所有桶（Node）参与扩容。
    • 通过分布式扩容机制，多个线程可以同时参与扩容任务，降低扩容的性能瓶颈。

5. 性能对比

  • JDK 1.7：

    • 由于采用分段锁，锁粒度较粗，虽然并发度较高，但存在锁竞争。
    • 在高并发场景下，性能可能受限。

  • JDK 1.8：

    • 取消分段锁，锁粒度更细，结合 CAS 操作，大幅减少锁竞争。
    • 在读多写少的高并发场景中性能显著优于 JDK 1.7。
总结
特性JDK 1.7JDK 1.8
线程安全实现分段锁（Segment）CAS + synchronized
数据结构Segment + HashEntryNode + 链表 / 红黑树
锁粒度分段锁单桶锁或红黑树锁
Hash 冲突解决拉链法拉链法 + 红黑树
最大并发度16（默认 Segment 数量）Node 数组大小
扩容机制分段扩容全局分布式扩容
性能锁竞争较多，读写并发能力有限锁粒度更细，性能显著提升

JDK 1.8 的实现在并发性能、线程安全和查询效率上都大幅优于 JDK 1.7，是一个全面优化后的版本，适合高并发场景。

ConcurrentHashMap 为什么 key 和 value 不能为 null？

ConcurrentHashMap 的 key 和 value 不能为 null 主要是为了避免二义性和确保线程安全。

1. 二义性问题

  • null 作为键： 如果 null 被用作键，get(key) 方法可能会返回 null，但这可能是由于该键根本没有对应的值，或者该键的值本身就是 null。这就产生了二义性：
    • map.get(key) 返回 null，可能有两种情况：
      1. 该键不存在于 ConcurrentHashMap 中；
      2. 该键对应的值为 null。
  • 在单线程环境下，你可以通过 containsKey(key) 来检查某个键是否存在，从而避免这种歧义。然而，在多线程环境下，另一个线程可能在你调用 containsKey() 和 get() 之间修改了 map 的内容，这使得 containsKey() 和 get() 的调用之间的状态不可预测，从而无法解决二义性。

2. 多线程环境下的线程安全

  • 操作的干扰： 在并发环境下，一个线程可能正在修改 ConcurrentHashMap，而另一个线程正在读取该 map，这就使得无法确定一个返回 null 的值是由于键不存在，还是该键对应的值本身为 null。这对多线程操作来说会带来不一致的状态。

  • HashMap 与 ConcurrentHashMap 的区别：

    • 在 HashMap 中，null 作为键可以存储，但仅限于一个 null 键；null 作为值可以有多个。然而，HashMap 是单线程的，不存在多个线程并发修改的问题，因此可以通过 containsKey() 来判断键是否存在，从而避免二义性。
    • 在 ConcurrentHashMap 中，由于多线程的并发修改，无法通过 containsKey() 确定键是否存在。因此，不允许 null 作为键或值。

3. 替代方案

  • 如果需要在 ConcurrentHashMap 中存储 null 值，可以使用一个特殊的对象来代替 null，比如：

    public static final Object NULL = new Object();

  • 然后在操作中将 NULL 对象作为实际的值来存储，避免使用 null，从而解决二义性问题。

4. Doug Lea（ConcurrentHashMap 的作者）解释

  • Doug Lea 解释说：ConcurrentMap（包括 ConcurrentHashMap 和 ConcurrentSkipListMap）不允许 null 是因为非并发的 Map 中，某些歧义可能是可以容忍的，但在并发环境下，无法容忍这些歧义。例如，当 map.get(key) 返回 null 时，你无法确定该键是否显式映射到 null，还是该键根本没有被映射。这种二义性在并发情况下无法解决，因为在调用期间 map 可能已经发生了变化。
总结

在 ConcurrentHashMap 中不允许 null 作为键或值，是为了避免由于并发修改带来的二义性问题，确保多线程环境下操作的一致性和安全性。如果确实需要使用 null，可以使用一个特殊的对象来替代它。

ConcurrentHashMap 能保证复合操作的原子性吗？

ConcurrentHashMap 是线程安全的，意味着它可以确保多个线程同时访问时，不会导致数据不一致或出现像 JDK1.7 及之前版本的 HashMap 在多线程操作中出现的死循环问题。但这并不意味着它能保证所有复合操作的原子性。理解这一点非常重要。

1. 什么是复合操作？

复合操作是指由多个基本操作（如 put、get、remove、containsKey 等）组成的操作。例如，判断一个键是否存在（containsKey(key)），然后根据判断结果进行插入或更新（put(key, value)）。这类操作在执行过程中可能会被其他线程打断，从而导致结果不符合预期。

2. 复合操作可能出现的问题：

例如，假设有两个线程 A 和 B 同时进行复合操作，如下：

// 线程 A
if (!map.containsKey(key)) {
    map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
    map.put(key, anotherValue);
}

可能的执行顺序如下：

  1. 线程 A 判断 map 中不存在 key。
  2. 线程 B 判断 map 中不存在 key。
  3. 线程 B 将 (key, anotherValue) 插入 map。
  4. 线程 A 将 (key, value) 插入 map。

最终结果是 (key, value)，而不是预期的 (key, anotherValue)，这就是由于复合操作的非原子性导致的问题。

3. ConcurrentHashMap 的线程安全

ConcurrentHashMap 能够保证多个线程进行读写时不会破坏数据一致性，但它不能保证复合操作的原子性。例如，containsKey(key) 和 put(key, value) 之间可能会发生竞争条件。

4. 如何保证复合操作的原子性？

ConcurrentHashMap 提供了一些原子性方法来执行复合操作，这些方法可以有效地避免复合操作中的问题。常用的原子操作方法包括：

  • putIfAbsent(key, value)：只有在 key 不存在时，才插入 value。
  • compute(key, remappingFunction)：根据给定的 key 和 remappingFunction 更新 key 对应的值。
  • computeIfAbsent(key, mappingFunction)：如果 key 不存在，才通过 mappingFunction 计算并插入 value。
  • computeIfPresent(key, remappingFunction)：如果 key 存在，才通过 remappingFunction 更新其值。
  • merge(key, value, remappingFunction)：如果 key 存在，执行 remappingFunction；如果不存在，则插入新的 (key, value)。

例如，使用 putIfAbsent 替代上述复合操作：

// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);

或者，使用 computeIfAbsent 来确保 key 只有在不存在时才插入新的值：

// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);

这样，两个线程都能安全地执行插入操作，而不会出现竞态条件，且避免了使用显式锁。

5. 为什么不使用显式加锁？

在 ConcurrentHashMap 中，推荐使用原子复合操作方法而不是加锁同步机制。使用显式锁（如 synchronized）会影响性能并违背了 ConcurrentHashMap 设计的初衷——提供高效的并发操作。因此，尽量使用内置的原子性操作来确保线程安全。

总结

ConcurrentHashMap 本身保证了读写操作的线程安全，但并不保证复合操作的原子性。为了保证复合操作的原子性，应使用 ConcurrentHashMap 提供的原子性方法，如 putIfAbsent、computeIfAbsent、computeIfPresent 等。这些方法在实现中已确保线程安全，不需要显式加锁。

二、Collections 工具类（不重要）

Collections 工具类常用方法

1. 排序操作

方法描述
reverse(List list)将指定列表中的元素反转。
shuffle(List list)随机排列列表中的元素。
sort(List list)对列表按自然顺序（升序）排序。
sort(List list, Comparator c)使用指定的比较器对列表进行排序，排序规则由 Comparator 决定。
swap(List list, int i, int j)交换列表中两个指定位置的元素。
rotate(List list, int distance)将列表的元素按照指定距离旋转。正数表示后 distance 个元素移动到前面，负数表示前 distance 个元素移动到后面。

2. 查找与替换操作

方法描述
binarySearch(List list, Object key)对列表进行二分查找，返回目标元素的索引。列表必须是有序的。
max(Collection coll)返回集合中最大元素（按自然顺序）。
max(Collection coll, Comparator c)使用指定的比较器返回集合中最大元素。
min(Collection coll)返回集合中最小元素（按自然顺序）。
min(Collection coll, Comparator c)使用指定的比较器返回集合中最小元素。
fill(List list, Object obj)用指定元素替换列表中的所有元素。
frequency(Collection c, Object o)返回指定元素在集合中出现的次数。
indexOfSubList(List list, List target)返回子列表 target 在列表 list 中第一次出现的索引，找不到则返回 -1。
lastIndexOfSubList(List list, List target)返回子列表 target 在列表 list 中最后一次出现的索引，找不到则返回 -1。
replaceAll(List list, Object oldVal, Object newVal)用新元素替换列表中所有匹配的旧元素。

3. 同步控制

Collections 提供了一系列 synchronizedXxx() 方法，将非线程安全的集合转换为线程安全集合。但效率较低，建议使用 java.util.concurrent 包下的并发集合作为替代。

方法描述
synchronizedCollection(Collection<T> c)将指定集合包装成线程安全的集合。
synchronizedList(List<T> list)将指定列表包装成线程安全的列表。
synchronizedMap(Map<K, V> m)将指定映射包装成线程安全的映射。
synchronizedSet(Set<T> s)将指定集合包装成线程安全的集合。
注意事项

  1. 排序与查找操作：

    • 排序方法对可变集合（如 ArrayList）有效，修改会影响原集合。
    • 二分查找要求集合必须是已排序的，否则结果不可预测。

  2. 同步控制：

    • 使用 synchronizedXxx 方法的集合适合少量线程访问场景，多线程情况下效率较低。
    • 建议使用 ConcurrentHashMap、CopyOnWriteArrayList 等更高效的线程安全集合。

  3. 线程安全性：

    • 尽管同步集合解决了线程安全问题，但它们并不保证复合操作的原子性。例如，contains 和 put 的组合操作仍需额外同步。
总结

Collections 工具类提供了丰富的操作方法，包括排序、查找、替换、同步控制等，但在高并发场景下，应尽量使用 java.util.concurrent 包中的集合，以获得更高的效率和线程安全性。

上次编辑于: 2025/1/8 22:08:23
贡献者: jiang