Java高手的30k之路｜面试宝典｜精通Map篇

HashMap

HashMap 是 Java 集合框架中非常重要的一部分，它是基于哈希表的数据结构。

1. 基于哈希表的实现

HashMap 基于哈希表实现。哈希表是通过将键（Key）映射到值（Value）的一种数据结构。具体来说，HashMap 使用一个数组和链表（在冲突较少时）或红黑树（在冲突较多时）来存储元素。

2. 负载因子（Load Factor）

负载因子是决定 HashMap 何时需要扩容的一个参数。默认负载因子为 0.75，这意味着当 HashMap 的大小达到其容量的 75% 时，HashMap 会进行扩容。扩容操作通常会将容量翻倍，然后重新散列现有元素。

3. 初始容量（Initial Capacity）

初始容量是 HashMap 在创建时分配的桶数组的大小。默认的初始容量为 16。可以在创建 HashMap 时通过构造函数设置初始容量，以减少扩容次数，从而提高性能。

4. 哈希冲突处理

哈希冲突是指两个或多个不同的键被哈希函数映射到相同的桶位置。HashMap 使用两种主要方法来处理哈希冲突：

链地址法（Chaining）

这是默认的冲突处理方法。每个桶包含一个链表，当冲突发生时，新元素被添加到链表的末尾。如果链表长度超过一定阈值（默认 8），则链表转换为红黑树，以提高查询效率。

红黑树（Red-Black Tree）

当单个桶中的元素数量过多（默认大于 8）时，HashMap 会将链表转换为红黑树。这是因为红黑树的查找性能是 O(log n)，而链表的查找性能是 O(n)。转换为红黑树后，可以显著提高性能。

5. 线程安全问题

HashMap 是非线程安全的。如果多个线程同时访问一个 HashMap，并且至少有一个线程在进行修改操作（插入、删除、更新），就可能导致数据不一致或其他并发问题。为了解决线程安全问题，有几种常见的方案：

使用 Collections.synchronizedMap

Java 提供了一个同步包装器，可以通过 Collections.synchronizedMap 方法来获得一个同步的 Map 实现：

Map<String, String> synchronizedMap = Collections.synchronizedMap(new HashMap<>());

使用 ConcurrentHashMap

ConcurrentHashMap 是一个线程安全的哈希表实现，它使用了一种分段锁机制来提高并发性。每个分段都是一个独立的哈希表，多个线程可以并发访问不同的分段，而不会相互干扰：

ConcurrentHashMap<String, String> concurrentMap = new ConcurrentHashMap<>();

总结

HashMap 是基于哈希表实现的一种高效的键值对存储结构。它通过负载因子和初始容量来控制容量的增长，通过链地址法和红黑树来处理哈希冲突。然而，HashMap 并不是线程安全的，如果需要在多线程环境中使用，可以使用 Collections.synchronizedMap 或 ConcurrentHashMap 来确保线程安全。

LinkedHashMap

LinkedHashMap 是 Java 集合框架中的一个重要类，它继承自 HashMap，并在此基础上增加了维护元素顺序的功能。LinkedHashMap 通过双向链表来维护插入顺序或访问顺序，使得它不仅具备 HashMap 的所有特性，还能在一定程度上满足顺序访问的需求。

1. 基本特性

LinkedHashMap 继承自 HashMap，因此它具备 HashMap 的所有基本特性，包括基于哈希表的实现、高效的插入和查找操作。除此之外，LinkedHashMap 通过双向链表维护键值对的顺序。

2. 维护顺序

LinkedHashMap 可以维护两种顺序：

插入顺序

这是 LinkedHashMap 的默认行为。元素按插入的顺序进行排列，迭代时会按插入顺序返回键值对。这意味着在遍历 LinkedHashMap 时，元素的顺序与其插入顺序一致。

LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");

for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " => " + entry.getValue());
}
// 输出顺序：1 => one, 2 => two, 3 => three

访问顺序

可以通过构造函数参数来启用访问顺序模式。在访问顺序模式下，每次访问元素（包括调用 get 方法、put 方法时访问已存在的键），该元素都会被移到链表的末尾。

LinkedHashMap<Integer, String> map = new LinkedHashMap<>(16, 0.75f, true);
map.put(1, "one");
map.put(2, "two");
map.put(3, "three");

// 访问键 2
map.get(2);

for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " => " + entry.getValue());
}
// 输出顺序：1 => one, 3 => three, 2 => two

