02-Collection(20)

1. 简单介绍下集合类

  • 面试刚开始的时候被问，用于暖场热身，不需要说的那么详细
  • Java 集合从分类上看，有 collection 和 map 两种。前者是存储对象的集合类，后者存储的是键值对（key-value）
20220219202800.png

1. Collection

1. Set

  • 保证存储唯一（不重复），至于集合是有序还是无序，需要看具体实现类。eg：TreeSet有序，HashSet无序（Set是无序集合非常不准确）

2. List

  • 具体实现类ArrayList、LinkedList。区别在于底层实现不同，前者数组，后者双向链表 => 引申出《数组和链表的区别》

3. Queue

  • 队列，有序，严格遵守先进先出
  • 常用的实现类就是 LinkedList，实现了 Queue 接口
  • 优先队列，即 PriorityQueue，内部是基于数组构建的，自定义一个 comparator ，自定义对比规则，这个队列就是按这个规则来排列出队的优先级

2. Map

  • 存储的是键值对，也就是给对象（value）搞了一个 key，这样通过 key 可以找到那个 value
20220219202845.png
  • HashMap，无序
  • LinkedHashMap 和 TreeMap，前者里面搞了个链表，这样塞入顺序就被保存下来了，后者是红黑树实现了，所以有序

2. 数组、链表区别

  • 面试的一个热点！
  • 数组的内存是连续的，且存储的元素大小是固定的，实现上是基于一个内存地址，然后由于元素固定大小，支持利用下标的直接访问
  • 具体是通过下标（元素大小+内存基地址算出一个访问地址），然后直接访问，所以随机访问的效率很高O(1)
  • 内存连续这个特性，删除中间元素时就需要搬迁元素，进行内存拷贝，所以说删除的效率不高
20220219202821.png
  • 链表的内存不需要连续，通过指针相连，对内存的要求没那么高（数组的申请需要一块连续的内存），链表就可以散装内存，不过链表需要额外存储指针，所以总体来说，链表的占用内存会大一些
20220219202832.png
  • 由于是指针相连，所以无法随机访问一个元素，必须从头（如双向链表，可尾部）开始遍历，所以随机查找的效率不高O(n)
  • 删除的效率高，只需要改变指针即可，没有额外的内存拷贝动作（删的前提是查询）

3. List哪些实现类

ArrayList 和 LinkedList，不是并发容器，线程不安全

ArrayList 是基于动态数组实现，因此它的特性与数组一致，随机访问很快，删除和插入相对比较慢

  • 随机访问时间复杂度为 O(1)
  • 插入和删除（除了在列表末尾）时间复杂度为 O(n)

LinkedList 是基于双向链表实现的，因此两端都能操作

  • 随机访问时间复杂度为 O(n)，需要遍历链表
  • 插入和删除时间复杂度为 O(1)

1. 扩展Vector

  • 基于动态数组实现，与 ArrayList 类似，但它是线程安全，所有方法都是同步的
  • 都加了 synchronized 锁，性能相对较低
image.png

2. 扩展CopyOnWriteArrayList

  • 基于动态数组实现，但所有可变操作（add()、set() 等）都会创建一个新的数组。
  • 运用了一个叫写时复制的技术，即当写的时候，再去复制
  • 线程安全的，适合在多线程环境中频繁读取、很少修改的场景。

3. 扩展AbstractList

  • 一个抽象类，实现了 List 接口的大部分方法，提供了基本的 List 功能
  • 扩展实现自己的列表，那么可以用它作为自定义列表实现的基础类，大大减少自定义成本

4. HashMap、HashTable区别

1. 线程安全性

  • HashMap：不是线程安全的。如果多个线程同时访问一个 HashMap，以下代码封装进行同步：
Map<String, String> map = Collections.synchronizedMap(new HashMap<>());
  • Hashtable：是线程安全的。所有的方法都加了锁，可以在多线程环境中使用

2. 性能

  • HashMap：由于没有同步开销，所以它的性能一般比 Hashtable 更好，尤其是在单线程环境
  • Hashtable：由于每个方法都进行同步，因此性能比 HashMap 差

3. null 值的处理

  • HashMap：允许一个 null 键和多个 null 值
