Java集合--JCF

2025-05-07 12:11:26   0  举报





AI智能生成

Java集合框架（JCF）是Java编程语言的核心组件，提供了一套设计用于存储和操作对象集合的接口和类。这个框架旨在解决数据结构的组织和检索，包括各种列表（List）、集合（Set）、映射（Map）等数据结构。JCF不仅改善了代码的可重用性，也为Java开发者提供了一套可以预测且高效处理对象的工具。 Java集合框架中的核心接口包括`Collection`、`Set`、`List`、`Map`等。这些接口定义了相应类型的通用操作，允许开发者编写与具体实现无关的通用代码。具体实现类如`ArrayList`（实现了List接口）、`HashSet`（实现了Set接口）和`HashMap`（实现了Map接口），分别提供了高效的数组列表、集合映射和键值对映射功能。该框架主要定义在`java.util`包中，并广泛应用于各种应用场景，如数据处理、排序、搜索等。JCF在Java 1.2版本中引入，并从那时起一直是Java开发者不可或缺的资源，极大地简化了复杂的集合操作。此外，集合框架支持线程安全的实现，如`Vector`和`Hashtable`，以及更加灵活的并发集合，这些都归属于`java.util.concurrent`包，用于支持多线程编程。JCF的出现使得Java集合管理更为高效、方便，并为Java程序的数据操作提供了强大的支持。

java

后端开发

计算机技术

java面试必备

JAVA语言

作者其他创作

大纲/内容

List结构

List集合几个重要的接口

java.lang.Iterable

Iterable接口概述

定义与功能

表示可迭代对象

支持for-each循环

实现Iterable接口的类

集合框架中的类

常用方法

iterator()方法

返回Iterator对象

迭代器的使用

示例代码

遍历ArrayList

默认方法

forEach(Consumer action)

Spliterator spliterator()

stream()方法

应用场景

遍历集合

List、Set、Map的遍历

与增强for循环的结合

增强Foreach循环其实本质也是迭代器，且和Stream一样也是Split迭代器

与其他迭代方式的对比

Iterator与Enumeration 注意：Enumeration这种方式算一个遗留接口了，在新的集合中不会有这个接口的实现了

Iterator与Stream

Stream本质还是使用的迭代器便利的，区别点在于Stream使用的是Split迭代器

Iterable接口的实现

实现Iterable接口的步骤

定义类并实现Iterable接口

类的声明

实现iterator()方法

创建Iterator内部类

Iterator的hasNext()和next()方法

示例代码

常见错误与注意事项

未实现hasNext()或next()方法

抛出NoSuchElementException

多次调用next()未检查hasNext()

跳过或重复元素

示例代码与错误分析

Iterator的remove()方法实现

可选实现

注意事项与示例

Iterable接口的扩展

Guava库中的FluentIterable（没啥用了Java8之后推荐使用原生的Stream流）

FluentIterable简介

提供丰富的迭代操作

与Java 8 Stream API的对比

常用方法

filter(Predicate predicate)

transform(Function function)

concat(Iterable other)

示例代码

过滤集合元素

转换集合元素类型

合并两个集合

java.util.Collection
（JCF中的集合不一定实现该接口，但是实现了该接口一定是JCF中的集合）

Collection接口概述

基本功能

添加元素

add(E e)

addAll(Collection c)

移除元素

remove(Object o)

removeAll(Collection c)

检查元素

contains(Object o)

containsAll(Collection c)

遍历元素

迭代器遍历

iterator()

增强for循环遍历

for-each语法

遍历过程中修改集合

并发遍历

ConcurrentModificationException

如何安全遍历

java.util.AbstractList

AbstractList的基本特性

抽象类与接口的关系

继承自AbstractCollection

实现List接口

提供部分实现，减少子类工作

默认实现的方法

线程安全性

非线程安全

需要手动同步

使用Collections.synchronizedList包装

同步性能考虑

不可变性

不支持直接创建不可变列表

使用Collections.unmodifiableList包装

包装后的列表行为

LIst集合的分类

根据是否支持随机访问「支持随机访问的List时间复杂度为O(1)」

根据数据是否可修改权限进行分类，可以分为可修改LIst和不可修改List

根据容量不可变进行分类

java.util.RandomAccess

Marker Interface 标识接口，继承了该接口表示支持随机访问

Vector

基本组成

