八股记录——集合

Posted on Edited on In Word count in article: 5.7k Reading time ≈ 5 mins.

一、集合概览

整体框架：

1、说说 List, Set, Queue, Map 四者的区别？

  • List(对付顺序的好帮手): 存储的元素是有序的、可重复的。
  • Set(注重独一无二的性质): 存储的元素是无序的、不可重复的。
  • Queue(实现排队功能的叫号机): 按特定的排队规则来确定先后顺序，存储的元素是有序的、可重复的。
  • Map(用 key 来搜索的专家): 使用键值对（key-value）存储，类似于数学上的函数 y=f(x)，”x” 代表 key，”y” 代表 value，key 是无序的、不可重复的，value 是无序的、可重复的，每个键最多映射到一个值。

2、集合框架底层数据结构总结

先来看一下 Collection 接口下面的集合。

List

  • ArrayList： Object[] 数组
  • Vector：Object[] 数组
  • LinkedList： 双向链表(JDK1.6 之前为循环链表，JDK1.7 取消了循环)

Set

  • HashSet(无序，唯一): 基于 HashMap 实现的，底层采用 HashMap 来保存元素
  • LinkedHashSet: LinkedHashSet 是 HashSet 的子类，并且其内部是通过 LinkedHashMap 来实现的。有点类似于我们之前说的 LinkedHashMap 其内部是基于 HashMap 实现一样，不过还是有一点点区别的
  • TreeSet(有序，唯一): 红黑树(自平衡的排序二叉树)

Queue

  • PriorityQueue: Object[] 数组来实现二叉堆
  • ArrayQueue: Object[] 数组 + 双指针

Map

  • HashMap： JDK1.8 之前 HashMap 由数组+链表组成的，数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的（“拉链法”解决冲突）。JDK1.8 以后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间
  • LinkedHashMap： LinkedHashMap 继承自 HashMap，所以它的底层仍然是基于拉链式散列结构即由数组和链表或红黑树组成。另外，LinkedHashMap 在上面结构的基础上，增加了一条双向链表，使得上面的结构可以保持键值对的插入顺序。同时通过对链表进行相应的操作，实现了访问顺序相关逻辑。详细可以查看：《LinkedHashMap 源码详细分析（JDK1.8）》open in new window
  • Hashtable： 数组+链表组成的，数组是 Hashtable 的主体，链表则是主要为了解决哈希冲突而存在的
  • TreeMap： 红黑树（自平衡的排序二叉树）

3、如何选用集合?

截屏2023-03-13 23.02.44

不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的时间复杂度都是 O(n) 。

二、Collection 子接口之 List

1、ArrayList 和 Vector 的区别?

线程安全和线程不安全

2、ArrayList 与 LinkedList 区别?

结合底层数据结构理解

  • 都是线程不安全
  • 底层数据结构：前者 Object 数组，后者双向链表
  • 插入和删除是否受元素位置的影响：
  • 是否支持快速随机访问：前者支持，后者不支持
  • 内存空间占用：ArrayList` 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

不要下意识地认为 LinkedList 作为链表就最适合元素增删的场景。我在上面也说了，LinkedList 仅仅在头尾插入或者删除元素的时候时间复杂度近似 O(1)，其他情况增删元素的时间复杂度都是 O(n) 。

3、说一说 ArrayList 的扩容机制吧

截屏2023-03-13 23.09.52

扩容调用的是grow()方法

三、Collection 子接口之 Set

1、comparable 和 Comparator 的区别

  • comparable 接口实际上是出自java.lang包 它有一个 compareTo(Object obj)方法用来排序
  • comparator接口实际上是出自 java.util 包它有一个compare(Object obj1, Object obj2)`方法用来排序

一般我们需要对一个集合使用自定义排序时，我们就要重写compareTo()方法或compare()方法

2、无序性和不可重复性的含义是什么

  • 无序性不等于随机性 ，无序性是指存储的数据在底层数组中并非按照数组索引的顺序添加 ，而是根据数据的哈希值决定的。
  • 不可重复性是指添加的元素按照 equals() 判断时 ，返回 false，需要同时重写 equals() 方法和 hashCode()方法。