3. 内部实现

LinkedHashMap 通过维护一个双向链表来记录元素的顺序。每个节点包含指向前一个节点和后一个节点的指针，确保迭代时可以按照插入或访问顺序遍历所有元素。

class LinkedHashMap<K,V> extends HashMap<K,V> {
    // 双向链表的头部和尾部
    transient LinkedHashMap.Entry<K,V> head;
    transient LinkedHashMap.Entry<K,V> tail;

    // 其他实现细节...

    // 新元素插入到链表的尾部
    void linkNodeLast(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> last = tail;
        tail = p;
        if (last == null)
            head = p;
        else {
            p.before = last;
            last.after = p;
        }
    }

    // 删除节点
    void removeNode(LinkedHashMap.Entry<K,V> p) {
        LinkedHashMap.Entry<K,V> before = p.before, after = p.after;
        p.before = p.after = null;
        if (before == null)
            head = after;
        else
            before.after = after;
        if (after == null)
            tail = before;
        else
            after.before = before;
    }
    
    // 其他实现细节...
}

4. 使用场景

LinkedHashMap 适用于需要维护元素顺序的场景，例如：

• 实现 LRU（最近最少使用）缓存。在访问顺序模式下，每次访问元素都会将其移动到链表末尾，这样可以很容易地删除最久未访问的元素。
• 保留插入顺序的情况下迭代元素。例如，当需要按照元素插入顺序处理数据时，使用 LinkedHashMap 可以简化代码。

总结

LinkedHashMap 在 HashMap 的基础上，通过双向链表维护插入顺序或访问顺序，提供了一种既高效又有序的键值对存储结构。它保留了 HashMap 的快速查找和插入性能，同时允许用户按特定顺序访问元素，适用于各种需要顺序访问的场景。

TreeMap

TreeMap

TreeMap 是 Java 集合框架中的一种基于红黑树实现的有序映射（map），它按照键的自然顺序或者通过指定的比较器对键进行排序。

基于红黑树的实现

TreeMap 的底层数据结构是红黑树（Red-Black Tree），这是一种自平衡的二叉搜索树。红黑树保证了以下特性：

1. 节点是红色或黑色：每个节点都是红色或黑色。
2. 根是黑色：树的根节点必须是黑色。
3. 红色节点不能有红色父节点：红色节点的子节点必须是黑色（即不能有两个连续的红色节点）。
4. 每个叶子节点（NIL节点）都是黑色：叶子节点（空节点）是黑色。
5. 从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点：这确保了树的平衡性。

由于红黑树的性质，TreeMap 能够在 O(log n) 时间内完成插入、删除和查找操作。

排序特性

TreeMap 会根据键的自然顺序（通过 Comparable 接口）或指定的顺序（通过 Comparator 接口）对键进行排序。因此，TreeMap 是一种有序的映射（map），键值对按照键的顺序进行排列。

键必须实现 Comparable 接口或提供 Comparator

为了确保键的顺序，TreeMap 要求所有键必须实现 Comparable 接口，或者在创建 TreeMap 时提供一个 Comparator 对象。以下是两种方式的示例：

1. 键实现 Comparable 接口：

import java.util.TreeMap;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>();
        treeMap.put("apple", 1);
        treeMap.put("banana", 2);
        treeMap.put("cherry", 3);

        System.out.println(treeMap);
        // 输出: {apple=1, banana=2, cherry=3}
    }
}

2. 提供 Comparator 对象：

import java.util.TreeMap;
import java.util.Comparator;

public class TreeMapExample {
    public static void main(String[] args) {
        TreeMap<String, Integer> treeMap = new TreeMap<>(Comparator.reverseOrder());
        treeMap.put("apple", 1);
        treeMap.put("banana", 2);
        treeMap.put("cherry", 3);

        System.out.println(treeMap);
        // 输出: {cherry=3, banana=2, apple=1}
    }
}

使用场景

• 需要有序的键值对：当需要按自然顺序或自定义顺序访问键值对时，TreeMap 是一种合适的选择。例如，存储有序的配置数据或成绩单等。
• 频繁的范围查询：由于 TreeMap 是有序的，进行范围查询（如查找所有键在特定范围内的键值对）非常高效。
• 实现排序功能：当需要自动排序和保持排序顺序时，TreeMap 可以很方便地满足这些需求。

性能分析

