Java八股文背诵第二天 java集合

kill bert

已于 2025-04-07 13:09:09 修改

阅读量651

点赞数 8

分类专栏：代码随想录算法训练营文章标签： java python 开发语言

于 2025-04-07 13:04:37 首次发布

本文链接：https://blog.csdn.net/sweeping_robot/article/details/147041595

版权

代码随想录算法训练营专栏收录该内容

58 篇文章

订阅专栏

Java 集合

Java的集合类有哪些
- Java 中的集合类主要由 Collection 和 Map 这两个接口派生而出，其中 Collection 接口又派生出三个子接口，分别是 Set、List、Queue。所有的 Java 集合类，都是 Set、List、Queue、Map 这四个接口的实现类，这四个接口将集合分成了四大类。
- Collection 接口：是所有集合框架的根接口，包含了对集合进行基本操作的方法。
- List 接口：有序集合，允许重复元素。常见的实现类有 ArrayList、LinkedList 等。
- Set 接口：不允许重复元素的集合。常见的实现类有 HashSet、LinkedHashSet、TreeSet 等。
- Queue 接口：用于表示队列的数据结构。常见的实现类有 LinkedList、PriorityQueue 等。
- Map 接口：表示键值对的集合。常见的实现类有 HashMap、LinkedHashMap、TreeMap 等。
哪些是线程安全的？哪些是线程不安全的？
- 线程安全：
  - Vector：一个古老的集合类，它的方法都是同步的，因此是线程安全的。然而，它相对较重，不够灵活，现在通常建议使用 ArrayList。
  - HashTable：一个古老的哈希表实现，其方法都是同步的，因此是线程安全的。但它的使用已经不太推荐，通常建议使用 HashMap。
  - Collections.synchronizedList、Collections.synchronizedSet、Collections.synchronizedMap：这些方法可以将非线程安全的集合包装成线程安全的集合。
- 线程不安全：
  - ArrayList、LinkedList、HashSet、HashMap：这些集合类是非线程安全的。在多线程环境中，如果没有适当的同步措施，对这些集合的并发操作可能导致不确定的结果。
  - TreeMap、TreeSet：虽然 TreeMap 和 TreeSet 是有序的集合，但它们也是非线程安全的。
ArrayList 和 Array 有什么区别
- 大小和自动扩容：
  - 数组在创建时必须指定大小，且大小是固定的。一旦数组被创建，其大小不能更改。
  - ArrayList 是动态数组实现的，它的大小可以动态增长或缩小。在不断添加元素时，会自动进行扩容。
- 支持泛型：
  - 数组可以存储任何类型的元素，但不支持泛型。
  - ArrayList 支持泛型，可以指定存储的元素类型。
- 存储对象：
  - 数组可以直接存储基本类型数据，也可以存储对象。
  - ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。
- 集合功能：
  - 数组是一个简单的数据结构，不提供额外的方法来进行元素的增删改查操作。
  - ArrayList 是集合框架的一部分，提供了丰富的方法，如添加、删除、查找等。
ArrayList 和 LinkedList 的区别是什么？底层实现是怎么样的？
- ArrayList：
  - 内部结构：基于动态数组的实现，可以提供快速的随机访问和非常快的遍历操作。
  - 性能：
    - 随机访问：由于基于数组，所以访问元素时有很高的效率，时间复杂度为 O(1)。
    - 添加/删除元素：在列表末尾添加元素通常很快，但在列表中间或开始插入或删除元素时，可能需要移动后续元素，时间复杂度为 O(n)。
    - 扩容开销：当数组容量不足以容纳更多元素时，ArrayList 会扩容，这个过程涉及创建新数组和复制旧数组的内容，有一定的开销。
  - 使用场景：当需要频繁地访问列表中的元素，且添加和删除操作主要在列表末尾进行时，ArrayList 是一个很好的选择。