内部包括：
一个数组（elementData）、一个指向当前数组的可验证边界（elementCount）、一个数组扩容的参考值（capacityIncrement）

扩容机制

扩容时机

初始化的时候扩容

初始10，后续容量2倍

add()方法超出了容量上限的时候扩容

调用者明确重新确认 Vector容量的时候，也可能会扩容（重设容量值）

小于当前容量则会元素丢弃；反之则扩容

扩容实现

核心两个点：
1. Arrays.copyOf(elementData, newCapacity) 方法。【少则抛、多则填充NULL】
2. 计算新数组的容量

基本方法

set(int, E)

removeElementAt(int)

指定索引删除，该所有后置所有元素都要“移位”---这里是改变索引指向

ArrayList

ArrayList的基本概念

定义与用途

动态数组的实现

存储元素的容器

主要特性

动态扩容机制

扩容策略

扩容性能影响

元素有序性

插入顺序保持

访问效率

与数组的区别

固定大小 vs 动态大小

数组大小限制

ArrayList的灵活性

类型安全性

泛型支持

类型检查

ArrayList的操作方法

添加元素

add(E e)

末尾添加

返回值与异常处理

addAll(Collection c)

集合添加

重复元素处理

删除元素

remove(int index)

按索引删除

元素移动与更新

remove(Object o)

按值删除

null值处理

查找元素

get(int index)

按索引访问

边界检查

contains(Object o)

值查找

equals方法比较

遍历元素

Iterator iterator()

迭代器遍历

并发修改异常

forEach(Consumer action)

Lambda表达式遍历

自定义操作

ArrayList的内部实现

存储结构

Object[] elementData

默认容量

实际存储元素

扩容机制

ensureCapacityInternal(int minCapacity)

内部扩容逻辑

最小容量计算

grow(int minCapacity)

新容量计算

数组复制

元素存取

modCount修改计数器

修改次数记录

rangeCheck(int index)

索引范围检查

越界异常处理

ArrayList和Vector的对比

集合内部数据结构的对比

1. 内部都是一个数组，都叫elementData
2. Vector不指定容量默认会初始化为10；ArrayList默认不指定容量初始化的长度为0

扩容逻辑对比

容量不足都会自动扩容，Vector默认两倍，ArrayList默认扩容原始容量的百分之50

线程安全性保证对比

Vector中，提供对外的读/写方法都是object-monitor模式，用synchronized进行修饰
ArrayList中，并不支持线程安全的操作，如果强行并发的操作，那么会造成脏数据的问题（实际上ArrayList会在迭代器中通过modCount全局变量
标记的操作数来规避一些“脏读”的问题，是CAS思想的借鉴）

对序列化过程就进行对比

Vector没有对序列化进行特殊的处理，序列化的时候多余的索引位会被一起序列化，产生了不必要的开销
ArrayList 只会对elementData里面已经使用的索引位置进行序列化，当然，反序列化的时候也不会产生多余的容量

Stack

先进后出（LIFO）
可以看成是特殊的Vector，扩容一般情况下，也是增加1倍；支持线程安全的操作，但是不推荐高并发场景使用；序列化也没有优化处理

jdk1.6之后就不推荐了，如果不考虑并发场景则使用：java.util.ArrayDeque ; 如果考虑并发场景则使用：java.util.concurrent.LinkedBlockingDeque

LinkedList

LinkedList同时具备List集合和Queue集合的基本特性，1.6版本之前，官方推荐使用LinkedList集合模拟栈结构

LinkedList集合的主要结构

基本操作

插入

删除

查找

LinkedList栈工作的特性

LinkedList 和 ArrayList 对比！！

两种集合写性能的比较

ArrayList写操作的Case

不触发扩容，在末尾添加元素---此时性能是很高的

末尾添加元素，出发了扩容，这里会有较多的耗时
- 可以根据指定容量避免

数组指定索引位置添加元素，最差的是在0处添加元素，此时每添加一个元素都会将数组所有数据的位置向后移动
并且容量不足也同时会触发扩容。这种情况是最耗时的。
- 但是可以利用编程的角度避免，“正着插入，反着索引排序，反着读”

LinkedList写操作的Case

链头或者链尾进行添加元素，是非常快的 O(1)

指定索引位置添加元素，时间主要消耗在找指定索引位上，时间是O(n)

两种集合读操作性能的比较

ArrayList读

支持随机访问 O（1）