HashMap<String, String> map = new HashMap<>();
map.put(null, "value");
map.put("key", null);
  • Hashtable：不允许 null 键和 null 值。如果将 null 键或值放入 Hashtable，会抛出 NullPointerException
Hashtable<String, String> hashtable = new Hashtable<>();
// hashtable.put(null, "value"); 	// 抛出 NullPointerException
// hashtable.put("key", null); 		// 抛出 NullPointerException

4. 其他

  • HashMap：默认初始容量为 16，负载因子为 0.75。使用 Iterator 遍历键值对，支持 fail-fast 机制，如果在遍历过程中结构发生变化，会抛出 ConcurrentModificationException
  • Hashtable：默认初始容量为 11，负载因子为 0.75。使用 Enumeration 遍历键值对，不支持 fail-fast 机制
  • Hashtable 其实是过期的类，如果真的需要线程安全的容器，现在也都用 ConcurrentHashMap，因为它的加锁粒度更低，性能更好，Hashtable 基本没有使用场景

5. HashMap、HashSet区别

  • HashSet 其实内部的实现还是 HashMap
img
  • 并且 HashSet#add 方法实际上调用的就是 HashMap#put
img
  • value 默认填了个 PRESNET，实际上就是定义的一个 Object 没有任何意义，仅为了适配 map
img

6. HashMap实现原理

  • HashMap 基于哈希表的数据结构实现，允许存储键值对，并且通过键快速访问对应的值
  • 内部使用数组和链表（在 Java8 及以后还可以使用红黑树）来存储元素，每个数组槽位（bucket）对应一个链表或红黑树
  • 数组内的元素保存了 key 和 value。当要塞入一个键值对时，会根据一个 hash 算法计算 key 的 hash 值，然后通过数组大小 n-1 & hash 值之后，得到一个数组的下标，然后往那个位置塞入这键值对
image.png
  • hash 算法是可能产生冲突的，且数组的大小是有限的，所以很可能通过不同的 key 计算得到一样的下标，因此为了解决键值对冲突的问题，采用了链表法
20220219202856.png
  • 在 JDK1.7 及之前链表的插入采用的是头插法，即在链表的头部插入新的键值对
20220219202908.png
  • 在 JDK1.8 的时候，改成了尾插法，并且引入了红黑树
20220219202916.png
  • 当链表的长度大于 8 且数组大小大于等于 64 的时候，就把链表转化成红黑树，当红黑树节点小于 6 的时候，又会退化成链表
20220219202925.png

7. HashMap扩容机制

  • HashMap 是基于数组和链表（红黑树）来实现
  • 因为 hash 会有冲突，因此需要链表或红黑树来解决冲突，如果数据太多，冲突会越来越严重，即使树化了，访问的时间复杂度也不及 O(1)，此时就需要扩容了
  • HashMap 中有阈值的概念。eg：设置一个 16 大小的 map，那么默认的阈值等于 16 * 0.75 = 12。如果 map 中元素的数量超过 12，那么就会触发扩容。扩容的时候，默认会新建一个数组，新数组的大小是老数组的两倍。然后将 map 内的元素重新 hash 映射搬运到新的数组中
    • 1.7 的时，每一个元素应该是重新 hash 一个一个搬迁过去
    • 1.8 做了优化，关键点就在于数组的长度是 2 的次方，且扩容为 2 倍

通过 key 的 hash 值定位其在数组位置 (数组长度-1) & hash。16 和 32 长度举例：

16-1=15，二进制为 001111
32-1=31，二进制为 011111
  • JDK8 不需要每个节点重写 hash 算下标。中 key 的 hash 值的从右往左数第五位是否是 1，如果是 1 说明需要搬迁到新位置，且新位置的下标就是原下标+16（原数组大小），如果是 0 说明吃不到新数组长度的高位，那就还是在原位置，不需要迁移
  • 所以，刚好拿老数组的长度（010000）来判断高位是否是 1
84ea522f41a74a1fa32b83ae23ab5b23
  • 链表的数据是一次性计算完，然后一堆搬运的，因为扩容时候，节点的下标变化只会是原位置，或者原位置+老数组长度，不会有第三种选择

8. HashMap扩容2^n