- LinkedList：
  - 内部结构：基于双向链表的实现，每个元素都包含前一个和后一个元素的引用。
  - 性能：
    - 随机访问：访问元素时效率较低，因为需要从头开始或从尾开始通过链接遍历，时间复杂度为 O(n)。
    - 添加/删除元素：在列表任何位置添加或删除元素都很快，因为这只需要改变几个引用指针，通常是 O(1) 的时间复杂度，但如果要删除指定位置的元素，依然需要先遍历到那个位置。
    - 特殊方法：提供额外的方法，如 addLast()、addFirst()、removeFirst()、removeLast()，这些在 ArrayList 中不是优化过的操作。
  - 使用场景：当需要频繁地在列表中插入或删除元素，且元素访问操作不是那么常见时，LinkedList 是更好的选择。
ArrayList 扩容机制
- ArrayList 扩容的本质就是计算出新的扩容数组的 size 后实例化，并将原有数组内容复制到新数组中去。不是原数组，而是新数组然后给予数组对象地址并返回。
- 最小容量：ArrayList 的底层是用动态数组来实现的。我们初始化一个 ArrayList 集合还没有添加元素时，其实它是个空数组，只有当我们添加第一个元素时，内部会调用扩容方法。
- 当添加一个新元素到 ArrayList 时，ArrayList 会先判断当前存储元素的数组容量是否已经达到最大大小（即 Integer.MAX_VALUE），如果已经达到则不再扩容。否则会进行扩容。
- ArrayList 扩容的计算是在一个 grow() 方法里面，grow 方法先尝试将数组扩大为原数组的 1.5 倍。新容量 = 旧容量 + (旧容量 >> 1)（相当于除以 2）。
- 若新的容量满足需求，会调用一个 Arrays.copyOf 方法，这个方法是真正实现扩容的步骤。如果扩容后的新容量还是不满足需求，那么新容量大小为当前所需的容量加上 1。
Map 接口有哪些实现类
- HashMap：对于不需要排序的场景，优先考虑使用 HashMap，因为它是性能最好的 Map 实现。如果需要保证线程安全，则可以使用 ConcurrentHashMap。它的性能好于 Hashtable，因为它在 put 时采用分段锁/CAS的加锁机制，而不是像 Hashtable 那样，无论是 put 还是 get 都做同步处理。
- LinkedHashMap：如果需要按插入顺序排序，则可以使用 LinkedHashMap。
- TreeMap：如果需要将 key 按自然顺序排列甚至是自定义顺序排列，则可以选择 TreeMap。如果需要保证线程安全，则可以使用 Collections 工具类将上述实现类包装成线程安全的 Map。
Java中的HashMap了解吗？HashMap 的底层实现
- HashMap 将数据以键值对的形式存储，是线程不安全的。
- JDK 7 中的 HashMap 使用的是数组 + 链表的实现方式，即拉链法。在 JDK 7 版本中，因为使用链表，在出现哈希冲突时，会在冲突位置形成链表，将新增元素加入到链表中，带来的问题是，在冲突过多的情况下，链表可能会特别长，导致复杂度无限接近于 O(N)。
- JDK 8 引入了红黑树，链表长度超过 8 时，会将链表转换为红黑树，以提高在链表长度较长时的查找性能。这种结构被称为树化桶（Tree Bins）。总结：Java 7 使用数组 + 链表，Java 8 使用数组 + 链表或红黑树（链表超过 8 会转为红黑树，小于 6 会变成链表）。
- 为什么链表大小超过 8 会自动转为红黑树，小于 6 时重新变成链表：
  - 根据泊松分布，在负载因子默认为 0.75 的时候，单个 hash 槽内元素个数为 8 的概率小于百万分之一，所以将 7 作为一个分水岭，等于 7 的时候不转换，大于等于 8 的时候才转换成红黑树，小于等于 6 的时候转化为链表。
- 为什么要引入红黑树，而不用其他树：
  - 在替换链表时，常用的数据结构是二叉树，但是二叉树一定是左 < 根 < 右。在时间复杂度中从链表的 O(N) 变成 O(logN)。在极端情况下，会出现左右其中一边无限长，导致退化到链表。基于此情况衍生出平衡二叉树，通过在添加元素时进行左旋、右旋操作维持根节点左右两端的平衡。但是因为为了保证两端的平衡，在数据量较大的插入删除时，会存在大量的 IO 开销。
  - 引入红黑树，是因为红黑树具有以下几点性质：
    - 不追求绝对的平衡，插入或删除节点时，允许有一定的局部不平衡，相较于 AVL 树的绝对自平衡，减少了很多性能开销。
    - 红黑树是一种自平衡的二叉搜索树，因此插入和删除操作的时间复杂度都是 O(log n)。
