Java 集合框架体系

Zenghr2021年4月25日大约 14 分钟

Java 集合框架体系

提示

本文用于整合集合框架的知识体系，如有不正确的地方请指出，感谢。

JDK Version：1.8.0.212

数据结构概述

数据结构就是数据在计算机中存储的方式，不同的数据结构，底层采用不同的存储算法，在执行具体的操作时，不同的算法会有不同的效率，有的查询效率慢，有的删除添加效率快等

常见的数据结构

数组(Array)
链表(Linked)
哈希表(Hash)
栈(Stack)
队列(Queue)
树(Tree)
图(Graph)
堆(Heap)

在日常的开发中，往往根据业务的需要，选择不同的数据结构，选择合适的集合类

这么多数据结构，我们又可以根据其数据结构特性(是否连成一条线)，分为 线性数据结构 和 非线性数据结构

线性数据结构

数组(Array)

把具有相同类型的数据有序地组织在一起，称为数组。数组使用 索引/下标 来表示元素的存储位置。

性能分析

添加操作：
如果是添加到数组尾部，只需要操作一次
如果添加到其他位置，则需要把后面的元素整体后移
删除操作：
如果是删除尾部元素，只需要操作一次
如果是删除其他位置元素，则需要把元素整体后移
修改操作：
给定索引，操作一次
根据内容，操作N次
查询操作：
给定索引，操作一次
根据内容，操作N次

总结：基于数组(Array)的数据结构做查询修改是非常快的，添加和删除就比较慢

链表(Linked)

每个元素在内存中的位置不是有序的，而是通过在每个元素中记录下一个元素的位置链接在一起，称为链表。

链表又分为单向链表和双向链表

单向链表：元素中只记录了下一个元素的位置，所以只能单向遍历
双向链表：元素中记录了上一个元素和下一个元素的位置，实现双向遍历

性能分析

添加操作：
添加位置在头部或尾部，操作一次
添加位置在其他位置，需要覆盖原有元素指向的位置，指向新的元素位置，新的元素则需要指向原有元素指向的位置
删除操作：
如果删除的元素是头部或尾部，操作一次
如果是中间元素，需要找到元素，删除操作一次
修改操作：
平均 (N + 1) / 2
查询操作：
平均 (N + 1) / 2

总结：链表(Linked) 数据结构对于添加删除操作较快，查询修改比较慢

队列(Queue)

队列是一种特殊的线性表，它只允许在头部进行删除操作，尾部进行添加操作，是一种受限制的线性表。

队列又分为单向队列和双向队列:

单向队列(Queue)：先进先出，只能在队尾插入，从队列头部删除
双向队列(Deque)：两端都可以进行添加删除数据，不能操作中间的数据

总结：擅长操作头部和尾部

栈(stack)

栈（stack）又名堆栈，它是一种运算受限的线性表，后进先出(LIFO)。

栈结构仅允许在表的一端进行插入和删除运算，这一端被称为栈顶，相对地，把另一端称为栈底。
向一个栈中插入新元素又称作入栈，它是把新元素放到栈顶元素的上面，使之成为新的栈顶元素。从一
个栈中删除元素又称作出栈

集合框架体系

集合是Java中提供的一种容器，可以用来存储多个数据，根据不同的存储方式形成的体系结构，就叫做集合框架体系。

每一种容器类底层拥有不同的底层算法(数据结构)。

Iterable 接口

从上图可以看出 Iterable 接口是所有集合的超类，实现此接口允许对象成为 for-each 循环的目标，它是 Java 中的一种 语法糖

List<Object> list = new ArrayList();
for (Object obj: list){}

其他遍历方式

Iterable 接口有一个方法，就是

Iterator<T> iterator();

该方法能创建一个轻量级的迭代器，用于安全的遍历元素，移除元素，如果在for-each中删除集合中的元素，是不安全的，会抛出 ConcurrentModificationException 异常，所以尽量使用迭代器的方式进行遍历，删除元素

for(Iterator it = coll.iterator(); it.hasNext(); ) {
	System.out.println(it.next());
}

提示

集合容器主要包括 Collection 和 Map 两种，Collection 存储对象的集合，而 Map 存储键值对 (key - value)

Collection 顶层接口

Collection 是顶层接口，它主要用于定义集合的约定

List 接口继承于 Collection 接口，同时也是 ArrayList、LinkedList 的父类