基于 i = (n - 1) & hash 公式看待这个问题

1. 哈希分布均匀性

  • 数组容量为 2^n，那么 n - 1 后低位都是 1 ，此时进行 & （两个位都为 1 时，结果才为 1）运算可以确保哈希码的最低几位均匀分布
    • eg：64 二进制表示为 0100 0000，64 - 1 = 0011 1111
    • 此时 0011 1111 与哈希码进行 & 运算，低位能均匀的反应出哈希码的随机性
    • 假设来个 0100 0000 与哈希码进行 & 运算，那么低位得到的值就都是 0 了，随机性很差，都是冲突

2. 性能

  • 基于哈希码来计算数组下标，想到的都是 %（取余）计算。eg：数组长度为 5 ，那么哈希码 % 5 得到的值就是对应的数组下标
  • 相比于位运算而言，效率比较低，所以推荐用位运算，而要满足 i = (n - 1) & hash 这个公式，n 的大小就必须是 2 的 n 次幂。即：当 b 等于 2 的 n 次幂时，a % b 等于 a & ( b - 1 )

9. 默认扩容负载因子0.75

  • HashMap 的源码中有这么一段注释：
img
  • 简单理解下，就是设置 0.75 是因为空间和时间上的平衡。经过大量实践，0.75 被认为是大多数场景下比较合适的值，能够在时间和空间之间取得良好的平衡
    • 较低的负载因子（0.5）会导致 HashMap 需要频繁扩容，空间利用率就低。不过因为冲突少，查找效率就高，但是因为扩容频繁会增加 rehashing 的开销
    • 较高的负载因子（1.0）会减少扩容次数，空间利用率高了，但会增加哈希冲突的概率，从而降低查找效率

10. HashMap做红黑树改动

  • 主要是避免 hash 冲突导致链表的长度过长，这样 get 的时候时间复杂度严格来说就不是 O(1) 了，因为可能需要遍历链表来查找命中的键值对。

为什么定义链表长度为 8 且数组大小大于等于 64 才转红黑树？不要链表直接用红黑树不就得了吗？

258612459d5d420995e72cb172ab1d98
  • 因为红黑树节点的大小是普通节点大小的两倍，所以为了节省内存空间不会直接只用红黑树，只有当节点到达一定数量才会转成红黑树，这里定义的是 8
  • 为什么是 8 呢？这个其实 HashMap 注释上也有说的，和泊松分布有关系
    • 在默认阈值是 0.75 的情况下，冲突节点长度为 8 的概率为 0.00000006，也就概率比较小（毕竟红黑树耗内存，且链表长度短点时遍历的还是很快的）
    • 基于时间和空间的平衡了，红黑树占用内存大，所以节点少就不用红黑树，如果万一真的冲突很多，就用红黑树，选个参数为 8 的大小
693be12649e94916839e594c18896ab9

为什么节点少于 6 要从红黑树转成链表？

  • 为了平衡时间和空间，节点太少链表遍历也很快，没必要成红黑树，变成链表节约内存

为什么定了 6 而不是小于等于 8 就变？

  • 留个缓冲余地，避免反复横跳。毕竟树化和反树化都是有开销的。eg：一个节点反复添加，从 8 变成 9 ，链表变红黑树，又删了，从 9 变成 8，又从红黑树变链表

11. HashMap还有哪些改动

  1. hash 函数的优化
  2. 扩容 rehash 的优化
  3. 头插法和尾插法
  4. 插入与扩容时机的变更

1. hash函数优化

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

// 8实现
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
  • 1.7 的操作太多了，经历了四次异或，所以 1.8 优化了下，它将 key 的哈希码的高 16 位和低 16 位进行了异或，得到的 hash 值同时拥有了高位和低位的特性，使得哈希码的分布更均匀，不容易冲突
  • JDK 开发者根据速度、实用性、哈希质量所做的权衡来做的实现：
d7511b9960f3456887e0ce6535bdb339

2. 扩容rehash优化

3. 头插法、尾插法

  • 1.7 是头插法
    • 好处：插入时不需要遍历链表，直接替换成头结点
    • 缺点：扩容的时候会逆序，而逆序在多线程操作下可能会出现环，然后就死循环了