- 红黑树和二叉搜索树、AVL 树有什么区别：
  - 红黑树：节点颜色为红色或黑色，且根节点和叶子节点为黑色；任意一个红色节点的子节点是黑色；插入和删除操作的时间复杂度都是 O(log n)。
  - 二叉搜索树：在最坏的情况下，二叉搜索树的时间复杂度为 O(n)；树不会平衡，不会进行旋转操作，达不到自平衡。
  - AVL 树：由于 AVL 树保持平衡性，查找、插入和删除操作的时间复杂度都是 O(log n)；插入和删除节点时，会发生旋转操作，达到自平衡。
- HashMap 会出现红黑树一直增高变成无限高的情况吗？
  - 不会无限增高，当链表长度超过 8 时，链表转换为红黑树，当不足这个阈值时，重新转换为链表。这种动态机制防止了红黑树的无限增长。
- HashMap 读和写的时间复杂度是多少？
  - 读：
    - 在最佳情况下：直接通过数组下标访问数据，O(1)。
    - 在最坏情况下：发生哈希冲突，链表为 O(n)，红黑树为 O(log n)。
  - 写：O(1)，但是如果所有元素都在一个桶内，则每次插入需要 O(n)。
Hash 冲突有什么解决方式？HashMap 是如何解决 hash 冲突的
- 哈希表为解决冲突，可以采用开放地址法和链地址法来解决问题。
- 开放地址法（也称为再散列法）：
  - 基本思想是：当关键字 key 的哈希地址 p = H(key) 出现冲突时，以 p 为基础，产生另一个哈希地址 p'，如果 p' 仍然冲突，再以 p' 为基础，产生另一个哈希地址 p''，……，直到找出一个不冲突的哈希地址 pi，将相应元素存入其中。这种方法有一个通用的再散列函数形式：
    - Hi = (H(key) + di) % m，其中 H(key) 为哈希函数，m 为表长，di 称为增量序列。增量序列的取值方式不同，相应的再散列方式也不同。主要有以下几种：
      - 线性探测再散列：di = 1, 2, 3, …, m-1。这种方法的特点是：冲突发生时，顺序查看表中下一单元，直到找出一个空单元或查遍全表。
      - 二次探测再散列：di = 1², -1², 2², -2², …, k², -k²（k < m/2）。这种方法的特点是：冲突发生时，在表的左右进行跳跃式探测，比较灵活。
      - 伪随机探测再散列：di 为伪随机数序列。具体实现时，应建立一个伪随机数发生器，如 i = (i + p) % m，并给定一个随机数做起点。
  - 例如，已知哈希表长度 m = 10，哈希函数为 H(key) = key % 10，则 H(47) = 7，H(2) = 2，H(5) = 5，假设下一个关键字为 57，则 H(57) = 7，与 47 冲突。
    - 如果用线性探测再散列处理冲突，下一个哈希地址为 H(57) = (7 + 1) % 10 = 8，仍然冲突，再找下一个哈希地址为 H(57) = (7 + 2) % 10 = 9，还是冲突，继续找下一个哈希地址为 H(57) = (7 + 3) % 10 = 0，此时不再冲突，将 57 填入 0 号单元。
    - 如果用二次探测再散列处理冲突，下一个哈希地址为 H(57) = (7 + 1²) % 10 = 8，仍然冲突，再找下一个哈希地址为 H(57) = (7 - 1²) % 10 = 6，此时不再冲突，将 57 填入 6 号单元。
    - 如果用伪随机探测再散列处理冲突，且伪随机数序列为：2, 5, 3, …，则下一个哈希地址为 H(57) = (7 + 2) % 10 = 9，仍然冲突，再找下一个哈希地址为 H(57) = (7 + 5) % 10 = 2，此时不再冲突，将 57 填入 2 号单元。
- 链地址法（也称为拉链法）：
  - 简单来说就是数组和链表的结合，在每个数组元素上都有一个链表结构，数据被 Hash 后得到数组下标，把数据放在对应下标元素的链表上。
  - Java 中的 HashMap 使用链地址法。