TreeMap 的时间复杂度如下：

• 插入、删除、查找：O(log n)
• 范围查询：O(log n) 时间找到起始节点，然后 O(k) 迭代 k 个范围内的元素

在大量数据的情况下，TreeMap 的性能依赖于红黑树的平衡性，相比于无序集合（如 HashMap），插入和删除操作稍慢，但其有序性和范围查询能力使其在特定场景下非常有用。

最佳实践

• 选择合适的排序方式：根据具体需求选择自然排序（键实现 Comparable）或自定义排序（提供 Comparator）。
• 避免在频繁变更数据的情况下使用 TreeMap：如果数据频繁插入和删除，且不需要有序访问，考虑使用 HashMap。
• 关注内存消耗：由于红黑树的实现，TreeMap 的内存开销通常比 HashMap 大，但提供了额外的排序功能。

注意事项

• 线程安全：TreeMap 不是线程安全的。如果需要在多线程环境中使用，请考虑使用 Collections.synchronizedSortedMap 方法或者使用 ConcurrentSkipListMap。
• 键不可变：键的排序依赖于键对象的 hashCode 和 compareTo 方法，因此键对象在存储到 TreeMap 后不应修改其影响排序的字段。

通过对 TreeMap 的深入理解，可以在需要有序映射的场景下有效地使用它。

ConcurrentHashMap

ConcurrentHashMap 是 Java 集合框架中一种线程安全的哈希表实现，它允许并发访问，从而在多线程环境中提供更高的性能。

高并发实现

ConcurrentHashMap 通过减少锁的粒度来实现高并发。在 Java 7 之前，它使用了分段锁（Segment Locking）机制。在 Java 8 之后，这种实现方式被改进，改为使用 CAS 操作和更细粒度的锁。

分段锁机制（Java 7）

在 Java 7 及之前，ConcurrentHashMap 将整个哈希表分成若干个段（Segment），每个段都是一个独立的哈希表，并且拥有自己的锁。这样，当一个线程访问某个段时，不会阻塞其他线程访问其他段，从而提高并发性能。

具体实现如下：

• 整个哈希表被分为多个段，每个段是一个独立的哈希表。
• 对于每个段，操作是线程安全的，使用 ReentrantLock 来保证。
• 多线程可以同时访问不同的段，从而提高并发度。

CAS 操作和细粒度锁（Java 8）

在 Java 8 中，ConcurrentHashMap 的实现进行了重大改进，不再使用分段锁，而是采用 CAS 操作和细粒度锁（synchronized 锁）来提高并发性能。

具体实现如下：

• 使用 CAS（Compare-And-Swap）操作来保证原子性，避免了对整个数据结构的锁定。
• 只在必要时使用 synchronized 锁，锁的粒度更小，例如在链表或树的节点上加锁。
• 使用了 Node、TreeNode 和 TreeBin 等内部类来实现链表和红黑树结构，以处理哈希冲突。

CAS（Compare-And-Swap）操作
CAS 是一种无锁算法，用于实现多线程间的同步。其基本思想是对一个变量进行操作前先比较它的值，如果它的值等于预期值，就交换它的值。CAS 操作是一个原子操作，它包含三个操作数：

• V：需要更新的变量（内存地址）
• E：预期值
• N：新值
  操作步骤如下

1. 比较 V 和 E 的值，如果相等则将 V 的值设为 N。
2. 如果不相等，则说明该变量已经被其他线程修改过了，操作失败。
   CAS 通过硬件指令保证了操作的原子性，因此可以避免使用传统的锁机制。Java 中的 Unsafe 类提供了 CAS 的原子操作。

性能优势

ConcurrentHashMap 在高并发场景下具有显著的性能优势。主要表现在以下几个方面：

• 高并发访问：多个线程可以同时访问不同的键值对，而不会发生阻塞，极大地提高了并发度。
• 锁粒度小：通过分段锁机制（Java 7）或细粒度锁和 CAS 操作（Java 8），减少了锁的粒度，从而减少了锁竞争。
• 非阻塞算法：使用 CAS 操作保证了一些关键操作的原子性，避免了不必要的锁定，提高了性能。

使用场景

ConcurrentHashMap 适用于以下场景：

• 多线程环境：需要线程安全的哈希表，并且对性能要求较高的场景，如缓存、计数器、会话存储等。
• 高并发读写：适合读多写少的场景，因为它对读操作没有锁定，对写操作也进行了优化。
• 分布式系统：在分布式系统中用作共享状态或数据存储，可以有效减少锁竞争，提高系统吞吐量。