LinkedList读

如果头部和尾部进行读，有last属性和first属性标识，不存在查询的额外耗时
其他情况，都需要逐个遍历读取，但是LinkedList做了优化，可以根据size的大小决定从前半段开始还是后半段开始
最差的情况其实是，从中间的位置进行读取
总之，LinkedList的访问时间复杂度位 O（n）

不同形式的遍历操作，对于LinkedList的意义

fori 索引get遍历

性能最差，O（n方）

传统迭代器方式遍历

O（n）

Lambda Foreach遍历

本质使用可分割迭代器 Spliterator O（n）

增强For循环--传统for each循环

本质使用可分割迭代器 Spliterator O（n）

stream流提供的Foreach方法循环

本质使用可分割迭代器 Spliterator O（n）

什么场景推荐使用LinkedList？

集合的写操作元元大于读操作，并且写的操作不能用编程技巧规避

满足上面1条，并且还需要使用LinkedList结构的栈特性的，（栈结构特性推荐使用ArrayDeque）

Queue结构

ArrayDeque

内部结构

transient Object[] elements;

transient int head;

transient int tail;

扩容机制

private void grow(int needed) {
// overflow-conscious code
final int oldCapacity = elements.length;
int newCapacity;
// Double capacity if small; else grow by 50%
int jump = (oldCapacity < 64) ? (oldCapacity + 2) : (oldCapacity >> 1);
if (jump < needed
|| (newCapacity = (oldCapacity + jump)) - MAX_ARRAY_SIZE > 0)
newCapacity = newCapacity(needed, jump);
final Object[] es = elements = Arrays.copyOf(elements, newCapacity);
// Exceptionally, here tail == head needs to be disambiguated
if (tail < head || (tail == head && es[head] != null)) {
// wrap around; slide first leg forward to end of array
int newSpace = newCapacity - oldCapacity;
System.arraycopy(es, head,
es, head + newSpace,
oldCapacity - head);
for (int i = head, to = (head += newSpace); i < to; i++)
es[i] = null;
}
}

添加操作时，当tail==head，此时会触发扩容操作，循环队列的扩容不像是普通的copy那么简单，copy之后需要重新指正head的位置，从而使队列不是“满”的

堆和堆排序

树、二叉树

树的层次和树的深度

根节点的层次为1 其他层次依次+1
一个数所有节点层次的最大值就是这个树的深度

儿子节点、双亲节点

字面意思....

根节点

没有双亲节点的节点，就是这棵树的根节点

子树

如果一棵树中的节点存在儿子节点，儿子节点当做根节点向下其实就是子树

度、叶子节点、分支节点

以树中的节点任意节点为树的根节点，那么拥有的子树个数即这个树的度、度为0的节点称作为，叶子结点
度不为0的节点称之为分支节点

二叉树

一棵树中不存在大于2的度的节点

满二叉树

一颗深度为k的树，有2的k次方-1个结点，那么可以称之为这个树为满二叉树

完全二叉树

堆、小顶堆、大顶堆

堆的降纬-----使用数组标识堆结构

堆排序

PriorityQueue

基于堆数据结构的队列

Map结构

Map概述

映射式数据结构 K-V

内部是一个个的Map.Entry<K,V>的对象

重要的接口和抽象类

Map

SortedMap

NavigableMap

AbstractMap

子主题

红黑树

Map一些集合类的设计离不开红黑树数据结构，比如：TreeMap基于红黑树，HashMap，LinkedHashMap基于数组+链表+红黑树

为什么需要红黑树呢？

二叉查找树，本身已经具有良好的查询性能，只要不是极端的情况，基本可以控制在logn 但也会出现极端的情况，比如右倾or左倾
如果过渡不平衡，那么时间复杂度其实就是 N
所以为了避免上面的极端的情况，出现了红黑树，对二叉查找树引入一个平衡的约束
注意：红黑树并不是平衡二叉树，最大的却别在于红黑树放弃了绝对的子树平衡，转而追求一种大致平衡。保证了与平衡二叉树的时间复杂度相差不大的庆坤下
在红黑树中新增的节点最多进行3次旋转操作，就能重新班组红黑树的结构要求

口诀：红不相邻，黑平衡

TreeMap

HashMap

LinkedHashMap

Set结构

Set概述

HashSet

LinkedHashSet

TreeSet

数据结构

线性表

数组