HashMap 的 put 方法流程
- 判断数组是否为空，为空进行初始化。
- 不为空，计算 key 的 hash 值，通过 n - 1 & hash 计算应当存放在数组中的下标 index。
- 查看 table[index] 是否存在数据，没有数据就构造一个 Node 节点存放在 table[index] 中。
- 存在数据，说明发生 hash 冲突（存在一个节点 KEY 的 hash 值一样），继续判断 key 是否相等，相等，用新的 value 替换原数据（onlyIfAbsent 为 false）。
- 如果不相等，判断当前节点类型是不是树型节点，如果是树型节点，创造树型节点插入红黑树中（如果当前节点是树型节点证明当前已经是红黑树）。
- 如果不是树型节点，创建普通 Node 加入链表中；判断链表长度是否大于 8 并且数组长度大于 4，大于的话链表转换为红黑树。
- 插入完成之后判断当前节点数是否大于阈值，如果大于开始扩容为原数组的 2 倍。
HashMap 的扩容机制
- JDK 1.7 扩容机制：
  - 生成新数组。
  - 遍历老数组中的每个位置上的链表上的每个元素。
  - 获取每个元素的 key，并基于新数组长度，计算出每个元素在新数组中的下标。
  - 将元素添加到新数组中去。
  - 所有元素转移完之后，将新数组赋值给 HashMap 对象的 table 属性。
- JDK 1.8 扩容机制：
  - 生成新数组。
  - 遍历老数组中的每个位置上的链表或红黑树。
    - 如果是链表，则直接将链表中的每个元素重新计算下标，并添加到新数组中去。
    - 如果是红黑树，则先遍历红黑树，先计算出红黑树中每个元素对应在新数组中的下标位置。
      - 统计每个下标位置的元素个数。
      - 如果该位置下的元素个数超过了 8，则生成一个新的红黑树，并将根节点添加到新数组的对应位置。
      - 如果该位置下的元素个数没有超过 8，那么则生成一个链表，并将链表的头节点添加到新数组的对应位置。
  - 所有元素转移完了之后，将新数组赋值给 HashMap 对象的 table 属性。
HashMap 为什么是线程不安全的？如何实现线程安全
- 为什么是线程不安全的：
  - 主要原因是它的操作不是原子的，即在多个线程同时进行读写操作时，可能会导致数据不一致或抛出异常。
  - 并发修改：当一个线程进行写操作（插入、删除等）时，另一个线程进行读操作，可能会导致读取到不一致的数据，甚至抛出 ConcurrentModificationException 异常。
  - 非原子性操作：HashMap 的一些操作不是原子的，例如，检查是否存在某个键、获取某个键对应的值等，这样在多线程环境中可能发生竞态条件。
- 如何实现线程安全：
  - 使用 ConcurrentHashMap：ConcurrentHashMap 是专门设计用于线程环境的哈希表实现。它使用分段锁机制，允许多个线程同时进行读操作，提高并发性能。
  - 使用锁机制：可以在自定义的 HashMap 操作中使用显式的锁，例如：
    - 使用 Collections.synchronizedMap() 方法：可以通过 Collections.synchronizedMap() 方法创建一个线程安全的 HashMap，该方法返回一个同步的 Map 包装器，使得所有对 Map 的操作都是同步的。
    - 使用 ReentrantLock：为实现线程安全的 HashMap，可以使用 ReentrantLock 来保证线程安全。
ConcurrentHashMap 如何保证线程安全
- JDK 1.7 中的 ConcurrentHashMap：
  - 使用数组 + 链表的结构，其中数组分为两类：Segment（分段锁）和 HashEntry（哈希表的节点）。
  - 线程安全是建立在 Segment 加 ReentrantLock 重入锁来保证的。
- JDK 1.8 中的 ConcurrentHashMap：
  - 使用数组 + 链表 + 红黑树的方式实现。
  - 它是通过 CAS 或者 synchronized 来保证线程安全的，并且缩小了锁的粒度，查询性能也更高。
