2.Java集合

LIst

ArrayList

Object[] 数组。

ArrayList 中可以存储任何类型的对象，包括
null 值。不过，不建议向
ArrayList 中添加
null 值，
null 值无意义，会让代码难以维护比如忘记做判空处理就会导致空指针异常。

ArrayList插入删除时间复杂度

对于插入：

头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。尾部插入：当
ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。

对于删除：

头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

将ArrayList变为线程安全的

new Collections.synchronaiedList(arrayList)vectornew copyOnWriteArrayList<>()

ArrayList具体来说线程不安全体现

并发修改导致数据覆盖（丢失）

步骤	Thread-A (添加元素A)	Thread-B (添加元素B)	数组状态	size值
1	执行 elementData[5] = A;		[ ..., A, ... ]	5
2	（准备执行 size+1）	执行 elementData[5] = B;	[ ..., B, ... ]	5
3	执行 size = 5 + 1; (结果6)		[ ..., B, ... ]	6
4		执行 size = 5 + 1; (结果6)	[ ..., B, ... ]	6

大小不准确（Size Mismatch）

扩容导致的数组越界或内部状态不一致（最复杂的问题）

ArrayList扩容机制

ArrayList的扩容机制可以概括为一句话：当需要添加新元素而当前数组已满时，它会创建一个更大的新数组，并将所有旧元素复制到新数组中。

触发条件：

当调用
add 方法，并且
size + 1 > elementData.length 时。当调用
ensureCapacity(minCapacity) 并且
minCapacity > elementData.length 时。

扩容公式：

新容量 = 旧容量 * 1.5 (即
oldCapacity + oldCapacity/2)。这是为了在空间浪费和频繁扩容之间取得平衡。

特殊情况处理：

从空数组初始化：第一次添加元素时，容量直接设为 10。扩容值不足：如果按1.5倍计算的新容量仍然不够，则直接使用所需的最小容量（比如调用
addAll 添加大量元素时）。容量上限：新容量不能超过
Integer.MAX_VALUE - 8（
MAX_ARRAY_SIZE），具体取决于JVM实现。

核心操作：


Arrays.copyOf(...)：这是扩容过程中性能开销最大的一步。它的时间复杂度是 O(n)，需要将旧数组的所有元素逐个复制到新数组。

计算新的扩容后的长度—>创建新数组—>复制到新数组—>修改引用—>扩容完成

LinkedList

双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

LinkedList插入删除时间复杂的

头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。

ArrayList和LinkedList对比

是否保证线程安全：
ArrayList 和
LinkedList 都是不同步的，也就是不保证线程安全；底层数据结构：
ArrayList 底层使用的是
Object 数组；
LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）插入和删除是否受元素位置的影响：
ArrayList
采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)
方法的时候， ArrayList
会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)`），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（
add(E e)、
addFirst(E e)、
addLast(E e)、
removeFirst()、
removeLast()），时间复杂度为 O(1)，如果是要在指定位置
i 插入和删除元素的话（
add(int index, E element)，
remove(Object o),
remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
是否支持快速随机访问：
LinkedList 不支持高效的随机元素访问，而
ArrayList（实现了
RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于
get(int index)方法)。内存空间占用：
ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

Vector

“Object[]` 数组。线程安全

ArrayList和Array


ArrayList 内部基于动态数组实现，比
Array（静态数组） 使用起来更加灵活：


ArrayList会根据实际存储的元素动态地扩容或缩容，而
Array 被创建之后就不能改变它的长度了。
ArrayList 允许你使用泛型来确保类型安全，
Array 则不可以。
ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。
Array 可以直接存储基本类型数据，也可以存储对象。
ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如
add()、
remove()等。
Array 只是一个固定长度的数组，只能按照下标访问其中的元素，不具备动态添加、删除元素的能力。
ArrayList创建时不需要指定大小，而
Array创建时必须指定大小。

Set

HashSet(无序，唯一)

基于
HashMap 实现的，底层采用
HashMap 来保存元素。

LinkedHashSet

