java容器类

Java 主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection 接口又有 3 种子类型，List、Set 和 Queue，再下面是一些抽象类，最后是具体实现类，常用的有 ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap 等等。

集合框架是一个用来代表和操纵集合的统一架构。所有的集合框架都包含如下内容：

• **接口：**是代表集合的抽象数据类型。例如 Collection、List、Set、Map 等。之所以定义多个接口，是为了以不同的方式操作集合对象
• **实现（类）：**是集合接口的具体实现。从本质上讲，它们是可重复使用的数据结构，例如：ArrayList、LinkedList、HashSet、HashMap。
• **算法：**是实现集合接口的对象里的方法执行的一些有用的计算，例如：搜索和排序，这些算法实现了多态，那是因为相同的方法可以在相似的接口上有着不同的实现。

除了集合，该框架也定义了几个 Map 接口和类。Map 里存储的是键/值对。尽管 Map 不是集合，但是它们完全整合在集合中。

集合框架体系如图所示

Java 集合框架提供了一套性能优良，使用方便的接口和类，java集合框架位于java.util包中， 所以当使用集合框架的时候需要进行导包。

集合里不能直接存基本数据类型

Collection

Collection是一个接口，它是Set、List等容器的父接口

Collections是一个集合工具类，提供一系列的静态方法来辅助容器操作，这些方法包括对容器的搜索、排序、线程安全化等等。

List

列表的特征是其元素有序，可重复，有索引，下有ArrayList, LinkedList和Vector（一般不用）三类

ArrayList

底层结构：动态数组

方法	说明
add(E e)	将元素添加到列表末尾（高效）
add(int index, E element)	在指定位置插入元素，原位置及之后元素后移
addAll(Collection<? extends E> c)	将指定集合的所有元素追加到列表末尾
addAll(int index, Collection<? extends E> c)	从指定位置开始插入集合中的所有元素
get(int index)	获取指定位置的元素
set(int index, E element)	替换指定位置的元素，返回被替换的旧值
remove(int index)	删除指定位置的元素，返回被删除的元素
remove(Object o)	删除列表中第一个匹配的元素（按 .equals()）
removeAll(Collection<?> c)	删除列表中所有包含在指定集合中的元素
retainAll(Collection<?> c)	仅保留列表中也包含在指定集合中的元素
clear()	清空列表，移除所有元素
size()	返回列表中元素的个数
isEmpty()	判断列表是否为空（无元素）
contains(Object o)	判断列表是否包含指定元素（使用 .equals()）
indexOf(Object o)	返回指定元素首次出现的索引，未找到返回 -1
lastIndexOf(Object o)	返回指定元素最后一次出现的索引
toArray()	转换为 Object 数组
toArray(T[] a)	转换为指定类型的数组（推荐传入 new T[0]）
subList(int fromIndex, int toIndex)	返回 [fromIndex, toIndex) 的视图子列表（原列表修改会反映到子列表）
forEach(Consumer<? super E> action)	对每个元素执行指定操作（Java 8+）
removeIf(Predicate<? super E> filter)	删除满足条件的所有元素（Java 8+）
replaceAll(UnaryOperator<E> operator)	使用函数替换每个元素（Java 8+）
sort(Comparator<? super E> c)	根据指定比较器对列表排序（Java 8+）
clone()	返回 ArrayList 的浅拷贝（注意：非泛型安全）

• toArray() 总是返回 Object[]，不能直接转为 String[] 等具体类型（会抛 ClassCastException）。
• 而 toArray(new String[0]) 可以安全返回 String[]。底层使用优化的反射

💡 提示：

• ArrayList 是非线程安全的，适用于单线程环境。Vector虽然是线程安全的，但由于过度同步问题已经是遗留产物
• 底层基于动态数组，随机访问（get/set）时间复杂度为 O(1)，中间插入/删除为 O(n)。
• 所有索引均从 0 开始，toIndex 在 subList 等方法中表示不包含（左闭右开）。

LinkedList

底层数据结构是双链表

特有方法	说明
public void addFirst(E e)	在该列表开头插入指定的元素
public void addLast(E e)	将指定的元素追加到此列表的末尾
public E getFirst()	返回此列表中的第一个元素
public E getLast()	返回此列表中的最后一个元素
public E removeFirst()	从此列表中删除并返回第一个元素
public E removeLast()	从此列表中删除并返回最后一个元素