示例代码

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

        // 添加元素
        map.put("apple", 1);
        map.put("banana", 2);

        // 读取元素
        Integer value = map.get("apple");
        System.out.println("Value for apple: " + value);

        // 删除元素
        map.remove("banana");

        // 遍历元素
        map.forEach((key, val) -> System.out.println(key + ": " + val));
    }
}

最佳实践

• 避免过度同步：ConcurrentHashMap 已经实现了高效的并发访问，尽量避免在外部对其进行额外的同步操作。
• 合理初始化容量：在创建 ConcurrentHashMap 时，合理设置初始容量和负载因子，可以减少扩容操作，提高性能。
• 使用合适的并发级别：并发级别（concurrency level）在 Java 7 中可以指定，用于确定分段数，但在 Java 8 之后这个参数被移除了。

注意事项

• 键和值的不可变性：尽量使用不可变对象作为键和值，以保证线程安全。
• 避免长时间持有锁：避免在持有锁时进行耗时操作，例如 IO 操作或复杂计算。
  • ⚠️ 存疑：获取锁和释放锁都是ConcurrentHashMap管理，用户怎么可能干涉

CAS in java

CAS是思想，Java中实现此思想的类是Unsafe类。
因此如果要具体讨论ConcurrentHashMap中哪里用到了CAS，那就是所有调用Unsafe静态方法的位置

ConcurrentHashMap 是 Java 中一个线程安全的哈希表实现，设计用于在高并发环境中提供高性能的键值对存储。Java 8 之前的 ConcurrentHashMap 使用分段锁机制，而从 Java 8 开始，ConcurrentHashMap 采用了更加高效的 CAS（Compare-And-Swap）操作来保证原子性，避免对整个数据结构的锁定。

CAS（Compare-And-Swap）操作

CAS 是一种无锁算法，用于实现多线程间的同步。其基本思想是对一个变量进行操作前先比较它的值，如果它的值等于预期值，就交换它的值。CAS 操作是一个原子操作，它包含三个操作数：

• V：需要更新的变量（内存地址）
• E：预期值
• N：新值

操作步骤如下：

1. 比较 V 和 E 的值，如果相等则将 V 的值设为 N。
2. 如果不相等，则说明该变量已经被其他线程修改过了，操作失败。

CAS 通过硬件指令保证了操作的原子性，因此可以避免使用传统的锁机制。Java 中的 Unsafe 类提供了 CAS 的原子操作。

Unsafe

Unsafe 类是 Java 中一个特殊且强大的类，它提供了访问和操作底层内存和对象的能力，这在标准 Java API 中通常是不可用的。Unsafe 类位于 sun.misc 包中，这意味着它并非公开API的一部分，而是属于内部实现细节，可能在不同JVM实现中有所不同，且不受向后兼容性承诺的保护。因此，尽管它提供了许多强大功能，但使用时需谨慎，以避免潜在的稳定性、安全性和移植性问题。

Unsafe 类的主要功能包括：

1. 直接内存访问：允许直接在堆外内存进行读写操作，这对于高性能数据结构（如Netty中的ByteBuf）尤其有用，因为它们避免了垃圾收集器的干扰。

2. 原子操作：提供了原子变量更新的底层实现，这对于并发编程非常重要，特别是在设计无锁数据结构时。

3. 对象字段偏移量：可以获取对象字段的内存偏移量，这在某些情况下可用于优化性能。

4. 指针操作：允许直接操作指针，尽管在Java中通常不使用指针，但在某些低级操作中可能会用到。

5. 内存屏障：提供了内存屏障操作，用于控制编译器和处理器的重排序行为，这对于实现高性能的并发算法至关重要。

6. 类加载器操作：可以绕过正常的类加载过程，直接加载类，但这通常不推荐，因为可能会破坏Java的安全沙箱。

如何获取 Unsafe 实例：

由于 Unsafe 类没有公共构造函数，因此不能直接实例化。可以通过反射来访问其静态成员 theUnsafe，如下所示：

import sun.misc.Unsafe;

public class UnsafeExample {
    public static void main(String[] args) {
        try {
            java.lang.reflect.Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
            theUnsafe.setAccessible(true);
            Unsafe unsafe = (Unsafe) theUnsafe.get(null);
            // 使用 unsafe 对象...
        } catch (NoSuchFieldException | IllegalAccessException e) {
            throw new Error(e);
        }
    }
}