“LinkedHashSet
是HashSet
的子类，并且其内部是通过LinkedHashMap` 来实现的。

TreeSet(有序，唯一)

红黑树(自平衡的排序二叉树)。

Comparator和Comparable


Comparable 接口实际上是出自
java.lang包 它有一个
compareTo(Object obj)方法用来排序


Comparator接口实际上是出自
java.util 包它有一个
compare(Object obj1, Object obj2)方法用来排序

负数：当前对象 < 参数对象（排在前面）

零：当前对象 = 参数对象

正数：当前对象 > 参数对象（排在后面）

特性	Comparable	Comparator
包	java.lang	java.util
方法	compareTo(T o)	compare(T o1, T o2)
排序逻辑	自然排序（内置）	定制排序（外部）
影响类	修改类的本身	不修改原类
别称	内部比较器	外部比较器

import java.util.*;

public class ComparatorDemo {
    public static void main(String[] args) {
        List<Student> students = new ArrayList<>();
        students.add(new Student("张三", 85, 20));
        students.add(new Student("李四", 92, 19));
        students.add(new Student("王五", 78, 21));
        students.add(new Student("赵六", 85, 22)); // 同分数

        // 1. 按姓名升序排列
        Comparator<Student> byName = new Comparator<Student>() {
            @Override
            public int compare(Student s1, Student s2) {
                return s1.getName().compareTo(s2.getName());
            }
        };

        // 2. 按年龄升序排列（使用 Lambda 表达式）
        Comparator<Student> byAge = (s1, s2) -> s1.getAge() - s2.getAge();

        // 3. 复杂排序：先按分数降序，同分数按年龄升序
        Comparator<Student> byScoreThenAge = (s1, s2) -> {
            int scoreCompare = s2.getScore() - s1.getScore(); // 分数降序
            if (scoreCompare != 0) {
                return scoreCompare;
            }
            return s1.getAge() - s2.getAge(); // 年龄升序
        };

        System.out.println("按姓名排序：");
        students.sort(byName);
        students.forEach(System.out::println);

        System.out.println("
按年龄排序：");
        students.sort(byAge);
        students.forEach(System.out::println);

        System.out.println("
先按分数降序，同分按年龄升序：");
        students.sort(byScoreThenAge);
        students.forEach(System.out::println);
    }
}

class Student implements Comparable<Student> {
    private String name;
    private int score;
    private int age;

    public Student(String name, int score, int age) {
        this.name = name;
        this.score = score;
        this.age = age;
    }

    // 实现自然排序：按分数降序排列
    @Override
    public int compareTo(Student other) {
        // 分数高的排在前面
        return other.score - this.score;
        
        // 或者更清晰的写法：
        // if (this.score > other.score) return -1;
        // else if (this.score < other.score) return 1;
        // else return 0;
    }

    // Getter 方法
    public String getName() { return name; }
    public int getScore() { return score; }
    public int getAge() { return age; }

    @Override
    public String toString() {
        return name + "(" + score + "分)";
    }
}

HashSet,LinkedHashSet,TreeSet


HashSet、
LinkedHashSet 和
TreeSet 都是
Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
HashSet、
LinkedHashSet 和
TreeSet 的主要区别在于底层数据结构不同。
HashSet 的底层数据结构是哈希表（基于
HashMap 实现）。
LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。
TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。底层数据结构不同又导致这三者的应用场景不同。
HashSet 用于不需要保证元素插入和取出顺序的场景，
LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，
TreeSet 用于支持对元素自定义排序规则的场景。

特性	HashSet	LinkedHashSet	TreeSet
底层实现	HashMap	LinkedHashMap	TreeMap（红黑树）
排序保证	无顺序	插入顺序	自然排序或定制排序
性能	O(1)	O(1)	O(log n)
null 元素	允许一个 null	允许一个 null	不允许 null（除非自定义 Comparator）
线程安全	否	否	否
重复元素	不允许	不允许	不允许

Map

HashMap

JDK1.8 之前
HashMap 由数组+链表组成的，数组是
HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

遍历：

for(Map.Entry<String,Integer> entry : mymap.entrySet())mymap.forEach((k,v) -> {——–})Iterator i = map.iterator() -> i.next()

场景	时间复杂度	条件
理想情况	O(1)	良好的哈希函数，低冲突
一般情况	O(1)	正常的哈希分布
高冲突	O(log n)	JDK 8+，链表转红黑树
最坏情况	O(n)	所有key哈希冲突，且JDK 7或链表长度 ≤ 8

HashMap put过程

put(key, value)
       ↓
   hash(key)  // 计算哈希值，进行扰动
       ↓
   putVal()   // 核心方法
       ↓
判断 table 是否为空
   │          │
  空          非空
   ↓          ↓
 resize()   计算下标: i = (n-1) & hash
   ↓          ↓
创建数组      tab[i] 是否为空?
   │          │    │
   │          空   非空 → 哈希冲突!
   ↓          ↓        │
插入新节点    插入新节点   │
                      ↓
             判断第一个节点类型
                /      
          链表节点    树节点
             ↓          ↓
        遍历链表    调用树插入
        /              ↓
    找到key   未找到 → 尾插入
      ↓          ↓      ↓
    更新value  插入新节点 检查树化
       ↓          ↓      ↓
    返回旧值    检查扩容  可能树化

懒加载：HashMap 在第一次 put 时才初始化数组哈希扰动：通过
hashCode() ^ (hashCode() >>> 16) 减少冲突下标计算：
(n - 1) & hash，n 必须是 2 的幂解决冲突：链表 → 红黑树（链表长度 ≥ 8 且数组长度 ≥ 64）插入方式：JDK 1.8 使用尾插法，避免死循环扩容时机：元素数量 > 容量 × 负载因子(0.75)

第一阶段：哈希计算与扰动处理

当放入一个键值对时，HashMap首先会处理key的哈希值：

调用key的hashCode方法获得原始哈希值然后进行哈希扰动：将哈希值的高16位与低16位进行异或运算目的：让高位特征也参与到后续计算中，增加低位的随机性，减少哈希冲突如果key为null，其哈希值固定为0，这就是HashMap支持一个null key的原因

第二阶段：数组初始化检查

HashMap采用懒加载机制：

创建HashMap时，内部的数组并没有立即初始化在第一次执行put操作时，才会检查数组是否为空如果数组为空，则进行初始化resize()，默认创建大小为16的数组，并计算扩容阈值（16 × 0.75 = 12）

第三阶段：桶位定位与状态判断

通过
(数组长度 - 1) & 扰动后的哈希值 计算键值对应存放的数组位置（桶位）这个位运算相当于取模运算，但效率更高接着检查该位置当前的状态：
情况A：位置为空 → 直接创建新节点放入情况B：位置不为空 → 进入哈希冲突解决流程

第四阶段：哈希冲突解决（最核心的部分）

当目标位置不为空时，说明发生了哈希冲突，需要分情况处理：

情况1：首节点匹配

检查该位置的第一个节点，如果key的哈希值相同且key内容相等说明找到了相同的key，直接准备覆盖value值

情况2：红黑树节点

如果该位置已经转化为红黑树结构则按照红黑树的插入规则执行插入操作

情况3：链表遍历（JDK 1.8的重要改进）

如果是普通链表结构，则从头开始遍历链表在遍历过程中：
如果找到key相同的节点，则标记为覆盖操作如果遍历到链表尾部都没找到，则采用尾插法在链表末尾插入新节点
尾插法改进：JDK 1.8改为在链表尾部插入，避免了JDK 1.7头插法在多线程扩容时可能产生的死循环问题树化检查：插入新节点后，如果链表长度达到8，会检查数组长度：
如果数组长度 ≥ 64，则将链表转化为红黑树如果数组长度 < 64，则优先选择扩容来分散数据

第五阶段：后续处理

覆盖处理：如果是覆盖已有key的情况，会替换value并返回旧值新增处理：如果是新增节点，会：
增加修改计数（用于快速失败机制）增加元素总数检查当前元素数量是否超过扩容阈值如果超过阈值，则触发扩容操作

扩容机制

当元素数量超过容量 × 负载因子(0.75)时，会触发扩容：

创建一个新的数组，大小为原数组的2倍重新计算所有元素在新数组中的位置JDK 1.8的优化：元素在新数组中的位置要么保持不变，要么是原位置 + 原数组长度这个优化避免了重新计算哈希值，提升了扩容性能

两种扩容场景对比

特性	情况一：元素数量 > 容量 × 0.75	情况二：链表长度 ≥ 8 但数组长度 < 64
触发条件	全局元素总数超过阈值	单个桶的链表过长，但数组还较小
设计目的	避免整体哈希冲突加剧，保持操作效率	避免过早树化，尝试通过扩容分散数据
检查时机	每次成功插入新节点后	在链表尾部插入新节点且链表长度≥8时
扩容结果	数组容量 × 2，阈值 × 2	数组容量 × 2，阈值 × 2
性能影响	维护整体的O(1)时间复杂度	防止在数组较小时创建昂贵的红黑树

红黑树

红黑树的五大核心规则：

节点颜色：每个节点要么是红色，要么是黑色。根节点：根节点必须是黑色。叶子节点（NIL）：所有叶子节点（空节点）都是黑色。红色节点规则：任何红色节点的两个子节点都必须是黑色。（即：不能有两个连续的红色节点）黑色高度平衡：从任意一个节点到其所有后代叶子节点的所有路径上，包含的黑色节点数量必须相同。

核心思想：
规则5是确保平衡的关键。它保证了从根到最远叶子的路径不会超过根到最近叶子路径的两倍。这虽然不像平衡二叉树（AVL）那样严格平衡，但已经足够好，能避免严重的性能退化。

下面是详细的对比分析：

特性	红黑树	平衡二叉树（AVL树）	对HashMap的意义
平衡严格度	宽松平衡（只确保没有一条路径会大于其他路径的两倍）	严格平衡（每个节点的左右子树高度差绝对值不超过1）	关键区别
查询性能	平均 O(log n)，最坏情况比AVL稍慢	查询速度更快，始终保持在最优的 O(log n)	HashMap查询主要靠数组索引O(1)，树查询是冲突后的备用方案，频率相对较低。因此，查询的极致优化不是首要目标。
插入/删除性能	更快！平均O(1)次旋转。因为平衡要求宽松，插入和删除时需要的旋转操作更少。	较慢。平均O(1)次旋转，但可能更复杂。为了维持严格平衡，插入和删除时可能需要更多的旋转操作。	这是选择红黑树的核心原因。HashMap在put和remove操作时，如果遇到树化或拆分，频繁的插入删除性能至关重要。红黑树在这方面开销更小。
适用场景	适合频繁插入、删除的场景（例如，Java的HashMap，TreeMap；C++的std::map）	适合查询频繁，但插入删除较少的场景（例如，数据库索引的某些实现）	HashMap的桶在扩容时可能需要拆分树，这是一个涉及大量插入删除的操作，红黑树更适合。

LinkedHashMap

LinkedHashMap
继承自HashMap
，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap` 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。使迭代顺序与插入顺序一致