20220219203032.png
  • 1.8 是尾插法，每次都从尾部插入的话，扩容后链表的顺序还是和之前一致，所以不可能出现多线程扩容成环的情况

怀疑。因为 HashMap 本就不是线程安全的，还优化多线程的情况？开发者应该不会做这样的优化。没找到官方解答

4. 插入、扩容时机变更

  • 1.7 是先判断 put 的键值对是新增还是替换，如果是替换则直接替换，如果是新增会判断当前元素数量是否大于等于阈值，如果超过阈值且命中数组索引的位置已经有元素了，那么就进行扩容
    • 1.7 是先扩容，然后再插入
if ((size >= threshold) && (null != table[bucketIndex])) {
    resize(2 * table.length);
    hash = (null != key) ? hash(key) : 0;
    bucketIndex = indexFor(hash, table.length);
}
createEntry(...)
  • 1.8 则是先插入，然后再判断 size 是否大于阈值，若大于则扩容

就这么个差别，至于为什么，只是看源码发现了，具体的原因没查出来。个人觉得两者没差

12. LinkedHashMap的了解

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

  • 把 HashMap 的 Entry 加了两个指针：before 和 after
20220219203048.png
  • 把塞入的 Entry 之间进行关联，串成双向链表，下图红色的就是新增的两个指针：
20220219203058.png
  • 内部还有个 accessOrder 成员，默认是 false， 代表链表顺序是按插入顺序来排的，如果是 true 则会根据访问顺序来进行调整，就是咱们熟知的 LRU 那种，如果哪个节点访问了，就把它移到最后，代表最近访问的节点
  • 具体实现其实就是 HashMap 埋了几个方法，然后 LinkedHashMap 实现了这几个方法做了操作，比如以下
    • 访问节点之后干啥
    • 插入节点之后干啥
    • 删除节点之后干啥
f685d307d907410f866e9b55afcf4182
  • afterNodeInsertion 举例，埋在 HashMap 的 put 里，在塞入新节点之后，会调用这个方法
5d2b382f01a541e8a4613ccd71dc0511
  • LinkedHashMap 实现了这个方法，用来移除最老的节点
294812622e9e49659b035a59360b1220
  • 假如你想用 map 做个本地缓存，由于缓存的数量不可能无限大，所以就继承 LinkedHashMap 来实现，当节点超过一定数量的时候，在插入新节点的同时，移除最老最久没有被访问的节点，这样就实现了一个 LRU 了
    • 具体做法是把 accessOrder 设置为 true，这样每次访问节点就会把刚访问的节点移动到尾部，然后再重写 removeEldestEntry 方法，LinkedHashMap 默认的实现是直接返回 true
2d10f4bbf5554315a7baaaa7a710c424
 protected boolean removeEldestEntry(Entry<K, V> eldest) {
       return this.size() > this.maxCacheSize;
 }
  • 简单实现一个 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;
        }
    }

1. 实现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 我就没贴了，代码太长了
    }
}

13. TreeMap了解

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

基本特性：

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

1. 使用示例

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

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

public class TreeMapExample {
    public static void main(String[] args) {
        // 使用自然顺序
        TreeMap<Integer, String> treeMap = new TreeMap<>();
        treeMap.put(3, "Three");
        treeMap.put(1, "One");
        treeMap.put(2, "Two");
        System.out.println("TreeMap: " + treeMap);

        // 使用自定义比较器
        TreeMap<Integer, String> reverseTreeMap = new TreeMap<>(Comparator.reverseOrder());
        reverseTreeMap.put(3, "Three");
        reverseTreeMap.put(1, "One");
        reverseTreeMap.put(2, "Two");
        System.out.println("Reverse TreeMap: " + reverseTreeMap);

        // 获取子映射
        System.out.println("SubMap (1, 3): " + treeMap.subMap(1, 3));

        // 获取前缀映射
        System.out.println("HeadMap (2): " + treeMap.headMap(2));

        // 获取后缀映射
        System.out.println("TailMap (2): " + treeMap.tailMap(2));
    }
}

2. 红黑树知识

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

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

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

  1. 插入操作

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

  2. 删除操作

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

红黑树动态渲染open in new window

14. IdentityHashMap了解