Set 接口跟 List 接口处于同级的层次，也继承于 Collection 接口，同时也是 HashSet、TreeSet 的父类

Map 是一个支持 key-value 存储的对象，Map 不能包含重复的 key，注意 Map 不继承于 Collection 接口

提示

实现类命名方式：底层数据结构 + 实现的集合接口。e.g：ArrayList (数组结构 + List 接口)

List 接口

List接口是 Collection接口的子接口，List 接口定义了一种规范，要求该容器允许记录元素的添加顺
序，也允许元素重复。那么List接口的实现类都会遵循这一种规范

常用实现类

ArrayList： 表示数组结构，底层采用数组实现，开发中使用最多的类。
LinkedList： 表示链表结构，表示单向链表和双向链表
Stack： 栈结构，使用数组实现，使用不多
Vector： 向量，老版的 ArrayList，使用数组实现，使用不多

常用 API

添加操作

boolean add(E e)： 将元素添加到列表末尾
void add(int index, E element)： 在列表的指定位置插入指定元素
boolean addAll(Collection<? extends E> c)： 将指定 collection 中的所有元素都插入到列表中的指定位置

删除操作

boolean remove(Object o)： 从此列表中移除第一次出现的指定元素
E remove(int index)： 移除列表中指定位置的元素
boolean removeAll(Collection<? extends E> c)： 从列表中移除指定 collection 中包含的其所有元素

修改操作

Object set(int index, Object ele)： 修改列表中指定索引位置的元素，返回被替换的旧元素

查询操作

int size()： 返回当前列表中元素个数
boolean isEmpty()： 判断当前列表中元素个数是否为0
Object get(int index)： 查询列表中指定索引位置对应的元素
Object[] toArray()： 把列表对象转换为Object数组
boolean contains(Object o)： 判断列表是否存在指定对象

ArrayList

ArrayList 是实现了 List 接口的可扩容数组，它的内部是基于数组实现的，不是线程安全

transient Object[] elementData;

其内部定义了一个 Object 类型的数组，所以它允许存储所有类型元素
ArrayList 内部有容量的概念，用于表示该数组能存储多大的数据
ArrayList 不是线程安全的容器，使用线程安全应该使用 Collections.synchronizedList
```
List list = Collections.synchronizedList(new ArrayList(...)) 
```
在集合遍历中，删除添加改变集合的结构时，会出现异常

Vector

Vector 同 ArrayList 一样，都是基于数组实现的，只不过 Vector 是线程安全的容器。内部每个方法使用 synchronized 进行同步，避免多线程引起的安全问题，但是也导致了 Vector 效率低下

LinkedList

LinkedList 类，底层采用链表算法，实现了链表，队列，栈的数据结构。无论是链表还是队列主要
操作的都是头和尾的元素，因此在 LinkedList 类中除了 List 接口的方法，还有很多操作头尾的方法

注：这个实现也不是线程安全的

常用 API

栈操作

void push(Object e)： 将元素推入此列表所表示的栈。
Object pop()： 从此列表所表示的栈处弹出一个元素
Object peek()： 获取但不移除此列表的头（第一个元素）

单向队列

会抛出异常👇
boolean add(Object e)： 入队操作
Object remove()： 出队操作
Object element()： 获取但不移除此列表的头（第一个元素）
不会抛出异常👇
boolean offer(Object e)： 入队操作
Object poll()： 出队操作
Object peek()： 获取但不移除此列表的头（第一个元素）

双向队列

会抛出异常👇
boolean addFirst(Object e)： 头部入队操作
boolean addLast(Object e)： 尾部入队操作
Object removeFirst()： 头部出队操作
Object removeLast()： 尾部出队操作
Object getFirst()： 返回此列表的第一个元素
Object getLast()： 返回此列表的最后一个元素
不会抛出异常👇
boolean offerFirst(Object e)： 头部入队操作
boolean offerLast(Object e)： 尾部入队操作
Object pollFirst()： 头部出队操作
Object pollLast()： 尾部出队操作
Object peekFirst()： 返回此列表的第一个元素
Object peekLast()： 返回此列表的最后一个元素

提示

LinkedList之所以有这么多方法，是因为自身实现了多种数据结构，而不同的数据结构的操作方法
名称不同

Stack

