Java 集合

江南烟雨行舟 / 2023-08-11 / 原文

Java 集合也叫作容器，就是专门用来存放对象的；也就是说，没有办法存放基础数据类型 int，必须要存放包装类 Integer。

Java 集合主要是由两大接口派生而来：一个是 Collecton 接口，主要用于存放单一元素；另一个是 Map 接口，主要用于存放键值对。

对于 Collection 接口，下面又有三个主要的子接口：List 、 Set 和 Queue，如下图：

集合与数组的区别：

数组的长度是固定的，集合的长度不固定。
数组可以存储基本类型和引用类型，集合只能存储引用类型。

ArrayList

ArrayList 就是一个 非线程安全 的动态数组，并且允许元素为 null。

ArrayList 底层就是使用数组实现的，所以通过下标访问或修改快，尾部追加要看是不是需要扩容，需要扩容的话就慢。

1.数组用来做队列合适么？

ArrayList 不适合做队列，但是数组是非常合适的。比如 ArrayBlockingQueue 内部实现就是一个环形队列，它是一个定长队列，内部是用一个定长数组来实现的。

2.ArrayList 和 Vector 的区别？

主要区别就是 ArrayList 是非线程安全的，Vector 是线程安全的；它们的实现都是差不多的，都是使用 Object[] 数组存储元素，而且都可以返回 ListIterator<E> 迭代器。这两个集合都适用于查询比较多，增删比较少的情况。

下面是 ArrayList 的继承和实现：

public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable

继承和实现图：

扩容逻辑

先来说说扩容，我个人将 ArrayList 的扩容方式分为两种：主动扩容和被动扩容：

主动扩容：调用 ensureCapacity(int) 方法
被动扩容：是调用 add、addAll、readObject 方法时，会判断需不需要扩容

但是扩容逻辑都是一样的，目标大小 - 集合长度 > 0 就说明需要扩容：

按照当前集合长度 * 1.5 算出一个新的集合长度，假设当前集合长度为 10，10 * 1.5 = 15。
在创建一个新数组，然后调用 System.arraycopy 方法，将旧数组中的元素拷贝到新数组中。

添加元素

使用 boolean add(E) 方法在尾部追加元素：先判断需不需要扩容，然后再把元素添加到 size + 1 的下标位置。
使用 add(int, E) 在指定下标中插入元素：先判断需不需要扩容，然后从要插入的下标开始，使用 System.arraycopy 将原来的元素整体后移，最后将要插入的元素赋值给要插入的下标。

插入元素不一定比 LinkedList 慢，要看需不需要扩容。

移除元素

根据 E remove(int) 下标删除元素：从要删除的下标 + 1开始，使用 System.arraycopy 将原来的元素整体前移，最后将最后一个元素设置为 null。
根据 boolean remove(Object) 对象删除元素：通过 for 循环找到要删除的实例下标，然后从要删除的下标 + 1开始，使用 System.arraycopy 将原来的元素整体前移，最后将最后一个元素设置为 null。

删除集合中所有 null 元素

Java 8 方式：

List<Integer> listWithoutNulls = Lists.newArrayList(null, 1, 2, null, 3, null);
listWithoutNulls.removeIf(Objects::isNull);

LinkedList

LinkedList 使用 双向链表 的形式存放数据，非线程安全的，增删比较快，但是查询慢，因为要使用 for 循环遍历。

LinkedList 中有两个属性：

first：头节点
last：尾节点

每个节点也有两个属性：

next：下一个节点
prev：上一个节点

添加节点

在尾部追加元素：

添加第一个元素头尾节点都指向节点 1，节点 1 的上一个和下一个节点都为 null。

当添加节点2的时候，尾节点指向节点 2，节点 1 的下一个节点指向节点 2，节点 2 的上一个节点指向节点1。
在指定位置插入元素：假设链表中有两个节点，要在下标 1 的位置插入新节点 3

先通过 for 循环，获取出下标 1 的节点 2，然后节点 1 的下一个节点指向节点 3，节点 3 的上一个节点指向节点 1，下一个节点指向节点 2，然后节点 2 的上一个节点指向节点 3。
下面这张图是最终的执行结果图，节点 2 就是新节点，节点 3 就是上图的节点 2：

移除节点

通过下标移除元素：和在指定位置插入元素的操作相反。
通过对象移除元素：通过 for 循环从前面找到元素，修改左右两边元素的 next 和 prev。

获取节点

通过 get(int index) 方式获取节点时，先将集合大小（size）除以 2，如果参数 index 小于除以 2 以后的值，就会从前向后迭代；否则就会从后向前迭代。

链表不能向数组一样可以随机访问，只能通过 foreach 循环或 Iterator 的方式获取。

ArrayList 与 LinkedList 区别？

1.ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全。
2.ArrayList 底层适用数组，LinkedList 底层适用双向链表。
3.LinkedList 不支持高效的随机元素访问，而 ArrayList 支持。快速随机访问就是通过元素的序号快速获取元素对象（对应于 get(int) 方法）。
4.ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响；LinkedList 采用链表存储，所以如果是在头尾插入或者删除元素不受元素位置的影响。

ConcurrentHashMap

ConcurrentHashMap 就是一个线程安全的 HashMap，在 JDK 1.8 中取消了分段锁，而采用 Node + CAS + Synchronized 来保证线程安全。

HashTable 是在方法上使用 synchronized 关键字；HashMap 可以使用 Collections.synchronizedMap 进行包装，包装后也是使用 synchronized 关键字。

ConcurrentHashMap 的数据结构

在 JDK1.8 中，ConcurrentHashMap 采用数组+链表+红黑树的方式来实现数据存储，如下图：

在 JDK 1.8 中 ConcurrentHashMap 的数据结构和 HashMap 的数据结构是一样的，区别就是 HashMap 是非线程安全的。

在 JDK 1.7 中的数据结构是数组+链表。

扩容还是转化为红黑树

当链表长度大于或者等于 8 时，ConcurrentHashMap 认为链表已经有点长了，需要考虑优化，有两种方式：

当数组长度大于等于 64，并且链表长度也大于等于 8 的时候，就会把链表转化为红黑树；当不满足的时候还会再转换为链表。
当数组长度小于 64，并且链表长度大于等于 8 的时候，会对数组进行扩容。

使用红黑树代替链表是为了加快，查找、插入和删除操作。

如何解决冲突

插入数据的时候会先获取 Key 的 hash 值，再计算出数组的下标。

没有哈希冲突，就直接放到数组中。
有哈希冲突，就会将下标对应的位置转换为链表，并追加到这个链表的后面。

因为 hashCode 相同，但是值不一定是相等（equals 方法比较）。

为什么负载因子是 0.75

负载因子决定了 HashMap 什么时候进行扩容，默认情况下是存储了 12（16 * 0.75 = 12）个元素后，就会自动扩容，扩容为原来容量的两倍。

ConcurrentHashMap 的负载因子不允许修改。

0.75 就是为了平衡空间利用率和时间效率：

就是说数组长度越长，发生哈希冲突的几率就越小，就导致了元素都分布在数组上，会提高查询、添加、删除的效率；但是有可能导致数组没有被占满，也就是浪费了一些内存。
假设负载因子为 0.25，当存储了 4 个元素的时候就会进行扩容。
相反的，数组越短，发生哈希冲突的几率就越大，就会导致链表过长，会降低查询、添加、删除的效率；但是不会浪费内存。
假设负载因子为 1，当存储了 16 个元素的时候才会进行扩容。