Java 入门指南：Java 并发编程 —— 并发容器 ConcurrentSkipListMap

ConcurrentMap

ConcurrentMap 是 Java 并发包中提供的一个接口，它继承了 java.util.Map 接口，专门用于支持高并发环境下的线程安全操作。ConcurrentMap 提供了一系列线程安全的方法，旨在解决在多线程环境下使用普通 Map 类型（如 HashMap）时可能出现的竞态条件和数据不一致问题。

ConcurrentMap 具有以下特点：

1. 线程安全性： ConcurrentMap 中的方法都是线程安全的，可以在多线程环境中安全地使用，无需额外的同步措施。

2. 高并发性能： ConcurrentMap 的设计目标是在高并发环境下提供高性能的操作，尤其适用于读多写少的场景。

3. 原子性操作：提供了一系列原子性操作，如 putIfAbsent、remove 等，这些操作在执行时不会被其他线程干扰。

常见实现

ConcurrentMap 接口有多种实现，其中最常见的是 ConcurrentHashMap。其他实现还包括 ConcurrentSkipListMap 等。

• ConcurrentHashMap：

  • 在 Java 8 之前，ConcurrentHashMap 使用了锁分段技术（segment-based locking），将哈希表分割成多个段，每个段有自己的锁，从而允许多个写入操作并发进行。
  • 在 Java 8 中，ConcurrentHashMap 采用了基于 CAS（Compare and Swap）操作的新实现，提供了更高的并发性能。

• ConcurrentSkipListMap：

  • 使用跳表（Skip List）作为底层数据结构，提供了有序的键值对存储，适合需要排序操作的场景。

方法

ConcurrentMap 接口提供了以下常用方法（除了一些 Map 基本方法）：

1. V get(Object key)：获取指定键对应的值，如果映射表中不存在该键，则返回 null。

2. V put(K key, V value)：将指定键值对插入到映射表中，如果这个键已经存在，则用新值替换旧值，并返回旧值。如果插入一个 null 的键或值，则抛出 NullPointerException。

3. putIfAbsent(K key, V value)：如果指定的键(key)不存在，则将键值对插入到映射表中；如果键已经存在，则不进行插入操作，并返回原先的值。

4. boolean remove(Object key, Object value)：如果指定的键值对存在，则从映射表中删除该键值对；否则不进行任何操作。

5. boolean replace(K key, V value)：替换指定键的值，无论该键原来的值是什么，都会执行替换操作。

6. boolean replace(K key, V oldValue, V newValue)：以原子方式将键值对由旧值替换为新值，即只有在该键原来的值和提供的旧值(oldValue)相等时，才会执行替换操作。。

7. int size()：返回映射表中键值对的数量。

8. V computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)：如果指定键没有关联值，将通过运行映射函数来计算一个新的值，并将该键关联到该计算值。

9. V computeIfPresent(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)：如果指定键已经具有相关联的值，则通过运行重新映射函数来计算一个新值，并将该键关联到该值。在计算过程中，更新可能会顺便修改现有映射，从而避免了常见的条件费用。

10. V compute(K key, BiFunction<? super K, ? super V, ? extends V> remappingFunction)：原子性的操作，它能够在并发环境中安全地更新或计算指定键的值。

    key：要更新或计算值的键。remappingFunction：用于更新或计算值的函数。

    remappingFunction 是一个在并发操作中被调用的函数，它接受两个参数：当前键的值（如果存在）和当前键。通过这个函数，可以基于当前的值来计算新的值。remappingFunction 的返回值将作为新的值存储在 ConcurrentHashMap 中，若返回 null，则会删除当前键。

11. void forEach(BiConsumer<? super K, ? super V> action)：对映射表中的每个键值对执行给定的动作。

12. V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction)：如果指定的键已存在，将其关联的值与给定的合并函数合并，如果不存在，则将其关联到给定值。

13. default V getOrDefault(Object key, V defaultValue)：获取指定键的值，如果键不存在，则返回默认值。可以用于避免空指针异常。

ConcurrentNavigableMap

ConcurrentNavigableMap 是 Java 并发包中的一个接口，它扩展了 ConcurrentMap 接口，并支持导航（查找和遍历）的功能。它允许多个线程同时访问和修改映射表，同时提供了按照键排序的功能。

ConcurrentNavigableMap 实现了一种有序的键值映射表，可以使用键的自然顺序或自定义的比较器对键进行排序。这些特性使得其特别适用于需要按照键进行范围查找和迭代的情况。

ConcurrentNavigableMap 的常见实现类是 ConcurrentSkipListMap，它基于跳表（Skip List）数据结构实现了 ConcurrentNavigableMap 接口。

常用方法

• lowerKey(K key): 返回小于给定键的最大键，如果不存在则返回 null。

• floorKey(K key): 返回小于等于给定键的最大键，如果不存在则返回 null。

• ceilingKey(K key): 返回大于等于给定键的最小键，如果不存在则返回 null。

• higherKey(K key): 返回大于给定键的最小键，如果不存在则返回 null。

• subMap(K fromKey, boolean fromInclusive, K toKey, boolean toInclusive): 返回一个包含指定范围的子映射。

• headMap(K toKey, boolean inclusive): 返回小于等于给定键的部分映射。

• tailMap(K fromKey, boolean inclusive): 返回大于等于给定键的部分映射。

• descendingMap(): 返回一个逆序的视图，按键的降序排列。