HashSet 和 HashMap 和 Hashtable 的区别
- HashMap 和 Hashtable 的区别：
  - 同步：
    - Hashtable 是同步的，即它的方法是线程安全的。这是通过在每个方法上添加同步关键字来实现的，但这也可能导致性能下降。
    - HashMap 不是同步的，因此它不保证在多线程环境中的线程安全性。如果需要同步，可以使用 Collections.synchronizedMap() 方法来创建一个同步的 HashMap。
  - 性能：
    - 由于 Hashtable 是同步的，它在多线程环境中的性能可能较差。
    - HashMap 在单线程环境中可能比 Hashtable 更快，因为它没有同步开销。
  - 空值：
    - Hashtable 不允许键或值为 null。
    - HashMap 允许键和值都为 null。
  - 继承关系：
    - Hashtable 是 Dictionary 类的子类，而 HashMap 是 AbstractMap 类的子类，实现了 Map 接口。
  - 迭代器：
    - Hashtable 的迭代器是通过 Enumerator 实现的。
    - HashMap 的迭代器是通过 Iterator 实现的。
  - 初始容量和加载因子：
    - Hashtable 的初始容量和加载因子是固定的。
    - HashMap 允许通过构造方法设置初始容量和加载因子，以便更好地调整性能。
- HashMap 和 HashSet 的区别：
  - 使用：
    - HashMap 用于存储键值对，其中每个键都唯一，每个键关联一个值。
    - HashSet 用于存储唯一的元素，不允许重复。
  - 内部实现：
    - HashMap 使用键值对的方式存储数据，通过哈希表实现。
    - HashSet 实际上是基于 HashMap 实现的，它只使用了 HashMap 的键部分，将值部分设置为一个固定的常量。
  - 元素类型：
    - HashMap 存储键值对，可以通过键获取对应的值。
    - HashSet 存储单一元素，只能通过元素本身进行操作。
  - 允许 null：
    - HashMap 允许键和值都为 null。
    - HashSet 允许存储一个 null 元素。
  - 迭代方式：
    - HashMap 的迭代是通过迭代器或增强型 for 循环遍历键值对。
    - HashSet 的迭代是通过迭代器或增强型 for 循环遍历元素。
  - 关联关系：
    - HashMap 中的键与值是一一对应的关系。
    - HashSet 中的元素没有关联的值，只有元素本身。
  - 性能影响：
    - HashMap 的性能受到键的哈希分布和哈希冲突的影响。
    - HashSet 的性能也受到元素的哈希分布和哈希冲突的影响，但由于它只存储键，通常比 HashMap 的性能稍好。
HashMap 和 ConcurrentHashMap 的区别
- 线程安全性：
  - HashMap 不是线程安全的。在多线程环境中，如果同时进行读写操作，可能会导致数据不一致或抛出异常。
  - ConcurrentHashMap 是线程安全的。它使用分段锁（segment）机制，将整个数据结构分成多个段，每个段都有自己的锁。这样，不同的线程可以同时访问不同的段，提高并发性能。
- 同步机制：
  - HashMap 在实现上没有明确的同步机制，需要在外部进行同步，例如通过使用 Collections.synchronizedMap() 方法。
  - ConcurrentHashMap 内部使用一种更细粒度的锁机制，因此在多线程环境中具有更好的性能。
- 迭代时是否需要加锁：
  - 在 HashMap 中，如果在迭代过程中有其他线程对其进行修改，可能会抛出 ConcurrentModificationException 异常。
  - ConcurrentHashMap 允许在迭代时进行并发的插入和删除操作，而不会抛出异常。但是，它并不保证迭代器的顺序，因为不同的段可能会以不同的顺序完成操作。
- 初始化容量和负载因子：
  - HashMap 可以通过构造方法设置初始容量和负载因子。
  - ConcurrentHashMap 在 Java 8 及之后版本中引入。它可以通过构造方法设置初始容量、负载因子和并发级别。
- 性能：
  - 在低并发情况下，HashMap 的性能可能会比 ConcurrentHashMap 稍好，因为 ConcurrentHashMap 需要维护额外的并发控制。
  - 在高并发情况下，ConcurrentHashMap 的性能通常更好，因为它能够更有效地支持并发访问。