Hashtable

数组+链表组成的，数组是
Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的。

TreeMap

红黑树（自平衡的排序二叉树）。

HashMap和HashTable

线程是否安全：
HashMap 是非线程安全的，
Hashtable 是线程安全的,因为
Hashtable 内部的方法基本都经过
synchronized 修饰。（如果你要保证线程安全的话就使用
ConcurrentHashMap 吧！）；效率： 因为线程安全的问题，
HashMap 要比
Hashtable 效率高一点。另外，
Hashtable 基本被淘汰，不要在代码中使用它；对 Null key 和 Null value 的支持：
HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出
NullPointerException初始容量大小和每次扩充容量大小的不同： ① 创建时如果不指定容量初始值，
Hashtable 默认的初始大小为 11，之后每次扩充，容量变为原来的 2n+1。
HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。② 创建时如果给定了容量初始值，那么
Hashtable 会直接使用你给定的大小，而
HashMap 会将其扩充为 2 的幂次方大小（
HashMap 中的
tableSizeFor()方法保证，下面给出了源代码）。也就是说
HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方。底层数据结构： JDK1.8 以后的
HashMap 在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）时，将链表转化为红黑树（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树），以减少搜索时间（后文中我会结合源码对这一过程进行分析）。
Hashtable 没有这样的机制。哈希函数的实现：
HashMap 对哈希值进行了高位和低位的混合扰动处理以减少冲突，而
Hashtable 直接使用键的
hashCode() 值。