Identity，它判断是否相等的依据不是靠 equals，而是对象本身是否是它自己。

  • 首先看它覆盖的 hash 方法：
20220219203206.png
  • 用了 System.identityHashCode(x)，而不是 x.hashCode()
  • 返回原来默认的 hashCode 实现，不管对象是否重写了 hashCode 方法
    • 默认的实现返回的值是：对象的内存地址转化成整数
20220219203221.png
  • 然后 get 方法：
    • 判断 key 是否相等并不靠 hash 值和 equals，而是直接用了 ==
    • 因此得知，IdentityHashMap 的中的 key 只认它自己（对象本身），即便伪造个对象，就算值都相等也没用，put 进去 IdentityHashMap 只会多一个键值对，而不是替换，这就是 Identity 的含义
71dbd1de5bc34baa9270f11425cc0eb5
// IdentityHashMap 会存在两个 Yes
Map<String, String> identityHashMap = new IdentityHashMap<>();
identityHashMap.put(new Yes("1"), "1");
identityHashMap.put(new Yes("1"), "2");
  • 为什么返回值是 tab[i+1]？
788ce6bcc8554d3aa951d48a96c80e8b
  • IdentityHashMap 的存储方式有点不一样，它是将 value 存在 key 的后面
20220219203238.png

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

15. WeakHashMap了解

WeakHashMap 是 Java 中的一种特殊的 Map 实现，它使用弱引用（WeakReference）来存储键。当一个键不再有任何强引用时，即使它被 WeakHashMap 引用着，垃圾回收器也可以回收该键和它对应的值。

  • 临时需要大量数据，但这些数据又可以因为内存吃紧随时被回收的场景
    • eg：一些缓存场景。缓存一些图片，当图片不再被其他部分引用时，可以被垃圾回收，从而避免内存泄漏

在一些框架中，需要为对象存储额外的元数据，但不希望这些元数据影响对象的生命周期。可以用 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);
    }
}

16. ConcurrentHashMap7和8区别

1. ConcurrentHashMap7

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

  • 差别就在于引入了一个 Segments 数组，看下大致的结构
20220219203435.png
  • 原理：先通过 key 的 hash 判断得到 Segment 数组的下标，将这个 Segment 上锁，然后再次通过 key 的 hash 得到 Segment 里 HashEntry 数组的下标，下面其实就是和 HashMap 一致了
  • 因此可以简化理解：每个 Segment 数组存放的就是一个单独的 HashMap
20220219203444.png
  • 上图我们有 6 个 Segment，那么等于有六把锁，因此共可以有六个线程同时操作这个 ConcurrentHashMap，并发度就是 6，相比于直接将 put 方法上锁，并发度就提高了，这就是分段锁
  • 具体上锁的方式来源于 Segment，这个类实际继承了 ReentrantLock，因此它自身具备加锁的功能

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

2. ConcurrentHashMap8

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

20220219203455.png
  • 思想的转变就是把粒度更加细化。不分段了，直接把 Node 数组的每个节点分别上一把锁，这样并发度不就更高了吗？
  • 并且 1.8 也不借助于 ReentrantLock 了，直接用 synchronized，这也侧面证明，都 1.8 了 synchronized 优化后的速度已经不下于 ReentrantLock 了
    • 具体实现思路也简单：当塞入一个值的时候，先计算 key 的 hash 后的下标，如果计算到的下标还未有 Node，那么就通过 cas 塞入新的 Node。如果已经有 node 则通过 synchronized 将这个 node 上锁，这样别的线程就无法访问这个 node 及其之后的所有节点
    • 然后判断 key 是否相等，相等则是替换 value ，反之则是新增一个 node，这个操作和 HashMap 是一样的。

3. 8的扩容

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

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

image.png

大致理解下就够了：

  • 扩容无非就是搬迁 Node，假设当前数组长度为 32，那就可以分着搬迁，31-16 这几个下标的 Node 都由线程 A 来搬迁，然后线程 B 来搬迁 15-0 这几个下标的 Node
  • 简单说就是会维护一个 transferIndex 变量，来的线程死循环 cas 争抢下标，如果下标已经分配完了，那自然就不需要搬迁了，如果 cas 抢到了要搬运的下标，那就去帮忙搬就好了