Stack 表示栈，是 Vector 类的子类，具有先进后出的特性，拥有push（入栈），pop（出栈）方法

Set 接口

Set 是 Collection 子接口，Set 接口定义了一种规范，也就是该容器不记录元素的添加顺序，也不允
许元素重复，那么 Set 接口的实现类都遵循这一种规范。

常用实现类

HashSet： 底层采用哈希表实现，开发中使用较多的实现类
TreeSet： 底层采用红黑树实现，可以对集合中元素排序，默认自然排序

常用 API

boolean add(Object e)
boolean remove(Object e)
boolean contains(Object e)
void clear()
int size()

HashSet

HashSet 是 Set 接口的实现类，底层采用哈希表实现，不能保证元素的有序，保证了元素的唯一，运行存储 NULL 元素，注意它不是线程安全的容器。

查看源码可知，其内部是 HashMap 的实例

private transient HashMap<E,Object> map;
public HashSet() {
    map = new HashMap<>();
}

底层工作原理

内部使用哈希表实现，每个元素需要先计算 哈希值，再通过 散列函数 计算出元素的位置

如果该位置存在元素，则去除该位置上链表的所有元素，通过 equals 方法依次比较，如果有重复的元素，则不添加，没有重复的元素，则在其链表后面添加，如下图👇

hashCode 和 equals

根据其工作原理，我们可以得知，在哈希表中元素的 hashCode 和 equals 方法很重要

每一个存储到好像表中的对象，都得覆盖hashCode和equals方法用来判断是否是同一个对象，一
般的，根据对象的字段数据比较来判断，通常情况下equals为true的时候hashCode也应该相等

TreeSet

TreeSet 是 Set 接口的实现类，底层采用红黑树算法实现，会对存储的元素进行排序，默认是自然排序(从小到大)

注意：TreeSet 不允许存储 NULL 值

红黑树存储的时候是左边的存较小的元素，右边存储较大的元素
由于 TreeSet 是平衡二叉树，如果树不平衡，会对节点进行调整

当我们使用 TreeSet 存储元素时，此时要求元素必须具备 比较大小 的能力，也就是实现 java.util.Comparable 接口

Comparable 接口

TreeSet 会调用元素的 compareTo 方法来比较元素的大小关系,然后将集合元素按照升序排列

public interface Comparable<T> {
	public int compareTo(T o);
}

比较规则，拿当前元素和另一个元素比较：

返回负数，当前元素小
返回正数，当前元素大
等于 0，一样，此时认为两个为同一个对象

如果我们存储进 TreeSet 集合中的元素没有比较功能，可以让该元素实现 Comparable 接口，并
覆盖compareTo方法，在该方法编写比较规则，否则添加会报错。

class ComparableExample implements java.lang.Comparable<User> {
    public int compareTo(ComparableExample o) {
        // ... 比较规则
        return int;
    }
}

Comparator 接口

当原有的排序规则不满足我们的需求时，我们可以提供一个 外部比较器(Comparator) 通过 TreeSet 构造器传入该比较器的实现类

public interface Comparator<T> {
  int compare(T o1, T o2);
}

使用方法：

因为 Comparator 实现类只是用一次，我们可以使用匿名内部类，JDK8 提供了 lambda 表达式，我们可以简写

// 需求：通过比较字符串长度
// 原有的 String 自带的比较规则不满足需求，使用 Comparator
public static void main(String[] args) {
    TreeSet<String> treeSet = new TreeSet<>(Comparator.comparingInt(String::length));
    treeSet.add("abc");
    treeSet.add("apple");
    treeSet.add("zeng");

    System.out.println(treeSet);
}

Map 接口

Map提供了一种映射关系，其中的元素是以键值对（key-value）的形式存储的，能够实现根据key快速查找value

Map 结构如下👇

其实能看出一个 Map 其实就由多个 key-value（键值对）组成的，每一个键值对我们使用Entry表示，键（key值）不可重复，value值可以重复

所以也可以说 Map 的 key 是存储在 set 集合中，不可重复

常用实现类

HashMap： 底层基于哈希表算法
TreeMap： 底层基于红黑树算法

常用 API