HashMap和HashSet


HashSet 底层就是基于
HashMap 实现的。（
HashSet 的源码非常非常少，因为除了
clone()、
writeObject()、
readObject()是
HashSet 自己不得不实现之外，其他方法都是直接调用
HashMap 中的方法。

HashMap和TreeMap

// TreeMap 中的核心节点类
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; // 节点颜色
    
    // 构造函数和其他方法...
}


TreeMap 和
HashMap 都继承自
AbstractMap ，但是需要注意的是
TreeMap它还实现了
NavigableMap接口和
SortedMap 接口。

实现
NavigableMap 接口让
TreeMap 有了对集合内元素的搜索的能力。


NavigableMap 接口提供了丰富的方法来探索和操作键值对:

定向搜索:
ceilingEntry(),
floorEntry(),
higherEntry()和
lowerEntry() 等方法可以用于定位大于等于、小于等于、严格大于、严格小于给定键的最接近的键值对。子集操作:
subMap(),
headMap()和
tailMap() 方法可以高效地创建原集合的子集视图，而无需复制整个集合。逆序视图:
descendingMap() 方法返回一个逆序的
NavigableMap 视图，使得可以反向迭代整个
TreeMap。边界操作:
firstEntry(),
lastEntry(),
pollFirstEntry()和
pollLastEntry() 等方法可以方便地访问和移除元素。