3、比较 HashSet、LinkedHashSet 和 TreeSet 三者的异同

  • 都能保证元素唯一，并且都不是线程安全的。
  • 主要区别在于底层数据结构不同。
    • HashSet 的底层数据结构是哈希表（基于 HashMap 实现）。
    • LinkedHashSet 的底层数据结构是链表和哈希表，元素的插入和取出顺序满足 FIFO。
    • TreeSet 底层数据结构是红黑树，元素是有序的，排序的方式有自然排序和定制排序。

四、 Collection 子接口之 Queue

1、Queue 与 Deque 的区别

  • Queue 是单端队列，只能从一端插入元素，另一端删除元素，实现上一般遵循 先进先出（FIFO） 规则
  • Deque 是双端队列，在队列的两端均可以插入或删除元素。

在方法上的区别：

截屏2023-03-13 23.15.52

截屏2023-03-13 23.16.01

事实上，Deque 还提供有 push() 和 pop() 等其他方法，可用于模拟栈。

2、ArrayDeque 与 LinkedList 的区别

ArrayDeque 和 LinkedList 都实现了 Deque 接口，两者都具有队列的功能，但两者有什么区别呢？

  • ArrayDeque 是基于可变长的数组和双指针来实现，而 LinkedList 则通过链表来实现。
  • ArrayDeque 不支持存储 NULL 数据，但 LinkedList 支持。
  • ArrayDeque 是在 JDK1.6 才被引入的，而LinkedList 早在 JDK1.2 时就已经存在。
  • ArrayDeque 插入时可能存在扩容过程, 不过均摊后的插入操作依然为 O(1)。虽然 LinkedList 不需要扩容，但是每次插入数据时均需要申请新的堆空间，均摊性能相比更慢。

从性能的角度上，选用 ArrayDeque 来实现队列要比 LinkedList 更好。此外，ArrayDeque 也可以用于实现栈，但一般都用LinkedList来实现模拟栈。

3、说一说 PriorityQueue

PriorityQueue 是在 JDK1.5 中被引入的, 其与 Queue 的区别在于元素出队顺序是与优先级相关的，即总是优先级最高的元素先出队。

  • PriorityQueue 利用了二叉堆的数据结构来实现的，底层使用可变长的数组来存储数据
  • PriorityQueue 通过堆元素的上浮和下沉，实现了在 O(logn) 的时间复杂度内插入元素和删除堆顶元素。
  • PriorityQueue 是非线程安全的，且不支持存储 NULL 和 non-comparable 的对象。
  • PriorityQueue 默认是小顶堆，但可以接收一个 Comparator 作为构造参数，从而来自定义元素优先级的先后。

PriorityQueue 在面试中可能更多的会出现在手撕算法的时候，典型例题包括堆排序、求第K大的数、带权图的遍历等，所以需要会熟练使用才行。

五、Map接口

