【Java】集合（二）

什么是 Java 的 LinkedHashMap？

LinkedHashMap 的父类是 HashMap，所以 HashMap 有的它都有，然后基于 HashMap 做了一些扩展。

首先它把 HashMap 的 Entry 加了两个指针：before 和 after。这目的已经很明显了，就是要把塞入的 Entry 之间进行关联，串成双向链表，如下图红色的就是新增的两个指针：

并且内部还有个 accessOrder 成员，默认是 false， 代表链表是顺序是按插入顺序来排的，如果是 true 则会根据访问顺序来进行调整，就是咱们熟知的 LRU 那种，如果哪个节点访问了，就把它移到最后，代表最近访问的节点。

具体实现其实就是 HashMap 埋了几个方法，然后 LinkedHashMap 实现了这几个方法做了操作，比如以下这三个，从方法名就能看出了：访问节点之后干啥；插入节点之后干啥；删除节点之后干啥。

假如你想用 map 做个本地缓存，由于缓存的数量不可能无限大，所以你就能继承 LinkedHashMap 来实现，当节点超过一定数量的时候，在插入新节点的同时，移除最老最久没有被访问的节点，这样就实现了一个 LRU 了。

具体做法是把 accessOrder 设置为 true，这样每次访问节点就会把刚访问的节点移动到尾部，然后再重写removeEldestEntry 方法，LinkedHashMap 默认的实现是直接返回 true。

这样就简单的实现一个 LRU 了！下面展示下完整的代码，非常简单：

private static final class LRUCache<K, V> extends LinkedHashMap<K, V> {
    private final int maxCacheSize;

    LRUCache(int initialCapacity, int maxCacheSize) {
        super(initialCapacity, 0.75F, true);
        this.maxCacheSize = maxCacheSize;
    }

    protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
        return this.size() > this.maxCacheSize;
    }
}

这里还能引申出一个笔试题，手写实现一个 LRU 算法，来我给你写！

public class LRUCache<K,V> {
    class Node<K,V> {
        K key;
        V value;
        Node<K,V> prev, next;
        public Node(){}
        public Node(K key, V value) {
            this.key = key;
            this.value = value;
        }
    }
    private int capacity;
    private HashMap<K,Node> map;
    private Node<K,V> head;
    private Node<K,V> tail;
    public LRUCache(int capacity) {
        this.capacity = capacity;
        map = new HashMap<>(capacity);
        head = new Node<>();
        tail = new Node<>();
        head.next = tail;
        tail.prev = head;
    }

    public V get(K key) {
        Node<K,V> node = map.get(key);
        if (node == null) {
            return null;
        }
        moveNodeToHead(node);
        return node.value;
    }

    public void put(K key, V value) {
         Node<K,V> node = map.get(key);
       if (node == null) {
            if (map.size() >= capacity) {
                map.remove(tail.prev.key);
                removeTailNode();
            }
            Node<K,V> newNode = new Node<>(key, value);
            map.put(key, newNode);
            addToHead(newNode);
        } else {
            node.value = value;
            moveNodeToHead(node);
        }
    }

    private void addToHead(Node<K,V> newNode) {
        newNode.prev = head;
        newNode.next = head.next;
        head.next.prev = newNode;
        head.next = newNode;
    }

    private void moveNodeToHead(Node<K,V> node) {
        removeNode(node);
        addToHead(node);
    }

    private void removeNode(Node<K,V> node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }

    private void removeTailNode() {
        removeNode(tail.prev);
    }

    public static void main(String[] args) {
        LRUCache<Integer,Integer> lruCache = new LRUCache<>(3);
        lruCache.put(1,1);
        lruCache.put(2,2);
        lruCache.put(3,3);
        lruCache.get(1);
        lruCache.put(4,4);
        System.out.println(lruCache); // toString 我就没贴了，代码太长了
    }
}

什么是 Java 的 TreeMap？

TreeMap 内部是通过红黑树实现的，可以让 key 的实现 Comparable 接口或者自定义实现一个 comparator 传入构造函数，这样塞入的节点就会根据你定义的规则进行排序。

