Java开发笔记_集合
Java 集合？
- 集合框架主要有两大接口：Collection 接口、Map 接口
- Collection 接口用于存储一组对象，Map 接口用于存储键值对
- Collection 接口有三个主要子接口：List Set Queue
说说 List、Set、Queue、Map 四者的区别？
- List: 有序集合，允许重复存储元素
- Set：无序集合，元素不可以重复
- Queue：队列集合，按照先入先出的顺序操作元素，元素有序可重复
- Map：键值对集合，存储不重复的键值对
集合框架底层数据结构总结？
- ArrayList：数组
- LinkedList：双向链表
- Hashset：哈希表
- HashMap：哈希表
- TreeSet：红黑树
- TreeMap：红黑树
- PriorityQueue：堆
- ConcurrentHashMap：分段锁的哈希表
ArrayList 和 Vector 的区别?
- ArrayList 是 List 的主要实现类，使用于频繁查找的工作，线程不安全
- Vector 是 List 的古老实现，是线程安全的，在每个方法调用都进行同步，有很大的性能损失，推荐使用并发包的 CopyOnWriteArrayList，在副本修改，不会有并发问题
ArrayList 与 LinkedList 区别?
- 数据结构不同：
ArrayList 基于数组实现，LinkedList 基于双向链表实现 - 功能上：
ArrayList 适合查找，LinkedList 适合增删 - 是否支持随机访问：
ArrayList 支持随机访问；LinkedList 不支持随机访问 - 内存占用：
ArraryList 占用连续的内存空间；LinkedList 内存空间不连续
ArrayList 核心扩容机制？
- 向 ArrayList 添加元素时，元素数量等于容量，会触发扩容操作
- 扩容后的新容量大小一般为原容量大小的 1.5 倍
- 如果计算的新容量小于所需的容量。就会直接使用最小容量来扩容
- 确定好新的容量大小后，会创建一个新的数组，将原有元素复制到新数组中，同时释放原数组的空间
ArrayList 怎么序列化的知道吗？
- ArrayList 使用自定义的序列化机制，数组使用 transient 修饰，在序列化的时候只序列化实际存储的元素，而不是整个数组
为什么 ArrayList 用 transient 修饰数组？
- 当对象序列化时，Java 会默认将对象所有字段都进行序列化
- transient 关键字修饰数组就是告诉 Java 序列化机制不要对数组进行默认的序列化
- 数组的长度可能远大于当前实际存储的元素数量，序列化整个数组会占用大量的空间和时间
快速失败和安全失败了解吗？
-
快速失败：
一种错误检测机制，用于在多线程环境下，当多个线程同时修改同一个集合时，能够抛出异常 -
安全失败：
一种容错机制，在迭代操作时不会直接在原集合上操作，而是在原集合的副本上进行遍历操作，用于在遍历集合的同时，不会因为集合的修改而异常
有哪几种实现 ArrayList 线程安全的方法？
- 使用 Vector 代替 ArrayList
- 使用 Collection.synchronizedList() 方法
- 使用 Reentrantlock 实现同步
- 使用 CopyOnWriteArrayList
CopyOnWriteArrayList 了解多少？
- CopyOnwriteArrayList 是 Java 并发包中提供的一个线程安全的集合类
- 实现 List 接口
- 通过在写操作时创建一个新的数组来实现线程安全。读操作不需要加锁，所以适用于读多写少的场景。
Comparable 和 Comparator 的区别？
- Comparable 接口：是类内部的接口，用于定义对象自身的默认排序方式
通过类实现 Comparable 接口的 compareTo() 方法，可以实现排序 - Comparator 接口：是比较器接口，可以在类外部定义多种不同的排序方式
通过实现 Comparator 接口，可以创建不同的比较规则，而不需要修改原始类的代码
无序性和不可重复性的含义是什么？
- 无序性：元素没有明确的顺序关系，不一定按照特定的顺序存储或返回
- 不可重复性：集合中的元素是不重复的
比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同？
HashSet:
- 底层数据结构：哈希表
- 无序性
- 不可重复性
- 查找效率：平均查找时间复杂度是 O(1)
- 适用场景：适用于快速查找无序元素的情况
LinkedHashSet:
- 底层数据结构：哈希表 + 链表
- 有序性：元素按照插入顺序存储
- 不可重复性
- 查找效率：平均查找时间复杂度是 O(1)
- 适用场景：适用于保持插入顺序且不允许重复元素的情况
TreeSet:
- 底层数据结构：红黑树
- 有序性：元素按照自然顺序存储
- 不可重复性
- 查找效率：平均查找时间复杂度是 O(logN)
- 适用场景：适用于有序且不重复的元素的情况
Queue 与 Deque 的区别？
- Queue：单端队列，元素按照先进先出的顺序排序
- Deque：双端队列，在队列的两端都可以插入删除元素
ArrayDeque 与 LinkedList 的区别？
- 底层实现不同：ArrayDeque 是双端队列，底层实现是循环数组，LinkedList 是双向链表
- 随机访问：ArrayDeque 支持随机访问，LinkedList 不支持随机访问
- 使用场景：
如果在双端进行频繁的插入和删除操作，通常选择 ArrayDeque
如果在中间进行插入和删除操作，通常选择 LinkedList
说一说 PriorityQueue？
- PriorityQueue 是 Java 集合中的类，用于实现优先队列，基于二叉堆实现
- PriorityQueue 内部使用可变长数组来存储数据，通过堆的上浮和下沉操作，保证堆的特性
- 插入和删除堆顶元素的时间复杂度是 O(logn)
- PriorityQueue 默认是小顶堆，可以通过自定义的比较器创建大顶堆
HashMap
讲讲 HashMap？
- HashMap 是 Java 集合中的类，是键值对存储的数据结构，基于哈希表实现
- 允许存储任意类型的键值对，其中键唯一，值可以重复
- HashMap 内部使用哈希函数将键映射到桶，每个桶存储了一组键值对
- HashMap 是非线程安全的，多线程中，通常使用 ConcurrentHashMap
HashMap 底层数据结构？
- 在 JDK7 中，HashMap 使用的是数组 + 链表的数据结构来存储键值对。具体来说，数组的每个元素是一个链表，用于存储具有相同哈希值的键值对
- 在 JDK8 中，HashMap 对于链表长度过长的情况（默认超过 8 个元素）会将链表转换为红黑树，从而提高查询效率
你对红黑树了解多少？为什么不用二叉树/平衡树呢？
- 红黑树是自平衡的二叉查找树，在每个节点增加额外的颜色信息来满足平衡性质，插入、删除、查找的时间复杂度是 O(logn)
- 平衡二叉树是比红黑树更严格的平衡树，为了保持平衡，需要旋转的次数更多，保持平衡的效率比红黑树低
红黑树怎么保持平衡的知道吗？
- 节点颜色：每个节点都被标记为红色或者黑色
- 根节点：根节点是黑色的
- 叶节点：每个叶节点都是黑色的
- 红色子节点：如果一个节点是红色的，则其子节点必须是黑色的
- 黑色高度：任意节点到子树的每个叶子节点的路径，必须包含相同数量的黑色节点
HashMap 的 put 流程知道吗？
- 计算存储位置：HashMap 会根据键的 hashcode 值计算出键值对对应的存储位置
- 检查存储位置：如果该位置没有元素，则直接将键值对存储在该位置
- 位置已经有元素：如果该位置已经存在其他键值对，需要进行更多操作：
- 键存在：使用 hashcode 值和 equals() 方法判断该键是否存在，如果存在，则替换原有值
- 键不存在：将新的键值对添加到链表或红黑树中
- 链表转换为红黑树：当链表的长度超过 8 个节点时，HashMap 会将该链表转换为红黑树
- 扩容：当存储键值对的数量超过容量的 0.75 倍时，HashMap 会进行扩容操作
HashMap 怎么查找元素的呢？
- 使用扰动函数获取新的哈希值
- 计算数组下标，获取节点
- 如果当前节点和 key 匹配，直接返回该节点的 value 值，查找完成
- 如果当前节点是树节点，则在红黑树中查找 key 值
- 如果不是树节点，遍历链表查找
- 如果遍历完链表或红黑树仍然没找到 key 值，返回 null。
HashMap 的哈希/扰动函数是怎么设计的?
- HashMap 将 key 的 hashCode 右移 16 位，然后将结果和原 hashCode 进行异或操作
为什么哈希/扰动函数能降 hash 碰撞？
- 通过哈希函数的设计，使相同哈希值的键值对能够分散到不同的桶中
为什么 HashMap 的容量是 2 的倍数呢？
- 容量为 2 的倍数，可以使用位运算，哈希计算的效率更高
- 容量为 2 的倍数可以保证元素在哈希表中均匀分布，减少哈希碰撞
如果初始化 HashMap，传一个 17 的值 new HashMap<>，它会怎么处理？
hashMap 会向上寻找离最近的 2 的倍数，即 32，作为 HashMap 的实际容量
你还知道哪些哈希函数的构造方法呢？
- 直接定址法：直接根据 key 值映射到数组的位置
- 数字分析法：取 key 的某些位置作为映射的位置
- 平方取中法：取 key 平方的中间几位作为映射的位置
解决哈希冲突有哪些方法呢？
- 链地址法：(HashMap) 在冲突的位置上设置链表，把冲突的元素放进去
- 开放定址法：从冲突的位置往下找，直到找到空位
- 公共溢出区法：在哈希表中建立一个公共溢出区，将冲突元素放进去
为什么 HashMap 链表转红黑树的阈值为 8 呢？红黑树转链表的阈值为 6？
- 根据统计学，链表长度为 8 时，将链表转换为红黑树的效率值最大
- 选择 6 是为了避免频繁的链表和红黑树之间的转换
扩容在什么时候呢？为什么扩容因子是 0.75？
- 扩容通常发生在数据结构的存储空间快要到达容量上限的时候进行
- 扩容因子一般是 0.75，主要是考虑时间和空间的平衡性，是一个经验值
HashMap 扩容机制了解吗？
- 触发扩容机制：当 HashMap 中的元素超过负载因子和数组长度乘积时，触发扩容操作
- 创建新数组：需要扩容时会创建新的数组，长度为原来的2 倍
- 移动元素：HashMap 会重新计算原数组元素的哈希值，然后将原数组中的所有元素移动到新数组中对应的位置
JDK1.8 进行优化，不需要重新计算每个元素的哈希值，元素的位置只可能在原位置，或者原位置向右移动 2 的次幂
JDK1.8 对 HashMap 主要做了哪些优化呢？为什么？
- 数据结构变化：数组 + 链表变成数组 + 链表 + 红黑树
在链表过长时转为红黑树，将时间复杂度从 O(n) 降为 O(logn) - 链表插入方式变化：链表的插入方式从头插法改成了尾插法
头插法扩容时，会使链表发生反转，多线程环境下会产生环 - 扩容后数组位置优化：1.7 需要对原数组的元素重新计算哈希值，1.8 进行优化，元素位置不变或者移动 2 的次幂，提高扩容的效率
HashMap 是线程安全的吗？多线程下会有什么问题？
- HashMap 不是线程安全的
- 多线程的问题：
- 扩容死循环：JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容可能导致环形链表
- 元素丢失：多线程的 put 会导致元素的丢失，当计算的索引位置相同，新的 key 值会覆盖之前存储的值
- 并发的 put 和 get：线程的 put 和 get 并发时，可能会导致 get 操作读取的值为过时的数据或者空值
有什么办法能解决 HashMap 线程不安全的问题呢？
- 使用 ConcurrentHashMap
在内部使用了分段锁来对不同的部分进行并发控制，从而允许多个线程同时进行读取和写入操作，而不需要全局锁定整个数据结构 - 使用 Collections.synchronizedMap 方法
将普通的 HashMap 包装成线程安全的 Map
HashMap 和 Hashtable 的区别？
- 线程安全：Hashtable 是线程安全的，HashMap 不是线程安全的
- 允许空键值：HashTable 不允许键值为 null，而 HashMap 允许键值为 null
- 性能：Hashtable 是线程安全的，需要进行线程同步，所以在高并发的环境中，Hashtable 的性能相对较差
- 底层数据结构：HashTable 的底层数据结构是数组和链表，而 HashMap 在 JDK1.8 以后为数据 + 链表 + 红黑树
HashMap 和 HashSet 区别？
- 底层实现：HashSet 底层实现是基于 HashMap 实现的
- 接口实现：HashMap 实现 Map 接口，HashSet 实现 Set 接口
- 元素存储：HashMap 存储键值对，其中 key 值唯一，value 值可以重复；HashSet 用来存储唯一元素，重复的元素会自动去重
- 元素添加：HashMap 调用 put() 方法向 map 中添加元素，HashSet 调用 add() 方法向 Set 添加元素
HashMap 和 TreeMap 区别？
- 底层实现：HashMap 基于哈希表实现，TreeMap 基于红黑树实现
- 存储顺序：HashMap 不保证存储顺序，TreeMap 可以保证存储顺序，
- 时间复杂度：HashMap 的查找的平均时间复杂度是 O(1)，TreeMap 的时间复杂度为 O(logn)
- 空间复杂度：TreeMap 需要额外的空间存储红黑树结构，具有更高的空间复杂度
HashMap 有哪几种常见的遍历方式?
- 迭代器遍历：使用 Iterator 遍历 HashMap，获取键和值
Iterator<Map.Entry<Integer, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
Map.Entry<Integer, String> entry = iterator.next();
Integer key = entry.getKey();
String value = entry.getValue();
// 处理 key 和 value
}- foreach 遍历：遍历键的集合
for (Integer key : map.keySet()) {
String value = map.get(key);
// 处理 key 和 value
}- keySet 遍历：通过 keySet() 方法获取 HashMap 的键集合，然后通过 get() 方法获取对应的值
for (Integer key : map.keySet()) {
String value = map.get(key);
// 处理 key 和 value
}HashSet 如何检查重复?
- 比较对象 hashcode 值：检查是否有其他元素具有相同的 hashcode 值
- 如果没有相同的 hashcode 值，HashSet 会假设元素没有重复出现
- 如果有相同的 hashcode 值，会调用 equals() 方法比较，如果返回 true，HashSet 会认为元素重复
HashMap 多线程操作导致死循环问题？
- JDK1.7 中的 HashMap 使用头插法插入元素，在多线程的环境下，扩容可能导致环形链表
HashMap 内部节点是有序的吗？
- 不是有序的，元素的存储顺序是根据哈希值决定的，而不是插入的顺序
- 如果想使用有序的 Map，可以使用 LinkedHashMap 或者 TreeMap
讲讲 LinkedHashMap 怎么实现有序的？
- LinkedHashMap 内部维护一个双向链表，有头尾节点
讲讲 TreeMap 怎么实现有序的？
- TreeMap 的底层数据结构是红黑树
- 红黑树是一种自平衡的二叉查找树，通过旋转和改变节点颜色来保持树的平衡
- TreeMap 内部基于红黑树的自平衡性保证了其中元素的有序性
JDK1.7 和 JDK1.8 的 ConcurrentHashMap 的底层具体实现？
JDK1.7：
- JDK1.7 的 ConcurrentHashMap 使用分段锁技术，将整个 HashMap 分成若干个段，并为每个段分配一个独立的锁
JDK1.8：
- JDK1.8 的 ConcurrentHashMap 使用 CAS 和 synchronized 块实现线程安全，避免了锁的竞争，提高了并发的性能
- JDK1.8 的 ConcurrentHashMap 使用链表和红黑树的结构来存储哈希碰撞的元素，提高了查找性能
ConcurrentHashMap 和 Hashtable 的区别？
- 底层数据结构：
- JDK1.7 的 ConcurrentHashMap 底层使用分段的数组 + 链表实现
- JDK1.8 的 ConcurrentHashMap 底层使用数组 + 链表 + 红黑树实现
- Hashtable 使用数组 + 链表
- 实现线程的方式
- HashTable 使用 sychronized 来保证线程安全，效率偏低
- JDK1.7 的 ConcurrentHashMap 使用分段锁技术，将整个 HashMap 分成若干个段，并为每个段分配一个独立的锁
- JDK1.8 的 ConcurrentHashMap 使用 CAS 和 synchronized 技术保证线程安全，避免了锁的竞争，提高了并发的性能