boolean put(Object key, Object value)：存储一个键值对到Map中
boolean putAll(Map m)：把 m 中的所有键值对添加到当前Map中
Object remove(Object key)：从Map中删除指定key的键值对，并返回被删除key对应的value
boolean isEmpty()：判断当前Map中键值对个数是否为0
Object get(Object key)：返回Map中指定key对应的value值，如果不存在该key，返回null
boolean containsKey(Object key)：判断Map中是否包含指定 key
boolean containsValue(Object value)：判断Map中是否包含指定 value
Set keySet()：返回Map中所有 key 所组成的Set集合
Collection values()：返回Map中所有 value 所组成的Set集合
Set entrySet()：返回Map中所有键值对所组成的Set集合

HashMap

HashMap 底层基于哈希表算法，Map中存储的 key 对象的 hashCode 值决定了在哈希表中的存储位
置，因为Map中的 key 是 Set，所以不能保证添加的先后顺序，也不允许重复

因为 HashSet 内部使用的就是 HashMap 所以两两者原理一致，HashSet 只是在 HashMap 上封装了一层，其底层工作原理一致

TreeMap

TreeMap底层基于红黑树算法，因为Map中的 key 是 Set，所以不能保证添加的先后顺序，也不允
许重复，但是Map中存储的 key 会默认使用自然排序（从小到大），和 TreeSet 一样，除了可以使用自然
排序也可以自定义排序

底层工作原理和 TreeSet 一致

集合框架工具类

Arrays

Arrays类是数组的工具类，其中包含对数组的拷贝、格式化、排序查询等方法

Arrays.copyOf(T[] original, int newLength)： 数组拷贝
System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length)：System类下的数组拷贝方法
Arrays.toString()： 数组格式化输出
Arrays.sort()： 数组排序，内部使用快速排序
Arrays.binarySearch： 二分查找
asList()： 将数组转化为 List 集合，但是不可改变长度

Collections

Collections 是一个操作 Collection（Set、 List ）和 Map 等集合的工具类

常用 API

排序操作

reverse(List)：反转 List 中元素的顺序
shuffle(List)：对 List 集合元素进行随机排序
sort(List)：根据元素的自然顺序对指定 List 集合元素按升序排序
sort(List， Comparator)：根据指定的 Comparator 产生的顺序对 List 集合元素进行排序
swap(List， int， int)：将指定 list 集合中的 i 处元素和 j 处元素进行交换

查找和替换

Object max(Collection)：根据元素的自然顺序，返回给定集合中的最大元素
Object max(Collection， Comparator)：根据 Comparator 指定的顺序，返回给定集合中的最大元素
Object min(Collection)
Object min(Collection， Comparator)
int frequency(Collection， Object)：返回指定集合中指定元素的出现次数
void copy(List dest,List src)：将src中的内容复制到dest中
boolean replaceAll(List list， Object oldVal， Object newVal)：使用新值替换List 对象的所有旧值

解决多线程并发访问集合时的线程安全问题

Collections提供了基本每种集合类型都有的方法: synchronizedXxx() 方法,以解决多个线程同时操作一个集合的并发问题

//通过如下的方法保证List的线程安全性
List list = Collections.synchronizedList(list1);

Java 集合框架体系

# Java 集合框架体系

# 数据结构概述

# 常见的数据结构

# 线性数据结构

# 数组(Array)

# 链表(Linked)

# 队列(Queue)

# 栈(stack)

# 集合框架体系

# Iterable 接口

# Collection 顶层接口

# List 接口

# 常用实现类

# 常用 API

# ArrayList

# Vector

# LinkedList

# 常用 API

# Stack

# Set 接口

# 常用实现类

# 常用 API

# HashSet

# 底层工作原理

# hashCode 和 equals

# TreeSet

# Comparable 接口

# Comparator 接口

# Map 接口

# 常用实现类

# 常用 API

# HashMap

# TreeMap

# 集合框架 工具类

# Arrays

# Collections

Java 集合框架体系

数据结构概述

常见的数据结构

线性数据结构

数组(Array)

链表(Linked)

队列(Queue)

栈(stack)

集合框架体系

Iterable 接口

Collection 顶层接口

List 接口

常用实现类

常用 API

ArrayList

Vector

LinkedList

常用 API

Stack

Set 接口

常用实现类

常用 API

HashSet

底层工作原理

hashCode 和 equals

TreeSet

Comparable 接口

Comparator 接口

Map 接口

常用实现类

常用 API

HashMap

TreeMap

集合框架工具类

Arrays

Collections