线程安全List

Collections.synchronizedList(List<T> list)

对任意 List（如 ArrayList）进行同步包装。

特点：

• 所有方法加 synchronized 锁（粗粒度锁）；
• 不是完全“开箱即用”：迭代时仍需手动同步；
• 性能一般，适用于低并发场景。

常用方法与普通 List 相同

迭代必须手动加锁：

synchronized (safeList) {
    for (String s : safeList) {
        // 安全遍历
    }
}
// 或
synchronized (safeList) {
    Iterator<String> it = safeList.iterator();
    while (it.hasNext()) { ... }
}

CopyOnWriteArrayList<E>

专为并发读多写少场景设计，最常用的线程安全 List。

特点：

• 读操作无锁，高性能；
• 写操作（add/remove/set）会复制整个数组，开销大；
• 迭代器基于创建时的快照，不会抛 ConcurrentModificationException；
• 适合监听器列表、配置缓存、白名单等场景。

常用方法（线程安全）

List<String> cowList = new CopyOnWriteArrayList<>();

cowList.add("A");           // 写：复制数组
cowList.remove("A");        // 写：复制数组
String first = cowList.get(0); // 读：无锁
int size = cowList.size();     // 读：无锁

// 遍历无需加锁
for (String s : cowList) {
    // 即使其他线程在修改，这里也不会报错
    // 但看到的是“遍历开始时”的快照
}

不支持 ListIterator 的 set()（因为不可变快照）；

因为遍历的是快照，在写操作发生之前已经开始遍历的线程，不会看到该写操作带来的变更。

内存占用高（写时存在新旧两个数组）。

Set

无序，不重复，无索引

其基本方法与collection接口类似:

方法名称	说明
public boolean add(E e)	把给定的对象添加到当前集合中(已存在返回false)
public void clear()	清空集合中所有的元素
public boolean remove(E e)	把给定的对象从当前集合中删除
public boolean contains(Object obj)	判断当前集合中是否包含指定对象
public boolean isEmpty()	判断当前集合是否为空
public int size()	返回集合中元素的个数 / 集合的长度

这里介绍三种遍历方法：

1. 迭代器
2. 增强for循环
3. lambda表达式

       lambda:
       ts.forEach(new Consumer<Integer>() {
            @Override
            public void accept(Integer integer) {
                System.out.println(integer);
            }
        });

HashSet

无序，不重复，无索引

• 底层采用哈希表存储数据
• 哈希表是一种对于增删改查性能都比较好的结构
• jdk8开始采用数组+链表+红黑树（新增）组成

哈希值是哈希表的灵魂，哈希值是对象的整数表现形式，是对象通过哈希函数计算出的一个整数。

• 使用hashCode方法计算出来的int类型整数
• 这个方法定义在Object类中，所有对象都可调用，默认使用地址值计算
• 一般情况下会重写hashCode方法，使用对象内部属性值进行计算

在小部分情况下，不同的属性值或地址值计算出来的hash值也有可能一样（哈希碰撞）

如何重写?

