type
status
date
slug
summary
tags
category
icon
password
AI 摘要
1.1.1.1. Java集合也就是容器，是由两个接口派生而来
1.1.1.2. 说说 List, Set, Queue, Map 四者的区别？
List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
Set(注重独一无二的性质): 存储的元素不可重复的。
Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，"x" 代表 key，"y" 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。
1.1.1.3. 如何选用集合?
我们主要根据集合的特点来选择合适的集合。比如：
我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。
List
1.1.1.4. ArrayList 插入和删除元素的时间复杂度？
对于插入：
头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。
尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。
指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。
对于删除：
头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。
1.1.1.5. LinkedList 插入和删除元素的时间复杂度？
头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，因此需要遍历平均 n/2 个元素，时间复杂度为 O(n)。
1.1.1.6. ArrayList 与 LinkedList 区别?
1.1.1.7. LinkedList 为什么不能实现 RandomAccess 接口？
RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。
1.1.1.8. Comparable 和 Comparator 的区别
Comparable 接口和 Comparator 接口都是 Java 中用于排序的接口，它们在实现类对象之间比较大小、排序等方面发挥了重要作用：
Comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
Comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)方法用来排序
一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法，当我们需要对某一个集合实现两种排序方式，比如一个 song 对象中的歌名和歌手名分别采用一种排序方法的话，我们可以重写compareTo()方法和使用自制的Comparator方法或者以两个 Comparator 来实现歌名排序和歌星名排序，第二种代表我们只能使用两个参数版的 Collections.sort()
1.1.1.9. 比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同
元素唯一，线程安全、数据结构、（由数据结构决定）应用场景
- HashSet、LinkedHashSet 和 TreeSet 都是 Set 接口的实现类，都能保证元素唯一，并且都不是线程安全的。
- HashSet、LinkedHashSet 和 TreeSet 的主要区别在于底层数据结构不同。HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。
- 底层数据结构不同又导致这三者的应用场景不同。HashSet 用于不需要保证元素插入和取出顺序的场景，LinkedHashSet 用于保证元素的插入和取出顺序满足 FIFO 的场景，TreeSet 用于支持对元素自定义排序规则的场景
Queue
1.1.1.10. Queue 与 Deque 的区别
Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则。
Queue 扩展了 Collection 的接口，因为容量问题而导致操作失败后处理方式的不同 可以分为两类方法: 一种在操作失败后会抛出异常，另一种则会返回特殊值。
Deque是双端队列，在队列的两端均可以插入或删除元素。
Deque扩展了Queue的接口, 增加了在队首和队尾进行插入和删除的方法，同样根据失败后处理方式的不同分为两类：
1.1.1.11. ArrayDeque 与 LinkedList 的区别
ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？
- ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
- ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
- ArrayDeque 是在 6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
- ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。
从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈。
1.1.1.12. Java 中常用的阻塞队列实现类有以下几种：
1.1.1.13. ArrayBlockingQueue 和 LinkedBlockingQueue 有什么区别？
1.1.1.15. HashMap 和 HashSet 区别
1.1.1.16. HashMap 和 TreeMap 区别
总结：相比于HashMap来说，TreeMap主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力
1.1.1.17. HashMap 的长度为什么是 2 的幂次方
为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。我们上面也讲到了过了，Hash 值的范围值-2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。
这个算法应该如何设计呢？
我们首先可能会想到采用 % 取余的操作来实现。但是，重点来了：“取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。” 并且 采用二进制位操作 & 相对于 % 能够提高运算效率，这就解释了 HashMap 的长度为什么是 2 的幂次方。
1.1.1.18. ConcurrentHashMap 和 Hashtable 的区别
需结合源码分析
1.1.1.19. ConcurrentHashMap 为什么 key 和 value 不能为 null？
1.1.1.20. ConcurrentHashMap 能保证复合操作的原子性吗？
1.1.1.21. Java集合使用注意事项总结
1.1.1.21.1. 集合判空
判断所有集合内部的元素是否为空，使用isEmpty()方法，而不是size()==0的方式。
这是因为isEmpty()方法的可读性更好，并且时间复杂度为 O(1)。
1.1.1.21.2. 集合转 Map
在使用java.util.stream.Collectors类的toMap()方法转为Map集合时，一定要注意当 value 为 null 时会抛 NPE 异常。
原因：我们来看java.util.stream.Collectors类的toMap()方法 ，可以看到其内部调用了Map接口的merge()方法。
1.1.1.21.3. 集合遍历
不要在 foreach 循环里进行元素的remove/add操作。remove 元素请使用Iterator方式，如果并发操作，需要对Iterator对象加锁。
通过反编译你会发现 foreach 语法底层其实还是依赖 Iterator 。不过， remove/add 操作直接调用的是集合自己的方法，而不是 Iterator 的 remove/add方法
这就导致 Iterator 莫名其妙地发现自己有元素被 remove/add ，然后，它就会抛出一个 ConcurrentModificationException 来提示用户发生了并发修改异常。这就是单线程状态下产生的 fail-fast
Java8 开始，可以使用Collection#removeIf()方法删除满足特定条件的元素,如
1.1.1.21.4. 集合去重
可以利用Set元素唯一的特性，可以快速对一个集合进行去重操作，避免使用List的contains()进行遍历去重或者判断包含操作。
1.1.1.21.5. 集合转数组
使用集合转数组的方法，必须使用集合的 toArray(T[] array)，传入的是类型完全一致、长度为 0 的空数组。
toArray(T[] array) 方法的参数是一个泛型数组，如果 toArray 方法中没有传递任何参数的话返回的是 Object类 型数组。
由于 JVM 优化，new String[0]作为Collection.toArray()方法的参数现在使用更好，new String[0]就是起一个模板的作用，指定了返回数组的类型，0 是为了节省空间，因为它只是为了说明返回的类型。
1.1.1.21.6. 数组转集合
使用工具类 Arrays.asList() 把数组转换成集合时，不能使用其修改集合相关的方法， 它的 add/remove/clear 方法会抛出 UnsupportedOperationException 异常。
注意事项：
.那我们如何正确的将数组转换为 ArrayList ?
等等，也有其他的方式
1.1.1.22. 集合源码分析
1.1.1.22.1. ArrayList源码
ArrayList 的底层是数组队列，相当于动态数组。与 Java 中的数组相比，它的容量能动态增长。在添加大量元素前，应用程序可以使用ensureCapacity操作来增加 ArrayList 实例的容量。这可以减少递增式再分配的数量。
ArrayList 继承于 AbstractList ，实现了 List, RandomAccess, Cloneable, java.io.Serializable 这些接口。
- List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
- RandomAccess ：这是一个标志接口，表明实现这个接口的 List 集合是支持 快速随机访问 的。在 ArrayList 中，我们即可以通过元素的序号快速获取元素对象，这就是快速随机访问。
- Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
- Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。
注意：Java 中，类的实例字段会自动被初始化为其默认值。对于 int 类型，默认值是 0。
源码的几个关键点：
- Arraylist的三种初始化方法，即三种构造方法，默认构造函数、带初始容量的构造函数、带元素列表的构造函数
以无参数构造方法创建 ArrayList 时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为 10
- ArrayList扩容的核心方法
int newCapacity = oldCapacity + (oldCapacity >> 1),所以 ArrayList 每次扩容之后容量都会变为原来的 1.5 倍左右（oldCapacity 为偶数就是 1.5 倍，否则是 1.5 倍左右）！
- arraycopy() 和 Arrays.copyOf()方法
联系：看两者源代码可以发现 copyOf()内部实际调用了 System.arraycopy() 方法
区别：arraycopy() 需要目标数组，将原数组拷贝到你自己定义的数组里或者原数组，而且可以选择拷贝的起点和长度以及放入新数组中的位置 copyOf() 是系统自动在内部新建一个数组，并返回该数组
- ensureCapacity方法
理论上来说，最好在向 ArrayList 添加大量元素之前用 ensureCapacity 方法，以减少增量重新分配的次数；向 ArrayList 添加大量元素之前使用ensureCapacity 方法可以提升性能。不过，这个性能差距几乎可以忽略不计。而且，实际项目根本也不可能往 ArrayList 里面添加这么多元素。
1.1.1.22.2. LinkedList源码
LinkedList 实现了以下接口：
- List : 表明它是一个列表，支持添加、删除、查找等操作，并且可以通过下标进行访问。
- Deque ：继承自 Queue 接口，具有双端队列的特性，支持从两端插入和删除元素，方便实现栈和队列等数据结构。需要注意，Deque 的发音为 "deck" [dɛk]，这个大部分人都会读错。
- Cloneable ：表明它具有拷贝能力，可以进行深拷贝或浅拷贝操作。
- Serializable : 表明它可以进行序列化操作，也就是可以将对象转换为字节流进行持久化存储或网络传输，非常方便。
初始化
无参构造，有参构造
无参构造函数 LinkedList() 会创建一个空的链表实例。此时，链表的内部节点（即 first 和 last）均为 null，表示链表为空。size 也被初始化为 0。
增
add
核心代码：
删
LinkedList删除元素相关的方法一共有 5 个：
- removeFirst()：删除并返回链表的第一个元素。
- removeLast()：删除并返回链表的最后一个元素。
- remove(E e)：删除链表中首次出现的指定元素，如果不存在该元素则返回 false。
- remove(int index)：删除指定索引处的元素，并返回该元素的值。
- void clear()：移除此链表中的所有元素。
改
查
- --获取元素
LinkedList获取元素相关的方法一共有 3 个：
getFirst()：获取链表的第一个元素。
getLast()：获取链表的最后一个元素。
get(int index)：获取链表指定位置的元素。
get(int index) 或 remove(int index) 等方法内部都调用了该方法来获取对应的节点。
从这个方法的源码可以看出，该方法通过比较索引值与链表 size 的一半大小来确定从链表头还是尾开始遍历。如果索引值小于 size 的一半，就从链表头开始遍历，反之从链表尾开始遍历。这样可以在较短的时间内找到目标节点，充分利用了双向链表的特性来提高效率。
- --遍历元素
推荐使用for-each 循环来遍历 LinkedList 中的元素， for-each 循环最终会转换成迭代器形式。
- 作者:阿蒙
- 链接:https://blog.51xyw.xyz//article/javaCollection
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。