键值对Map-06

1.什么是 TreeMap?

TreeMap 是 Java 编程语言中的一个类，它实现了 SortedMap 接口，并且是 NavigableMap 接口的一个具体实现。它是一个基于红黑树数据结构的有序映射（键值对）集合，可以用来存储键值对，并根据键的自然顺序或自定义排序规则对键进行排序。

TreeMap 中的元素是按照键的顺序进行排序的，因此它是有序的。具体的排序顺序取决于键的比较方式。如果键的类型实现了 Comparable 接口，TreeMap 会使用键的自然顺序进行排序。如果键的类型没有实现 Comparable 接口，你也可以在构造 TreeMap 对象时提供一个 Comparator 对象来指定自定义的排序规则。

2.TreeMap 特点

TreeMap的主要特性包括:

1. 有序性：元素按照键的顺序进行排序，可以通过键的自然顺序或自定义比较器来实现。
2. 基于红黑树：TreeMap 底层使用红黑树这种自平衡二叉搜索树数据结构来存储键值对。这使得查找、插入和删除操作的时间复杂度为 O(log n)，保证了较高的性能。
3. 线程不安全：和 HashMap 一样，TreeMap 也不是线程安全的。如果在多线程环境中使用，需要考虑同步措施。
4. 支持导航方法：TreeMap 提供了许多导航方法，比如获取最小/最大键、获取小于/大于某个键的最接近键等等。

3.TreeMap 构造方法

使用 TreeMap 时，常见的构造方式如下：

TreeMap<K, V> treeMap = new TreeMap<>();

这将创建一个按键的自然顺序进行排序的 TreeMap。

如果要创建一个按照自定义排序规则排序的 TreeMap，可以使用带有 Comparator 参数的构造方法：

TreeMap<K, V> treeMap = new TreeMap<>(customComparator);

TreeMap 适用于需要在键的顺序上进行操作的场景，并提供了快速的查找和有序遍历能力。由于它基于红黑树实现，适用于大量数据的高效存储和操作。

4.说说 WeakHashMap?

• WeakHashMap 非同步，默认容量为 16，扩容因子默认为 0.75，底层数据结构为 Entry 数组（数组+链表）。
• WeakHashMap 中的弱引用 key 会在下一次 GC 被清除，注意只会清除 key，value 会在每次 map 操作中清除。
• 在 WeakHashMap 中强引用的 key 是不会被 GC 清除的。

5.ConcurrentSkipListMap

ConcurrentSkipListMap 是在 JDK 1.6 中新增的，为了对高并发场景下的有序 Map 提供更好的支持

它有几个特点:

• 高并发场景
• key 是有序的
• 添加、删除、查找操作都是基于跳表结构（SkipList）实现的
• key 和 value 都不能为 null

而跳表结合了树和链表的特点，其特性如下：

• 跳表由很多层组成；
• 每一层都是一个有序的链表；
• 最底层的链表包含所有元素；
• 对于每一层的任意一个节点，不仅有指向其下一个节点的指针，也有指向其下一层的指针；
• 如果一个元素出现在 Level n 层的链表中，则它在 Level n 层以下的链表也都会出现。

6.ConcurrentSkipListMap 结构

ConcurrentSkipListMap 用到了两种结构的节点。

Node 节点代表了真正存储数据的节点，包含了 key、value、指向下一个节点的指针 next：

static final class Node<K,V> {
  final K key;     // 键
  V val;           // 值
  Node<K,V> next;  // 指向下一个节点的指针
  Node(K key, V value, Node<K,V> next) {
    this.key = key;
    this.val = value;
    this.next = next;
  }
}

Index 节点代表了跳表的层级,层级节点，包含了当前节点 node、下一层 down、当前层的下一个节点 right：

static final class Index<K,V> {
  final Node<K,V> node;   // 当前节点
  final Index<K,V> down;  // 下一层
  Index<K,V> right;       // 当前层的下一个节点
  Index(Node<K,V> node, Index<K,V> down, Index<K,V> right) {
    this.node = node;
    this.down = down;
    this.right = right;
  }
}

如图所示，Node 节点将真实的数据按顺序链接起来，Index 节点组成了跳表中多层次的索引结构。