概述

TreeMap 是 Java 中基于 红黑树（Red-Black Tree） 实现的有序映射，支持自定义的排序规则。

不得不提，TreeMap 的代码读起来，既精简又优雅，很适合学习红黑树。

一、数据结构与节点定义

1. 节点类（Entry）

static final class Entry<K,V> implements Map.Entry<K,V> {
    K key;                 // 键
    V value;               // 值
    Entry<K,V> left;       // 左子节点
    Entry<K,V> right;      // 右子节点
    Entry<K,V> parent;     // 父节点
    boolean color = BLACK; // 颜色标记（默认黑色）

    Entry(K key, V value, Entry<K,V> parent) {
        this.key = key;
        this.value = value;
        this.parent = parent;
    }
}

概述

常用的 Set 实现类包括 HashSet、LinkedHashSet 和 TreeSet，它们基于不同的底层数据结构实现。

一、HashSet

实现原理

• 底层数据结构：基于 HashMap 实现，元素作为 HashMap 的键存储，值统一为 PRESENT（一个静态占位对象）。
• 无序性：元素的存储和遍历顺序不固定。
• 允许 null：允许存储一个 null 元素。

概述

LinkedHashMap 是 Java 中基于哈希表和双向链表实现的有序 Map，它继承自 HashMap，支持按插入顺序或访问顺序（如 LRU 缓存）遍历元素。

一、核心数据结构

1. 节点结构（Entry）

LinkedHashMap 的节点继承自 HashMap.Node，并扩展了双向链表的前驱（before）和后继（after）指针：

static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after; // 双向链表指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

概述

LinkedList 是 Java 集合框架中基于 双向链表 实现的列表，支持高效的头部和尾部操作，同时实现了 List 和 Deque 接口，可作为动态列表、队列或双端队列使用。

一、数据结构

1. 节点结构（Node）

每个节点包含数据（item）、前驱指针（prev）和后继指针（next）：

Stack与Deque的区别，以及为什么推荐使用Deque？

概述

在 Java 中，Stack 和 Deque 的设计差异反映了不同时期集合框架的理念。Stack 作为早期设计存在一些明显缺陷，而 Deque 接口的引入（Java 6）解决了这些问题并提供了更现代的替代方案。以下是它们的主要设计问题对比：

1. 继承关系与设计耦合

• Stack 的问题：
  Stack 直接继承自 Vector（一个线程安全的动态数组实现），导致其设计高度耦合于 Vector 的实现细节。

  • 违反「组合优于继承」原则：Stack 通过继承获得 Vector 的同步逻辑，但栈的逻辑（后进先出，LIFO）与动态数组的随机访问特性并不完全匹配。
  • 扩展性差：由于 Java 单继承的限制，Stack 无法灵活扩展其他类。

• Deque 的优势：
  Deque 是一个接口（如 ArrayDeque、LinkedList 是其实现），允许开发者根据需要选择底层数据结构，避免与具体实现耦合。

  • 例如：ArrayDeque 基于数组实现（高效随机访问），LinkedList 基于链表（高效插入删除）。

概述

ConcurrentHashMap 是 Java 并发编程中最重要的数据结构之一，其通过 CAS + synchronized 锁细化 和 多线程协同扩容 实现了高效的线程安全。

1. JDK 1.7 的分段锁（Segment）

   数据结构：

   • 将整个哈希表分成多个 Segment（默认 16 个），每个 Segment 是一个独立的哈希表，继承自 ReentrantLock。
   • 每个 Segment 内部结构与 HashMap 类似（数组 + 链表）。

   并发控制：

   • 锁分离：不同 Segment 的写操作互不干扰，锁粒度更细。
   • 读操作无锁：使用 volatile 保证可见性，读操作无需加锁。

2. JDK 1.8 的 CAS + synchronized

   数据结构：

   • 与 HashMap 类似，使用 数组 + 链表/红黑树。
   • Node 节点：链表节点使用 volatile 修饰 next 指针，保证可见性。

   并发控制：

   • CAS 操作：插入、删除时使用 CAS 保证原子性。
   • synchronized 锁单个桶：仅在哈希冲突时对链表头或树根加锁，锁粒度更细。

概述

HashMap 是基于数组 + 链表/红黑树实现的，支持自动扩容。

优点：高效的查找/插入(平均O(1)，最差O(n))、动态扩容、支持null键和null值

缺点：哈希冲突可能影响性能、线程不安全、内存占用较高

适合的场景：适合单线程高频查询场景

是否线程安全：HashMap是线程不安全的，如果需要线程安全，推荐使用 ConcurrentHashMap。用 Collections synchronizedMap() 也可以实现线程安全。

源码解析

1. 核心数据结构

概述

ArrayList 是基于数组实现的动态列表，支持自动扩容。

优点：高效的随机访问O(1)、动态扩容、内存连续

缺点：插入/删除性能较差O(n)、扩容开销较大、内存浪费（预留空间）

适合的场景：随机访问多、数据量变化小的场景。如果频繁插入/删除，推荐使用 LinkedList。

是否线程安全：ArrayList是线程不安全的，如果需要线程安全，可使用 CopyOnWriteArrayList 或 Collections.synchronizedList。

源码解析

本文结合 JDK 17 的源码展开，与其他版本相比变化不大。