基本特性：

• 数据结构：TreeMap 基于红黑树实现，红黑树是一种自平衡的二叉查找树，能够保证基本操作（插入、删除、查找）的时间复杂度为 O(log n)。
• 键的有序性：TreeMap 中的键是有序的，默认按自然顺序（键的 Comparable 实现）排序，也可以通过构造时提供的 Comparator 进行自定义排序。
• 不允许 null 键：TreeMap 不允许键为 null，但允许值为 null。

这个用的比较少，我常用在跟加密有关的时候，有些加密需要根据字母序排，然后再拼接成字符串排序，在这个时候就可以把业务上的值统一都塞到 TreeMap 里维护，取出来就是有序的。

扩展：红黑树

红黑树是一种自平衡二叉查找树，具有以下性质：

• 节点是红色或黑色。
• 根节点是黑色。
• 所有叶子节点（NIL 节点）是黑色。
• 红色节点的两个子节点都是黑色（从每个叶子到根的路径上不能有两个连续的红色节点）。
• 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

这些性质保证了红黑树的高度近似平衡，从而使得插入、删除、查找操作的时间复杂度保持在 O(log n)。

1）插入操作

• 新节点总是红色。
• 将新节点插入到树中。
• 进行修正，以保持红黑树的性质。这里可能会涉及到颜色的交换和旋转操作。

2）删除操作

• 找到要删除的节点。
• 删除节点后进行修正，以保持红黑树的性质。这里可能会涉及到颜色的交换和旋转操作。

关于红黑树动态渲染可以利用这个网站：https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

什么是 Java 的 IdentityHashMap？

理解这个 map 的关键就在于它的名字 Identity，也就是它判断是否相等的依据不是靠 equals，而是对象本身是否是它自己。

什么意思呢？

首先看它覆盖的 hash 方法：

可以看到，它用了个 System.identityHashCode(x)，而不是 x.hashCode()。

而这个方法会返回原来默认的 hashCode 实现，不管对象是否重写了 hashCode 方法

默认的实现返回的值是：对象的内存地址转化成整数，是不是有点感觉了？

然后我们再看下它的 get 方法：

可以看到，它判断 key 是否相等并不靠 hash 值和 equals，而是直接用了 == 。

而 == 其实就是地址判断！只有相同的对象进行 == 才会返回 true。

因此我们得知，IdentityHashMap 的中的 key 只认它自己（对象本身）。

即便你伪造个对象，就算值都相等也没用，put 进去 IdentityHashMap 只会多一个键值对，而不是替换，这就是 Identity 的含义。

这里眼尖的小伙伴发现代码里，为什么返回值是 tab[i+1]？

这是因为 IdentityHashMap 的存储方式有点不一样，它是将 value 存在 key 的后面。

认识到这就差不多了。它是一个非常特殊和有限用途的映射实现，主要用于需要引用相等性的场景。在一些框架中，代理对象可能需要根据实际对象实例进行映射，而不是逻辑相等的对象，这时候 IdentityHashMap 就派上用场了。

什么是 Java 的 WeakHashMap？

WeakHashMap 是 Java 中的一种特殊的 Map 实现，它使用弱引用（WeakReference）来存储键。

WeakHashMap 里对 key 的引用就是弱引用，所以当一个键不再有任何强引用时，即使它被 WeakHashMap 引用着，垃圾回收器也可以回收该键和它对应的值。

它被使用在临时需要大量数据，但这些数据又可以因为内存吃紧随时被回收的场景。

比如一些缓存场景，例如缓存一些图片，当图片不再被其他部分引用时，它们可以被垃圾回收，从而避免内存泄漏。

在一些框架中，需要为对象存储额外的元数据，但不希望这些元数据影响对象的生命周期。可以用 WeakHashMap 来存储这些元数据。

import java.util.Map;
import java.util.WeakHashMap;