按下Alt + Insert，可以让idea生成equals()和hashCode()方法

   @Override
    public boolean equals(Object o) {
        if (o == null || getClass() != o.getClass()) return false;
        Student student = (Student) o;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

因为是数组+链表的方式，因此计算数组下标公式是:
int index = (数组长度 - 1) & 哈希值;

如果index重复，先比较属性值(调用equals()方法判断，因此需要重写)如果相同就舍弃，不同就会将新元素用链表挂在老元素下面。

当数组快满时会扩容，当链表长度大于8且数组长度大于64会转成红黑树

因此如果集合中存储的是自定义对象，必须重写hashCode和equals方法

三个问题:

1. 为什么HashSet遍历顺序和存入顺序不一样? ：因为遍历是按照index顺序遍历的，存入位置是按照hash值计算出来的
2. 为啥没索引：因为有链表存在，一个索引可能有多个数据，没必要
3. 去重机制：相同属性的对象计算得到的index是相同的，再加上equals方法避免哈希碰撞。

​

LinkedHashSet

有序，不重复，无索引

继承自HashSet，会保证数据的存储和取出的元素顺序一致每个元素又额外多了一个双链表机制记录存储顺序

要求去重且存取有序，才用LinkedHashSet

TreeSet

不重复，无索引，可排序

• 可排序：默认从小到大排序，底层红黑树

排序原理:
对于数值类型，默认按照从小到大排序

对于字符，字符串类型，按照ASCLL码表中数字升序进行排序

对于自定义类型，指定排序规则两种方式

1.实现Comparable接口，重写抽象方法compareTo，默认是这种，因为排序规则内聚于类本身，是很多api以及Array.sort的默认排序规则

  public class Student implements Comparable<Student> {
  	@Override
    public int compareTo(Student o) { // o表示已经在红黑树存在的元素
        return this.getAge() - o.getAge(); // 小的存左边
    }

2.比较器排序，创建TreeSet对象时，传递比较器Comparator指定规则

比如包装类String默认是按照字典序排序，那么如果想让短的在前，长的在后，一样长的比较字符，那么就需要传递比较器，因为包装类不是自定义类不能修改。方便快速，适合临时使用或临时更改排序规则

        TreeSet<String> ts = new TreeSet<>(new Comparator<String>() {
            @Override
            public int compare(String o1, String o2) {
                int i = o1.length() - o2.length();
                return i != 0 ? i : o1.compareTo(o2);
            }
        });
        // 推荐使用Lambda 表达式
        TreeSet<String> ts = new TreeSet<>((o1, o2) -> {
            int i = o1.length() - o2.length();
            return i != 0 ? i : o1.compareTo(o2);
        });

线程安全Set

ConcurrentHashMap.newKeySet()

• 高并发、无锁读、分段写；
• 支持高吞吐的 add / remove / contains；
• 迭代器是 弱一致性（weakly consistent）：不会抛 ConcurrentModificationException，可能看到部分修改，但不保证实时性；
• 内存效率高，无冗余包装。

创建方式：

Set<String> safeSet = ConcurrentHashMap.newKeySet();
// 或指定初始容量
Set<String> safeSet = ConcurrentHashMap.newKeySet(16);

常用方法

safeSet.add("A");           // 添加元素（若不存在）
safeSet.remove("A");        // 删除元素
boolean has = safeSet.contains("A"); // 高效查找
int size = safeSet.size();  // 注意：size() 是估算值，因为ConcurrentHashMap 为了高并发性能，不使用全局锁，而是将数据分成多个 segment（JDK 7）或 bin（JDK 8+），每个 bin 可以独立操作，因此 size() 可能略小于或大于实际值（比如某个 bin 正在插入但未完成计数）
safeSet.isEmpty(); // 清空元素

// 安全遍历
for (String s : safeSet) {
    // 可能看不到“刚刚”被其他线程添加的元素，但不会崩溃
}

Collections.synchronizedSet(Set<T>)

对任意 Set（如 HashSet）进行同步包装。

• 所有方法加 synchronized 锁（粗粒度）；
• 性能较差，仅适用于低并发；
• 迭代时必须手动加锁，否则可能出错或抛异常。

创建方式

Set<String> safeSet = Collections.synchronizedSet(new HashSet<>());

常见方法

safeSet.add("A");
safeSet.remove("A");
safeSet.contains("A");

注意迭代必须同步

synchronized (safeSet) {
    for (String s : safeSet) {
        
    }
}

ConcurrentSkipListSet（有序场景）

基于跳表（Skip List）实现的线程安全、有序 Set，相当于并发版 TreeSet。

• 元素按自然顺序或 Comparator 排序；
• 支持 first(), last(), headSet(), subSet() 等有序操作；
• 并发性能较好（无锁读 + CAS 写）；
• 适用于需要排序 + 并发的场景。

创建方式

Set<String> safeSet = new ConcurrentSkipListSet<>();
// 或自定义比较器
Set<String> safeSet = new ConcurrentSkipListSet<>(Comparator.reverseOrder());

适合需要排序 + 高并发读写的场景（如排行榜、时间窗口去重）。

Map

双列集合，键值对应，一个键值对java叫Entry对象

其实现类是HashMap<>，因此Map<> m = new HashMap<>

常见API，顶层接口

方法名称	说明
V put(K key, V value)	添加元素，重复会覆盖，返回被覆盖的值
V remove(objcet key)	根据键删除元素, 返回删除的值
void clear()	移除所有元素
boolean containsKey(Object key)	判断集合是否包含指定键
boolean containsValue(Object value)	判断集合是否包含指定的值
boolean isEmpty()	判断集合是否为空
int size()	集合的长度，键值的对数
Set<> keySet();	返回键集合
V putIfAbsent(K, V);	仅当键不存在才会插入,返回当前已存在的 value

• toArray() 总是返回 Object[]，不能直接转为 String[] 等具体类型（会抛 ClassCastException）。
• 而 toArray(new String[0]) 可以安全返回 String[]。底层使用优化的反射

遍历方式

• 键找值 keySet

Set<String> keys = map.keySet();
for(String a: map.keySet()){
	String value = map.get(key);
	System.out.println(key + "=" + value);
}

• 键值对遍历 entrySet();

先来介绍Entry:

   // Entry是一个键值对对象，键值对对象有getKey()和getValue()方法
        Map.Entry<String, String> entry;

for(Map.Entry<String, String> entry : mp.entrySet()){
            System.out.println(entry.getKey() + ":" + entry.getValue());
        }

HashMap

基本方法和Map一致，基础实现类

特点都是由键决定的:无序，不重复，无索引

底层原理和HashSet一样，都是哈希表结构，数组+链表+红黑树

LinkedHashMap

和LinkedList一样，有序，不重复，无索引

多一条双向链表记录存储顺序

TreeMap

底层同TreeSet，红黑树

由键决定特性，不重复，无索引，可排序。默认按照键的从小到大排序，也可自定义键的排序规则：

• 实现Comparable接口
• 创建集合时传递Comparator比较器对象，指定比较规则

线程安全Map

ConcurrentHashMap<K, V>

Java 并发包中最重要、最常用的线程安全 Map，适用于绝大多数高并发场景。

• 高并发读写：读操作无锁，写操作仅锁单个桶（bin）；
• 分段并发（JDK 8+ 使用 CAS + synchronized 锁单个 bin）；
• 弱一致性迭代器：遍历时不抛 ConcurrentModificationException，可能看不到“刚刚”插入的元素，但不会崩溃；
• size()、isEmpty() 是估算值（见前文解释）；
• 不支持 null 键或 null 值（会抛 NullPointerException）

常用方法

ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// 基础操作
map.put("A", 1);
map.get("A");           // 无锁，极快
map.remove("A");
map.containsKey("A");
map.containsValue(1);   // 慢！需遍历所有 bin

// 原子性复合操作（避免先查后改的竞态条件）
map.putIfAbsent("B", 2);        // 不存在才插入
map.replace("B", 3);            // 存在才替换
map.replace("B", 2, 3);         // 期望旧值为 2 才替换为 3
map.computeIfAbsent("C", k -> 4); // 若 key 不存在，计算并插入
map.computeIfPresent("C", (k, v) -> v + 1); // 若存在，更新
map.merge("D", 1, Integer::sum); // 不存在则设为1，存在则累加

// 批量操作（JDK 8+）
map.forEach((k, v) -> System.out.println(k + "=" + v));
map.replaceAll((k, v) -> v * 2);

// 安全遍历
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    // 弱一致性：可能看不到其他线程刚插入的元素
}

Collections.synchronizedMap(Map<K, V>)

对任意 Map（如 HashMap）进行同步包装。性能差

ConcurrentSkipListMap<K, V>（有序并发 Map）

基于跳表（Skip List）实现的线程安全、有序 Map，相当于并发版 TreeMap。

• 元素按键的自然顺序或 Comparator 排序；
• 支持范围查询：subMap(), headMap(), tailMap()；
• 并发性能较好（无锁读 + CAS 写）；
• 适用于需要排序 + 并发的场景。

常用方法

ConcurrentSkipListMap<Long, String> timeline = new ConcurrentSkipListMap<>();

timeline.put(System.currentTimeMillis(), "event1");
timeline.put(System.currentTimeMillis() + 1000, "event2");

// 获取最早事件
Map.Entry<Long, String> first = timeline.firstEntry();

// 获取时间戳 < t 的所有事件
NavigableMap<Long, String> past = timeline.headMap(t);