以上这些方法提供了对映射表进行范围查找和操作的能力。

ConcurrentSkipListMap

ConcurrentSkipListMap 是 Java 中的一个线程安全集合类，实现了ConcurrentMap 接口。它支持高效的插入、删除和查找操作，并提供了强一致性、线程安全的操作保证。

ConcurrentSkipListMap 底层基于跳表，每个节点包含一个键值对和多个指向下一个节点的指针。

在插入、删除、查找元素时，ConcurrentSkipListMap 会从节点的最高层级开始查找，并逐层降低层级，直到找到对应的节点或无法继续降低层级。可以在高并发环境下提供高效的查找、插入、删除操作，并且保证线程安全或强一致性。

ConcurrentSkipListMap 要求键必须实现 Comparable 接口或提供自定义的 Comparator 比较器，以便进行按键排序。

在使用 ConcurrentSkipListMap 时，需要注意元素的相等、哈希等条件，以确保操作的正确性。

特点

ConcurrentSkipListMap 的特性如下：

1. 线程安全：ConcurrentSkipListMap 支持多线程的并发访问，保证了线程安全性。

2. 有序键值对映射：ConcurrentSkipListMap 继承了 SortedMap 接口，保证了有序的键值对映射集合。

3. 可能存在重复的键：ConcurrentSkipListMap 可以存在相同的键，因此在插入键值对时需要注意。

4. 高效的插入、删除和查找操作：ConcurrentSkipListMap 采用跳表的数据结构，在高度平衡与高效性之间取得了一个良好的平衡，具有较高的速度。

构造方法

1. 创建一个空的 ConcurrentSkipListMap，使用键的自然顺序进行排序。

ConcurrentSkipListMap()

2. 创建一个空的 ConcurrentSkipListMap，使用指定的比较器对键进行排序。

ConcurrentSkipListMap(Comparator<? super K> comparator)

ConcurrentSkipListMap<String, Integer> map = new ConcurrentSkipListMap<>(Comparator.comparingInt(String::length));

3. 创建一个包含指定映射中所有映射关系的 ConcurrentSkipListMap

ConcurrentSkipListMap(Map<? extends K, ? extends V> m)

4. 创建一个与指定排序映射有相同映射关系的 ConcurrentSkipListMap。

ConcurrentSkipListMap(SortedMap<K, ? extends V> m)

常用方法

1. put(K key, V value)：将指定的键值对添加到映射中，如果键已经存在，则将其对应的值替换为新值。

2. remove(Object key)：从映射中移除指定键的键值对。

3. get(Object key)：获取给定键所对应的值，如果键不存在则返回null。

4. containsKey(Object key)：判断映射中是否包含指定的键，返回布尔值。

5. isEmpty()：判断映射是否为空，如果为空则返回true，否则返回false。

6. size()：返回映射中键值对的数量。

7. keySet()：返回一个包含映射中所有键的 Set 集合。

8. values()：返回一个包含映射中所有值的 Collection 集合。

9. entrySet()：返回一个包含映射中所有键值对的 Set 集合。

10. firstKey()：返回映射中的第一个键。

11. lastKey()：返回映射中的最后一个键。

12. subMap(K fromKey, K toKey)：返回一个子映射，包含所有在给定范围内的键值对。

13. headMap(K toKey)：返回一个子映射，包含所有小于给定键的键值对。

14. tailMap(K fromKey)：返回一个子映射，包含所有大于等于给定键的键值对。

15. clear()：清空映射，移除所有的键值对。

ConcurrentSkipListMap 使用示例

下面是使用 ConcurrentSkipListMap 的代码示例

import java.util.concurrent.ConcurrentSkipListMap;

public class ConcurrentSkipListMapExample {

    public static void main(String[] args) {
        // 创建一个 ConcurrentSkipListMap 实例
        ConcurrentSkipListMap<Integer, String> skipListMap = new ConcurrentSkipListMap<>();

        // 插入键值对
        skipListMap.put(3, "Three");
        skipListMap.put(1, "One");
        skipListMap.put(4, "Four");
        skipListMap.put(2, "Two");

        // 输出键值对
        System.out.println("Initial Map: " + skipListMap);

        // 获取键值对
        String value = skipListMap.get(3);
        System.out.println("Value of '3': " + value);

        // 判断是否存在键
        boolean contains = skipListMap.containsKey(5);
        System.out.println("Contains '5': " + contains);

        // 使用 putIfAbsent
        String newValue = skipListMap.putIfAbsent(5, "Five");
        System.out.println("Put or existing value of '5': " + newValue);

        // 使用 computeIfAbsent
        String computedValue = skipListMap.computeIfAbsent(6, k -> "Six");
        System.out.println("Computed value of '6': " + computedValue);

        // 使用 replace
        boolean replaced = skipListMap.replace(5, "Five", "New Five");
        System.out.println("Replaced '5' with 'New Five': " + replaced);

        // 遍历所有键值对
        skipListMap.forEach((key, val) -> System.out.println("Key: " + key + ", Value: " + val));

        // 使用 headMap 和 tailMap
        System.out.println("Head Map (up to 3): " + skipListMap.headMap(3));
        System.out.println("Tail Map (from 3): " + skipListMap.tailMap(3));

        // 使用 subMap
        System.out.println("Sub Map (from 2 to 4): " + skipListMap.subMap(2, 4));

        // 清空映射
        skipListMap.clear();
    }
}