public class WeakHashMapExample {
    public static void main(String[] args) {
        Map<String, String> weakMap = new WeakHashMap<>();
        String key1 = new String("key1");
        String key2 = new String("key2");

        // 放入键值对
        weakMap.put(key1, "value1");
        weakMap.put(key2, "value2");

        System.out.println("Before GC: " + weakMap);

        // 清除强引用
        key1 = null;

        // 触发垃圾回收
        System.gc();

        // 等待垃圾回收完成
        try {
            Thread.sleep(1000);
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // 打印 WeakHashMap 的内容
        System.out.println("After GC: " + weakMap);
    }
}

Java 中 ConcurrentHashMap 1.7 和 1.8 之间有哪些区别？

ConcurrentHashMap 1.7

其实大体的哈希表实现跟 HashMap 没有本质的区别，都是经过 key 的 hash 定位到一个下标，然后获取元素，如果冲突了就用链表相连。

差别就在于引入了一个 Segments 数组，我们来看下大致的结构。

原理就是先通过 key 的 hash 判断得到 Segment 数组的下标，将这个 Segment 上锁，然后再次通过 key 的 hash 得到 Segment 里 HashEntry 数组的下标，下面这步其实就是 HashMap 一致了，所以我说差别就是引入了一个 Segments 数组。

因此可以简化的这样理解：每个 Segment 数组存放的就是一个单独的 HashMap。

具体上锁的方式来源于 Segment，这个类实际继承了 ReentrantLock，因此它自身具备加锁的功能。

可以看出，1.7 的分段锁已经有了细化锁粒度的概念，它的一个缺陷是 Segment 数组一旦初始化了之后不会扩容，只有 HashEntry 数组会扩容，这就导致并发度过于死板，不能随着数据的增加而提高并发度。

ConcurrentHashMap 1.8

1.8 ConcurrentHashMap 做了更细粒度的锁控制，可以理解为 1.8 HashMap 的数组的每个位置都是一把锁，这样扩容了锁也会变多，并发度也会增加。

思想的转变就是把粒度更加细化。不分段了，我直接把 Node 数组的每个节点分别上一把锁，这样并发度不就更高了吗？

并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，这也侧面证明，都 1.8 了 synchronized 优化后的速度已经不下于 ReentrantLock 了。

具体实现思路也简单：当塞入一个值的时候，先计算 key 的 hash 后的下标，如果计算到的下标还未有 Node，那么就通过 cas 塞入新的 Node。如果已经有 node 则通过 synchronized 将这个 node 上锁，这样别的线程就无法访问这个 node 及其之后的所有节点。

然后判断 key 是否相等，相等则是替换 value ，反之则是新增一个 node，这个操作和 HashMap 是一样的。

扩容

1.8 的扩容，它允许协助扩容，也就是多线程扩容。

当 put 的时候，发现当前 node hash 值是 -1，则表明当前的节点正在扩容，则会触发协助扩容机制

其实大家大致理解下就够了：

扩容无非就是搬迁 Node，假设当前数组长度为 32，那就可以分着搬迁，31-16 这几个下标的 Node 都由线程 A 来搬迁，然后线程 B 来搬迁 15-0 这几个下标的 Node。

简单说就是会维护一个 transferIndex 变量，来的线程死循环 cas 争抢下标，如果下标已经分配完了，那自然就不需要搬迁了，如果 cas 抢到了要搬运的下标，那就去帮忙搬就好了，就是这么个事儿。

size

1.7 有个尝试的思想，当调用 size 方法的时候不会加锁，而是先尝试三次不加锁获取 sum。

如果三次总数一样，说明当前数量没有变化，那就直接返回了。如果总数不一样，那说明此时有线程在增删 map，于是加锁计算，这时候其他线程就操作不了 map 了。

而 1.8 不一样，它就是直接计算返回结果，具体采用的是类似 LongAdder 的思想，累加不再是基于一个成员变量，而是搞了一个数组，每个线程在自己对应的下标地方进行累加，等最后的时候把数组里面的数据统一一下，就是最终的值了。

所以这是一个分治的思想。

总而言之，就是平日的操作会维护 map 里面的节点数量，会先通过 CAS 修改 baseCount ，如果成功就直接返回，如果失败说明此时有线程在竞争，那么就通过 hash 选择一个 CounterCell 对象就行修改，最终 size 的结果就是 baseCount + 所有 CounterCell 。

这种通过 counterCell 数组来减少并发下场景下对单个成员变量的竞争压力，提高了并发度，提升了性能，这也就是 LongAdder 的思想。

get 方法是否需要加锁？

不需要加锁。

保证 put 的时候线程安全之后，get 的时候只需要保证可见性即可，而可见性不需要加锁。

为什么不支持 key 或 value 为 null？

首先，key 为什么也不能为 null ？

我猜测可能是因为如果允许 key 为 null 值，那么担心在并发条件下，其他 key 被意外置为 null 之后，导致访问到 null 对应的 value 而产生错误？

网上也没找到什么有说服力的答案（可能是作者 lea 佬不喜欢 null 值）。

那 value 为什么不能为 null ？

1）避免二义性

因为在多线程情况下，get 方法返回 null 时，无法区分 map 里到底是不存在在这个 key ，还是说被 put(key，null) 了。

这里可能有人会说，那 HashMap 不一样有这个问题？ HashMap 可以通过 containsKey 来判断是否存在这个 key，而多线程使用的 ConcurrentHashMap 就不能够。

比如你 get（key） 得到了 null，此时 map 里面没有这个 key 的，但是你不知道，所以你想调用 containsKey 看看，而恰巧在你调用之前，别的线程 put 了这个 key ，这样你 containsKey 就发现有这个 key，这是不是就发生“误会”了?

2）简化实现

不支持 null，这样在并发环境下，可以避免对 null 的特殊处理，可以减少代码中的条件分支，提高性能和可维护性。

你遇到过 ConcurrentModificationException 错误吗？它是如何产生的？

这个错误发生在迭代集合对象时候，修改集合本身内容，包括新增、修改和删除。

其实这个错误是为了检测并发修改的行为，在非线程安全的集合中，并发修改集合数据可能会发生数据丢失等一些奇怪的问题。

因此 Java 引入了这个错误，是为了保证集合迭代时语义的一致性。

简单来说就是：规矩就这样定了！这个集合非并发安全的，不让你改，改了就报错。

它的原理是在集合内部维护了一个修改次数的记录，如果发生了修改，那么这个次数会增加。在每次迭代的时候会检查这个次数，发现增加了就立马抛错。

如果非要修改那么可以使用线程安全的集合，例如可以使用 Collections.synchronizedList 将 List 包装为线程安全的集合或者直接使用 CopyOnWriteArrayList、ConcurrentHashMap。

Java 的 CopyOnWriteArrayList 和 Collections.synchronizedList 有什么区别？分别有什么优缺点？

CopyOnWriteArrayList：

是一个线程安全的 List 实现，特性就是写时复制。

每次对 List 的修改操作（如 add, set, remove）都会复制创建一个新的底层数组。读操作不需要加锁，写操作需要加锁。

优点：

• 读操作无锁：每次写操作都会创建并复制新数组，所以读写之间不冲突，因此读操作不需要加锁，能够提供非常高效的并发读性能。

缺点：

• 写操作开销大：每次写操作都会创建并复制新数组，且要将数据复制到新的数组中，在写操作频繁的场景下性能会较低。
• 内存消耗大：每次写操作都会创建并复制新数组，在数据量大的情况下，同一时刻会存在两倍 List 大小的内存占用，开销较大。

CopyOnWriteArrayList 适合读多写少的场景。

Collections.synchronizedList：

是一个包装方法，可以将任何 List 转换为线程安全的版本，它会对每个访问方法（如 get, set, add, remove）进行同步（加 synchronized 锁），从而保证线程安全。

优点：

• 方便：简单一个方法就可以将 List 变为线程安全版本，非常方便。

缺点：

• 并发低：读写操作都需要加锁，高并发场景下性能不高。

Collections.synchronizedList 适用于简单将 List 转为线程安全版本临时使用的场景。特定的场景还需使用并发度高的 JUC 类。