然而，这种做法违反了Java的封装原则，并依赖于JVM实现的内部细节，因此在生产代码中应避免使用 Unsafe，除非确实需要其提供的底层能力，并且充分理解了相关的风险和后果。

CAS in ConcurrentHashMap

在 ConcurrentHashMap 中，CAS（Compare-And-Swap） 操作被广泛用于确保并发环境下的线程安全，特别是在扩容和初始化过程中。下面详细解释这两个场景中 CAS 的具体使用和原理。

桶的初始化

桶的初始化是 ConcurrentHashMap 的一个关键步骤。为了确保只有一个线程可以成功初始化桶，ConcurrentHashMap 使用了 CAS 操作。以下是桶初始化的具体实现示例：

private final Node<K, V>[] initTable() {
    Node<K, V>[] tab;
    while ((tab = table) == null || tab.length == 0) {
        if (casTable(null, new Node[DEFAULT_CAPACITY])) {
            // CAS 成功初始化桶
            return table;
        }
        // 如果 CAS 失败，则其他线程已经完成了初始化，此时可以直接返回
    }
    return tab;
}

在上述代码中：

1. 检查当前表是否已初始化：在进入 while 循环时，检查 table 是否为 null 或长度为 0。如果是，表示需要初始化。
2. CAS 初始化表：调用 casTable 方法，尝试使用 CAS 操作将 null 表替换为一个新的空表（new Node[DEFAULT_CAPACITY]）。如果当前表为 null 且 CAS 操作成功，说明当前线程成功初始化了表。
3. 检查 CAS 结果：如果 CAS 操作成功，直接返回初始化后的表；如果失败，则表示其他线程已经完成了初始化，跳出循环并返回表。

casTable 方法的实现如下：

private final boolean casTable(Node<K, V>[] expect, Node<K, V>[] update) {
    return UNSAFE.compareAndSwapObject(this, TABLE_OFFSET, expect, update);
}

在上述方法中，UNSAFE.compareAndSwapObject 是底层的 CAS 操作，用于将 table 从 expect（预期值）更新为 update（新值）。

扩容

扩容是 ConcurrentHashMap 另一个需要确保线程安全的关键操作。扩容过程同样利用了 CAS 操作来保证只有一个线程可以成功执行扩容。以下是扩容过程的简化示例：

private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
    int n = tab.length;
    if (nextTab == null) {
        try {
            nextTab = (Node<K, V>[])new Node[n << 1];
        } catch (Throwable ex) {
            // 扩容失败的处理
            throw new OutOfMemoryError("Requested array size exceeds VM limit");
        }
        nextTable = nextTab;
        transferIndex = n;
    }
    // 省略具体的扩容操作
}

final Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
    if (tab != null && nextTab != null) {
        int sc;
        while (nextTab == nextTable && table == tab &&
               (sc = sizeCtl) < 0) {
            if (casSizeCtl(sc, sc - 1)) {
                // 如果 CAS 操作成功，帮助扩容
                transfer(tab, nextTab);
                break;
            }
        }
        return nextTab;
    }
    return table;
}

private final boolean casSizeCtl(int expect, int update) {
    return UNSAFE.compareAndSwapInt(this, SIZECTL, expect, update);
}

在上述代码中：

1. 检查是否需要扩容：transfer 方法中，如果 nextTab 为 null，表示需要扩容，创建一个新的表，并将其赋值给 nextTable。
2. 帮助扩容：helpTransfer 方法用于其他线程帮助扩容。它通过 casSizeCtl 方法使用 CAS 操作尝试减少 sizeCtl 的值。如果 CAS 操作成功，表示当前线程参与扩容，调用 transfer 方法进行扩容。
3. CAS 更新 sizeCtl：casSizeCtl 方法使用 CAS 操作来更新 sizeCtl 的值，以确保扩容操作的原子性。

总结

CAS 操作在 ConcurrentHashMap 的初始化和扩容过程中起到了关键作用。通过 CAS 操作，ConcurrentHashMap 能够确保只有一个线程可以成功执行初始化或扩容操作，同时其他线程可以通过 CAS 结果检测到这些操作是否已完成，从而避免重复执行。这种机制提高了并发性能，减少了线程间的竞争和阻塞。