这些方法都是基于红黑树数据结构的属性实现的，红黑树保持平衡状态，从而保证了搜索操作的时间复杂度为 O(log n)，这让
TreeMap 成为了处理有序集合搜索问题的强大工具。

实现
SortedMap接口让
TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器

import java.util.*;

public class TreeMapDemo {
    public static void main(String[] args) {
        // 创建一个TreeMap
        NavigableMap<Integer, String> map = new TreeMap<>();
        
        // 添加一些数据
        map.put(10, "Apple");
        map.put(20, "Banana");
        map.put(30, "Cherry");
        map.put(40, "Date");
        map.put(50, "Elderberry");
        
        System.out.println("原始Map: " + map);
        
        // 1. 定向搜索方法
        System.out.println("
=== 定向搜索 ===");
        System.out.println("ceilingEntry(25): " + map.ceilingEntry(25)); // 大于等于25的最小键
        System.out.println("floorEntry(25): " + map.floorEntry(25));     // 小于等于25的最大键
        System.out.println("higherEntry(30): " + map.higherEntry(30));   // 严格大于30的最小键
        System.out.println("lowerEntry(30): " + map.lowerEntry(30));     // 严格小于30的最大键
        
        // 2. 子集操作
        System.out.println("
=== 子集操作 ===");
        System.out.println("subMap(20, true, 40, true): " + 
                          map.subMap(20, true, 40, true));  // [20,40]
        System.out.println("subMap(20, false, 40, true): " + 
                          map.subMap(20, false, 40, true)); // (20,40]
        System.out.println("headMap(30): " + map.headMap(30));           // 小于30的所有键
        System.out.println("tailMap(30): " + map.tailMap(30));           // 大于等于30的所有键
        
        // 3. 逆序视图
        System.out.println("
=== 逆序视图 ===");
        NavigableMap<Integer, String> descendingMap = map.descendingMap();
        System.out.println("descendingMap(): " + descendingMap);
        
        // 4. 边界操作
        System.out.println("
=== 边界操作 ===");
        System.out.println("firstEntry(): " + map.firstEntry());
        System.out.println("lastEntry(): " + map.lastEntry());
        
        // pollFirstEntry() 和 pollLastEntry() 会移除元素
        NavigableMap<Integer, String> tempMap = new TreeMap<>(map);
        System.out.println("pollFirstEntry(): " + tempMap.pollFirstEntry());
        System.out.println("pollLastEntry(): " + tempMap.pollLastEntry());
        System.out.println("移除首尾后的Map: " + tempMap);
    }
}

特性	HashMap	TreeMap
底层结构	数组 + 链表/红黑树	红黑树
排序方式	不保证顺序	按键的自然顺序或Comparator排序
null键	允许一个null键	不允许（除非Comparator支持）
null值	允许多个null值	允许多个null值
线程安全	不安全，需要Collections.synchronizedMap	不安全，需要Collections.synchronizedMap

操作	HashMap	TreeMap
插入 put()	平均O(1)，最坏O(n)	O(log n)
查找 get()	平均O(1)，最坏O(n)	O(log n)
删除 remove()	平均O(1)，最坏O(n)	O(log n)
包含 containsKey()	平均O(1)，最坏O(n)	O(log n)
遍历	O(n)	O(n)

HashMap与ConcurrentHashMap

特性	HashMap	ConcurrentHashMap
线程安全	非线程安全	线程安全
键/值	允许一个 null键和多个 null值	不允许 null键和 null值
迭代器	Fail-Fast，遍历时若被修改会快速失败，抛出 ConcurrentModificationException	Weakly Consistent（弱一致性），遍历时能容忍并发修改，不会抛出异常
实现原理	数组+链表/红黑树	分段锁（JDK 7） / CAS + synchronized

HashSet如何检查重复

用hashmap的put实现的，若之前无此元素则返回null，否则返回之前的那个元素，无论有无都直接插入

// Returns: true if this set did not already contain the specified element
// 返回值：当 set 中没有包含 add 的元素时返回真
public boolean add(E e) {
        return map.put(e, PRESENT)==null;
}

HahMap的长度为什么是2的幂次方

高效计算索引：位运算替代取模

扩容时元素重分布的优化

当HashMap扩容时（通常是2倍），元素需要重新计算位置。2的幂次方容量使得重分布变得非常高效。

扩容前：
index_old = hash & (oldLength - 1)
扩容后：
index_new = hash & (newLength - 1)

由于
newLength = 2 * oldLength，所以：


newLength - 1 比
oldLength - 1 只是高位多了一个1这意味着新的索引值只有两种可能：
保持不变：
index_new = index_old移动固定偏移：
index_new = index_old + oldLength

哈希分布的均匀性

容量计算的优化

HashMap多线程导致死循环

JDK1.7 及之前版本的
HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用
HashMap，因为多线程下使用
HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用
ConcurrentHashMap 。

HashMap为什么线程不安全

数据损坏
java1.7头插法容易导致死循环java1.8改为尾插法但仍容易导致数据覆盖
计数问题可见性问题

ConcurrentHashMap和HashTable


ConcurrentHashMap 和
Hashtable 的区别主要体现在实现线程安全的方式上不同。

底层数据结构： JDK1.7 的
ConcurrentHashMap 底层采用 分段的数组+链表 实现，在 JDK1.8 中采用的数据结构跟
HashMap 的结构一样，数组+链表/红黑二叉树。
Hashtable 和 JDK1.8 之前的
HashMap 的底层数据结构类似都是采用 数组+链表 的形式，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；

实现线程安全的方式（重要）：

在 JDK1.7 的时候，
ConcurrentHashMap 对整个桶数组进行了分割分段(
Segment，分段锁)，每一把锁只锁容器其中一部分数据（下面有示意图），多线程访问容器里不同数据段的数据，就不会存在锁竞争，提高并发访问率。

到了 JDK1.8 的时候，
ConcurrentHashMap 已经摒弃了
Segment 的概念，而是直接用
Node 数组+链表+红黑树的数据结构来实现，并发控制使用
synchronized 和 CAS 来操作。（JDK1.6 以后
synchronized 锁做了很多优化） 整个看起来就像是优化过且线程安全的
HashMap，虽然在 JDK1.8 中还能看到
Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本；


Hashtable(同一把锁) :使用
synchronized 来保证线程安全，效率非常低下。当一个线程访问同步方法时，其他线程也访问同步方法，可能会进入阻塞或轮询状态，如使用 put 添加元素，另一个线程不能使用 put 添加元素，也不能使用 get，竞争会越来越激烈效率越低。

ConcurrentHashMap线程安全的实现

jdk1.8之前：

首先将数据分为一段一段（这个“段”就是
Segment）的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据时，其他段的数据也能被其他线程访问。


ConcurrentHashMap 是由
Segment 数组结构和
HashEntry 数组结构组成。


Segment 继承了
ReentrantLock,所以
Segment 是一种可重入锁，扮演锁的角色。
HashEntry 用于存储键值对数据。

static class Segment<K,V> extends ReentrantLock implements Serializable {
}

一个
ConcurrentHashMap 里包含一个
Segment 数组，
Segment 的个数一旦初始化就不能改变。
Segment 数组的大小默认是 16，也就是说默认可以同时支持 16 个线程并发写。


Segment 的结构和
HashMap 类似，是一种数组和链表结构，一个
Segment 包含一个
HashEntry 数组，每个
HashEntry 是一个链表结构的元素，每个
Segment 守护着一个
HashEntry 数组里的元素，当对
HashEntry 数组的数据进行修改时，必须首先获得对应的锁。也就是说，对同一
Segment 的并发写入会被阻塞，不同
Segment 的写入是可以并发执行的。

jdk1.8:


ConcurrentHashMap 取消了
Segment 分段锁，采用
Node + CAS + synchronized 来保证并发安全。数据结构跟
HashMap 1.8 的结构类似，数组+链表/红黑二叉树。Java 8 在链表长度超过一定阈值（8）时将链表（寻址时间复杂度为 O(N)）转换为红黑树（寻址时间复杂度为 O(log(N))）。Java 8 中，锁粒度更细，
synchronized 只锁定当前链表或红黑二叉树的首节点，这样只要 hash 不冲突，就不会产生并发，就不会影响其他 Node 的读写，效率大幅提升

场景	Java 7 Segment	Java 8 Node+CAS+synchronized
空桶插入	需要获取Segment锁	CAS无锁操作
读操作	需要volatile读	完全无锁
锁粒度	Segment级别（较粗）	桶级别（极细）
并发度	固定（默认16）	理论上与桶数量相同
内存开销	较高（Segment结构）	较低

JDK 1.8 ConcurrentHashMap 的锁实现核心思想：

读操作完全无锁 – 依靠volatile保证可见性写操作细粒度锁 – 只锁单个桶的头节点CAS无锁化操作 – 用于初始化、空桶插入等场景多线程协助扩容 – 并行扩容提高效率

ConcurrentHashMap保证原子性吗


ConcurrentHashMap 是线程安全的，意味着它可以保证多个线程同时对它进行读写操作时，不会出现数据不一致的情况，也不会导致 JDK1.7 及之前版本的
HashMap 多线程操作导致死循环问题。但是，这并不意味着它可以保证所有的复合操作都是原子性的，一定不要搞混了！

复合操作是指由多个基本操作(如
put、
get、
remove、
containsKey等)组成的操作，例如先判断某个键是否存在
containsKey(key)，然后根据结果进行插入或更新
put(key, value)。这种操作在执行过程中可能会被其他线程打断，导致结果不符合预期。

例如，有两个线程 A 和 B 同时对
ConcurrentHashMap 进行复合操作，如下：

// 线程 A
if (!map.containsKey(key)) {
map.put(key, value);
}
// 线程 B
if (!map.containsKey(key)) {
map.put(key, anotherValue);
}

如果线程 A 和 B 的执行顺序是这样：

线程 A 判断 map 中不存在 key线程 B 判断 map 中不存在 key线程 B 将 (key, anotherValue) 插入 map线程 A 将 (key, value) 插入 map

那么最终的结果是 (key, value)，而不是预期的 (key, anotherValue)。这就是复合操作的非原子性导致的问题。

那如何保证
ConcurrentHashMap 复合操作的原子性呢？


ConcurrentHashMap 提供了一些原子性的复合操作，如
putIfAbsent、
compute、
computeIfAbsent 、
computeIfPresent、
merge等。这些方法都可以接受一个函数作为参数，根据给定的 key 和 value 来计算一个新的 value，并且将其更新到 map 中。

上面的代码可以改写为：

// 线程 A
map.putIfAbsent(key, value);
// 线程 B
map.putIfAbsent(key, anotherValue);

或者

// 线程 A
map.computeIfAbsent(key, k -> value);
// 线程 B
map.computeIfAbsent(key, k -> anotherValue);

很多同学可能会说了，这种情况也能加锁同步呀！确实可以，但不建议使用加锁的同步机制，违背了使用
ConcurrentHashMap 的初衷。在使用
ConcurrentHashMap 的时候，尽量使用这些原子性的复合操作方法来保证原子性。

Queue

PriorityQueue

“Object[]` 数组来实现小顶堆。

DelayQueue

“PriorityQueue`。

ArrayDeque

可扩容动态双向数组。

Queue和Deque


Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。


Deque 是双端队列，在队列的两端均可以插入或删除元素

ArrayDeque 和 LinkedList


ArrayDeque 和
LinkedList 都实现了
Deque 接口，两者都具有队列的功能，但两者有什么区别呢？


ArrayDeque 是基于可变长的数组和双指针来实现，而
LinkedList 则通过链表来实现。
ArrayDeque 不支持存储
NULL 数据，但
LinkedList 支持。
ArrayDeque 是在 JDK1.6 才被引入的，而
LinkedList 早在 JDK1.2 时就已经存在。
ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然
LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用
ArrayDeque 来实现队列要比
LinkedList 更好。此外，
ArrayDeque 也可以用于实现栈。

PriorityQueue


PriorityQueue 是在 JDK1.5 中被引入的, 其与
Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

这里列举其相关的一些要点：


PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
PriorityQueue 是非线程安全的，且不支持存储
NULL 和
non-comparable 的对象。
PriorityQueue 默认是小顶堆，但可以接收一个
Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue<Student> byScoreAsc = new PriorityQueue<>(
            new Comparator<Student>() {
                @Override
                public int compare(Student s1, Student s2) {
                    return s1.getScore() - s2.getScore(); // 升序
                }
            }
        );

BlockingQueue


BlockingQueue 是 Java 并发包中的一个重要接口，它表示一个线程安全的队列，支持在队列满时阻塞插入操作，在队列空时阻塞获取操作。它是生产者-消费者模式的经典实现。

1. BlockingQueue 核心特性


ArrayBlockingQueue：使用数组实现的有界阻塞队列。在创建时需要指定容量大小，并支持公平和非公平两种方式的锁访问机制。
LinkedBlockingQueue：使用单向链表实现的可选有界阻塞队列。在创建时可以指定容量大小，如果不指定则默认为
Integer.MAX_VALUE。和
ArrayBlockingQueue不同的是， 它仅支持非公平的锁访问机制。
PriorityBlockingQueue：支持优先级排序的无界阻塞队列。元素必须实现
Comparable接口或者在构造函数中传入
Comparator对象，并且不能插入 null 元素。
SynchronousQueue：同步队列，是一种不存储元素的阻塞队列。每个插入操作都必须等待对应的删除操作，反之删除操作也必须等待插入操作。因此，
SynchronousQueue通常用于线程之间的直接传递数据。
DelayQueue：延迟队列，其中的元素只有到了其指定的延迟时间，才能够从队列中出队。

ArrayBlockingQueue和LinkedBlockingQueue


ArrayBlockingQueue 和
LinkedBlockingQueue 是 Java 并发包中常用的两种阻塞队列实现，它们都是线程安全的。不过，不过它们之间也存在下面这些区别：

底层实现：
ArrayBlockingQueue 基于数组实现，而
LinkedBlockingQueue 基于链表实现。是否有界：
ArrayBlockingQueue 是有界队列，必须在创建时指定容量大小。
LinkedBlockingQueue 创建时可以不指定容量大小，默认是
Integer.MAX_VALUE，也就是无界的。但也可以指定队列大小，从而成为有界的。锁是否分离：
ArrayBlockingQueue中的锁是没有分离的，即生产和消费用的是同一个锁；
LinkedBlockingQueue中的锁是分离的，即生产用的是
putLock，消费是
takeLock，这样可以防止生产者和消费者线程之间的锁争夺。内存占用：
ArrayBlockingQueue 需要提前分配数组内存，而
LinkedBlockingQueue 则是动态分配链表节点内存。这意味着，
ArrayBlockingQueue 在创建时就会占用一定的内存空间，且往往申请的内存比实际所用的内存更大，而
LinkedBlockingQueue 则是根据元素的增加而逐渐占用内存空间。

————————————————-

如何选取集合

我们需要根据键值获取到元素值时就选用
Map 接口下的集合，需要排序时选择
TreeMap,不需要排序时就选择
HashMap,需要保证线程安全就选用
ConcurrentHashMap。

我们只需要存放元素值时，就选择实现
Collection 接口的集合，需要保证元素唯一时选择实现
Set 接口的集合比如
TreeSet 或
HashSet，不需要就选择实现
List 接口的比如
ArrayList 或
LinkedList，然后再根据实现这些接口的集合的特点来选用。

集合中的fail-safe和fail-fast

Fail-Fast（快速失败） 和 Fail-Safe（安全失败） 是两种不同的迭代器行为策略，主要区别在于在迭代过程中检测到并发修改时的处理方式。

fail-fast : 在迭代过程中，一旦检测到集合被修改（除了通过迭代器自身的修改方法），立即抛出
ConcurrentModificationException。

在
java.util包下的大部分集合是不支持线程安全的，为了能够提前发现并发操作导致线程安全风险，提出通过维护一个
modCount记录修改的次数，迭代期间通过比对预期修改次数
expectedModCount和
modCount是否一致来判断是否存在并发操作，

fail-safe:在迭代过程中，即使集合被修改，也不会抛出异常。迭代器基于集合的副本或快照工作。–copyonwrite

特性	Fail-Fast（快速失败）	Fail-Safe（安全失败）
抛出异常	检测到修改立即抛出 ConcurrentModificationException	永远不会抛出 ConcurrentModificationException
工作机制	使用 modCount 检查修改	使用副本/快照迭代
性能	迭代性能高	写操作性能低（需要复制）
内存使用	正常	较高（需要维护副本）
一致性	强一致性	弱一致性
使用场景	单线程环境，或明确知道不会并发修改	多线程并发环境
Java包	java.util	java.util.concurren

Copy-On-Write（写时复制） 的基本原理是：

读操作：直接读取，不需要加锁写操作：先复制整个数据集，在副本上修改，然后用副本替换原数据

---

| 永远不会抛出
ConcurrentModificationException |
| 工作机制 | 使用
modCount 检查修改 | 使用副本/快照迭代 |
| 性能 | 迭代性能高 | 写操作性能低（需要复制） |
| 内存使用 | 正常 | 较高（需要维护副本） |
| 一致性 | 强一致性 | 弱一致性 |
| 使用场景 | 单线程环境，或明确知道不会并发修改 | 多线程并发环境 |
| Java包 |
java.util |
java.util.concurren |

Copy-On-Write（写时复制） 的基本原理是：

读操作：直接读取，不需要加锁写操作：先复制整个数据集，在副本上修改，然后用副本替换原数据

---