1、HashMap 和 Hashtable 的区别

  • 线程是否安全： HashMap 是非线程安全的，Hashtable 是线程安全的
  • 效率： 因为线程安全的问题，HashMap 要比 Hashtable 效率高一点。
  • 对 Null key 和 Null value 的支持： HashMap 可以存储 null 的 key 和 value，但 null 作为键只能有一个，null 作为值可以有多个；Hashtable 不允许有 null 键和 null 值，否则会抛出 `NullPointerException
  • 初始容量大小和每次扩充容量大小的不同：
    • 创建时如果不指定容量初始值，之后每次扩充，容量变为原来的 2n+1。，HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。
    • 创建时如果给定了容量初始值，那么 Hashtable 会直接使用你给定的大小，而 HashMap 会将其扩充为 2 的幂次方大小（HashMap 中的tableSizeFor()方法保证）。也就是说 HashMap 总是使用 2 的幂作为哈希表的大小,后面会介绍到为什么是 2 的幂次方（平均分布，减少碰撞，提高算法性能）

2、HashMap 和 HashSet 区别

HashSet 底层就是基于 HashMap 实现的，但部分方法不同，其中 clone()、writeObject()、readObject()是 HashSet 自己不得不实现的。截屏2023-03-13 23.27.30

3、HashMap 和 TreeMap 区别

TreeMap它还实现了NavigableMap接口和SortedMap 接口。

实现 NavigableMap 接口让 TreeMap 有了对集合内元素的搜索的能力。实现SortedMap接口让 TreeMap 有了对集合中的元素根据键排序的能力。默认是按 key 的升序排序，不过我们也可以指定排序的比较器。示例代码如下：

综上：相比于HashMap来说 TreeMap 主要多了对集合中的元素根据键排序的能力以及对集合内元素的搜索的能力。

4、HashSet 如何检查重复?

当你把对象加入HashSet时，HashSet 会先计算对象的hashcode值来判断对象加入的位置，同时也会与其他加入的对象的 hashcode 值作比较，如果没有相符的 hashcode，HashSet 会假设对象没有重复出现。但是如果发现有相同 hashcode 值的对象，这时会调用equals()方法来检查 hashcode 相等的对象是否真的相同。如果两者相同，HashSet 就不会让加入操作成功。

5、HashMap 的底层实现

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列

相比于之前的版本， JDK1.8 之后在解决哈希冲突时有了较大的变化，当链表长度大于阈值（默认为 8）（将链表转换成红黑树前会判断，如果当前数组的长度小于 64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间

6、HashMap 的长度为什么是 2 的幂次方

  • 为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量>把数据分配均匀。</span

  • 而且存储时，散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算，得到的余数才能用来要存放的位置也就是对应的数组下标。这个数组下标的计算方法是“ (n - 1) & hash”。取余(%)操作中如果除数是 2 的幂次则等价于与其除数减一的与(&)操作（也就是说 hash%length==hash&(length-1)的前提是 length 是 2 的 n 次方；）。”** 并且 采用二进制位操作 &，相对于%能够提高运算效率

7、HashMap 多线程操作导致死循环问题

主要原因在于并发下的 Rehash 会造成元素之间会形成一个循环链表。jdk 1.8 后解决了这个问题，但是还是不建议在多线程下使用 HashMap,因为多线程下使用 HashMap 还是会存在其他问题比如数据丢失

8、HashMap 有哪几种常见的遍历方式?

9、ConcurrentHashMap 和 Hashtable 的区别

主要在于实现线程安全的方式区别：

  • 底层数据结构：
    • ConcurrentHashMap：数组+链表/红黑二叉树
    • Hashtable： 数组+链表 。数组是 HashMap 的主体，链表则是主要为了解决哈希冲突而存在的；
  • 实现线程安全的方式：
    • jdk1.7：ConcurrentHashMap 对整个桶数组进行了分割分段——Segment分段锁。
    • jdk1.7之后：Node 数组+链表+红黑树的数据结构来实现，并发控制使用 synchronized 和 CAS 来操作。
    • Hashtable(同一把锁) ：使用 synchronized 来保证线程安全，效率非常低下

10、JDK 1.7 和 JDK 1.8 的 ConcurrentHashMap 实现有什么不同？

  • 线程安全实现方式 ：JDK 1.7 采用 Segment 分段锁来保证安全， Segment 是继承自 ReentrantLock。JDK1.8 放弃了 Segment 分段锁的设计，采用 Node + CAS + synchronized`` 保证线程安全，锁粒度更细，synchronized 只锁定当前链表或红黑二叉树的首节点。
  • Hash 碰撞解决方法 : JDK 1.7 采用拉链法，JDK1.8 采用拉链法结合红黑树（链表长度超过一定阈值时，将链表转换为红黑树）。
  • 并发度 ：JDK 1.7 最大并发度是 Segment 的个数，默认是 16。JDK 1.8 最大并发度是 Node 数组的大小，并发度更大。