4. 8的size()

  • 还有 1.8 的 size 方法和 1.7 也不一样

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

  • 如果三次总数一样，说明当前数量没有变化，那就直接返回了。如果总数不一样，那说明此时有线程在增删 map，于是加锁计算，这时候其他线程就操作不了 map 了
if (retries++ == RETRIES_BEFORE_LOCK) {
       for (int j = 0; j < segments.length; ++j)
           ensureSegment(j).lock(); // force creation
}
   ...再累加数量

1.8 不一样，它就是直接计算返回结果

  • 具体采用的是类似 LongAdder 的思想，累加不再是基于一个成员变量，而是搞了一个数组，每个线程在自己对应的下标地方进行累加，等最后的时候把数组里面的数据统一一下，就是最终的值了
  • 所以这是一个分解的思想，分而治之
00bb6ddd1cc744999bdbd496b1fa4b8e

在 put 的时候，就会通过 addCount 方法维护 counterCells 的数量，当然 remove 的时候也会调用此方法

604047d015504edeb275d597a92a858c
  • 总而言之，就是平日的操作会维护 map 里面的节点数量，会先通过 CAS 修改 baseCount ，如果成功就直接返回，如果失败说明此时有线程在竞争，那么就通过 hash 选择一个 CounterCell 对象就行修改，最终 size 的结果就是 baseCount + 所有 CounterCell
  • 这种通过 CounterCell 数组来减少并发下场景下对单个成员变量的竞争压力，提高了并发度，提升了性能，这也就是 LongAdder 的思想

17. ConcurrentHM#get加锁

不需要加锁

  • 保证 put 的时候线程安全之后，get 的时候只需要保证可见性即可，而可见性不需要加锁
  • 具体是通过Unsafe#getXXXVolatile 和用 volatile 来修饰节点的 val 和 next 指针来实现的

18.CHM不支持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，这是不是就发生“误会”了?

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

19. 听过Copy-On-Write

  • 顾名思义，当需要 write 时 copy。底层基于数组存储，写的时候会拷贝一个新数组

操作系统有父子进程的概念，当父进程创建子进程后，父子进程的内存空间是共享的，只有当子进程（或父进程）尝试写入或修改数据时，才需要复制一个内存新页面写入

优点：

  • 一开始共享内存，所以在没有发生写入的时候，内存其实压根不需要新复制一份，当写入的时候才发生复制，这就不仅节省内存，也避免了内存频繁复制的开销
  • Copy-On-Write 线程安全的。对读比较友好，多个并发读可以共享，互相不会阻塞，且当有个写在修改数据的时候，也不会阻塞读，因为可以读老的数据，写是独占的

缺点：

  • 写操作会延迟，因为写的时候需要拷贝数据，这并不快
  • 写操作非常频繁就会一直拷贝数据，开销比较大，所以它适合读多写少的场景

20. ConcurentModificationException

ConcurentModificationException 这种错误有遇到过吗？为什么会出现这个错误？

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

  • 其实这个错误是为了检测并发修改的行为，在非线程安全的集合中，并发修改集合数据可能会发生数据丢失等一些奇怪的问题。因此 Java 引入了这个错误，是为了保证集合迭代时语义的一致性。
  • 原理：在集合内部维护了一个修改次数的记录，如果发生了修改，那么这个次数会增加。在每次迭代的时候会检查这个次数，发现增加了就立马抛错
  • 如果非要修改，那么可以使用线程安全的集合，eg：可以使用 Collections.synchronizedList 将 List 包装为线程安全的集合或直接使用 CopyOnWriteArrayList、ConcurrentHashMap

1. 单线程情况下修改集合

如果单线程在一个循环中遍历集合的同时直接修改集合也会报这个错，可以通过 Iterator 进行遍历，并使用 Iterator 提供的 remove 方法来删除元素，避免 ConcurrentModificationException

public class ConcurrentModificationExceptionExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        list.add("C");

        Iterator<String> iterator = list.iterator();
        while (iterator.hasNext()) {
            String s = iterator.next();
            if (s.equals("A")) {
                iterator.remove();  // 正确的删除方式
            }
        }

        System.out.println(list);  // 输出: [B, C]
    }
}