跳到主要内容

Java集合

一、集合概述​

1. Java集合概述​

Java 集合，也叫作容器，主要是由两大接口派生而来：

  • 一个是 Collection接口，主要用于存放单一元素；
    • 下面又有三个主要的子接口：List、Set 、 Queue。
  • 另一个是 Map 接口，主要用于存放键值对。

2. 说说 List, Set, Queue, Map 四者的区别？​

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

3. 集合框架底层数据结构总结​

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

List​

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

Set​

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

Queue​

  • PriorityQueue: Object[] 数组来实现小顶堆。
  • DelayQueue:PriorityQueue。
  • ArrayDeque: 可扩容动态双向数组。

再来看看 Map 接口下面的集合。

Map​

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

4. 如何选用集合?​

我们主要根据集合的特点来选择合适的集合。比如：

  • 我们需要根据键值获取到元素值时就选用 Map 接口下的集合，需要排序时选择 TreeMap,不需要排序时就选择 HashMap,需要保证线程安全就选用 ConcurrentHashMap。
  • 我们只需要存放元素值时，就选择实现Collection 接口的集合，需要保证元素唯一时选择实现 Set 接口的集合比如 TreeSet 或 HashSet，不需要就选择实现 List 接口的比如 ArrayList 或 LinkedList，然后再根据实现这些接口的集合的特点来选用。

5. 为什么要使用集合？​

  • 当我们需要存储一组类型相同的数据时，数组是最常用且最基本的容器之一。
  • 但是，使用数组存储对象存在一些不足之处，因为在实际开发中，存储的数据类型多种多样且数量不确定。这时，Java 集合就派上用场了。
  • 相较于数组，Java 集合的优势在于它们的大小可变、支持泛型、具有内建算法等。
  • 总的来说，Java 集合提高了数据的存储和处理灵活性，可以更好地适应现代软件开发中多样化的数据需求，并支持高质量的代码编写。

二、List​

1. ArrayList和 Array（数组）的区别？​

ArrayList 内部基于动态数组实现，比 Array （静态数组） 使用起来更加灵活：

  • ArrayList 会根据实际存储的元素动态地扩容或缩容，而 Array 被创建之后就不能改变 它的长度了。
  • ArrayList 允许你使用泛型来确保类型安全， Array 则不可以。
  • ArrayList 中只能存储对象。对于基本类型数据，需要使用其对应的包装类（如 Integer、Double 等）。Array 可以直接存储`基本类型数据，也可以存储对象。
  • ArrayList 支持插入、删除、遍历等常见操作，并且提供了丰富的 API 操作方法，比如 add() 、 remove() 等。 Array 只是一个固定长度的数组，只能按照下标访问其中的元 素，不具备动态添加、删除元素的能力。
  • ArrayList 创建时不需要指定大小，而 Array 创建时必须指定大小。

2. ArrayList可以添加 null 值吗？​

ArrayList 中可以存储任何类型的对象，包括 null 值。不过，不建议向 ArrayList 中添 加 null 值， null 值无意义，会让代码难以维护。比如忘记做判空处理就会导致空指针异 常。

3. ArrayList 插入和删除元素的时间复杂度？​

对于插入：

  • 头部插入：由于需要将所有元素都依次向后移动一个位置，因此时间复杂度是 O(n)。
  • 尾部插入：当 ArrayList 的容量未达到极限时，往列表末尾插入元素的时间复杂度是 O(1)，因为它只需要在数组末尾添加一个元素即可；当容量已达到极限并且需要扩容时，则需要执行一次 O(n) 的操作将原数组复制到新的更大的数组中，然后再执行 O(1) 的操作添加元素。
  • 指定位置插入：需要将目标位置之后的所有元素都向后移动一个位置，然后再把新元素放入指定位置。这个过程需要移动平均 n/2 个元素，因此时间复杂度为 O(n)。

对于删除：

  • 头部删除：由于需要将所有元素依次向前移动一个位置，因此时间复杂度是 O(n)。
  • 尾部删除：当删除的元素位于列表末尾时，时间复杂度为 O(1)。
  • 指定位置删除：需要将目标元素之后的所有元素向前移动一个位置以填补被删除的空白位置，因此需要移动平均 n/2 个元素，时间复杂度为 O(n)。

4. LinkedList 插入和删除元素的时间复杂度？​

  • 头部插入/删除：只需要修改头结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
  • 尾部插入/删除：只需要修改尾结点的指针即可完成插入/删除操作，因此时间复杂度为 O(1)。
  • 指定位置插入/删除：需要先移动到指定位置，再修改指定节点的指针完成插入/删除，不过由于有头尾指针，可以从较近的指针出发，因此需要遍历平均 n/4 个元素，时间复杂度为 O(n)。

5. LinkedList 为什么不能实现 RandomAccess 接口？​

RandomAccess 是一个标记接口，用来表明实现该接口的类支持随机访问（即可以通过索引快速访问元素）。由于 LinkedList 底层数据结构是链表，内存地址不连续，只能通过指针来定位，不支持随机快速访问，所以不能实现 RandomAccess 接口。

6. ArrayList 与 LinkedList 区别?​

  • 是否保证线程安全： ArrayList 和 LinkedList 都是不同步的，也就是不保证线程安全；
  • 底层数据结构： ArrayList 底层使用的是 Object 数组；LinkedList 底层使用的是 双向链表 数据结构（JDK1.6 之前为循环链表，JDK1.7 取消了循环。注意双向链表和双向循环链表的区别，下面有介绍到！）
  • 插入和删除是否受元素位置的影响：
    • ArrayList 采用数组存储，所以插入和删除元素的时间复杂度受元素位置的影响。 比如：执行add(E e)方法的时候， ArrayList 会默认在将指定的元素追加到此列表的末尾，这种情况时间复杂度就是 O(1)。但是如果要在指定位置 i 插入和删除元素的话（add(int index, E element)），时间复杂度就为 O(n)。因为在进行上述操作的时候集合中第 i 和第 i 个元素之后的(n-i)个元素都要执行向后位/向前移一位的操作。
    • LinkedList 采用链表存储，所以在头尾插入或者删除元素不受元素位置的影响（add(E e)、addFirst(E e)、addLast(E e)、removeFirst()、 removeLast()），时间复杂度为 O(1)，如果是要在指定位置 i 插入和删除元素的话（add(int index, E element)，remove(Object o),remove(int index)）， 时间复杂度为 O(n) ，因为需要先移动到指定位置再插入和删除。
  • 是否支持快速随机访问： LinkedList 不支持高效的随机元素访问，而 ArrayList（实现了 RandomAccess 接口） 支持。快速随机访问就是通过元素的序号快速获取元素对象(对应于get(int index)方法)。
  • 内存空间占用： ArrayList 的空间浪费主要体现在在 list 列表的结尾会预留一定的容量空间，而 LinkedList 的空间花费则体现在它的每一个元素都需要消耗比 ArrayList 更多的空间（因为要存放直接后继和直接前驱以及数据）。

我们在项目中一般是不会使用到 LinkedList 的，需要用到 LinkedList 的场景几乎都可以使用 ArrayList 来代替，并且，性能通常会更好！

三、Set​

四、Queue​

五、Map​

1. HashMap 和 HashSet 区别​

HashSet 底层就是基于 HashMap 实现的。（HashSet 的源码非常非常少，因为除了 clone()、writeObject()、readObject()是 HashSet 自己不得不实现之外，其他方法都是直接调用 HashMap 中的方法。

image-20250306160526687

2. HashMap 和 TreeMap 区别​

TreeMap 和HashMap 都继承自AbstractMap ，但是需要注意的是TreeMap它还实现了NavigableMap接口和SortedMap 接口。

3. HashSet 如何检查重复?​

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

在 JDK1.8 中，实际上无论HashSet中是否已经存在了某元素，HashSet都会直接插入，只是会在add()方法的返回值处告诉我们插入前是否存在相同元素。

4. HashMap 的底层实现​

JDK1.8 之前​

JDK1.8 之前 HashMap 底层是 数组和链表 结合在一起使用也就是 链表散列。HashMap 通过 key 的 hashcode 经过扰动函数处理过后得到 hash 值，然后通过 (n - 1) & hash 判断当前元素存放的位置（这里的 n 指的是数组的长度），如果当前位置存在元素的话，就判断该元素与要存入的元素的 hash 值以及 key 是否相同，如果相同的话，直接覆盖，不相同就通过拉链法解决冲突。

HashMap 中的扰动函数（hash 方法）是用来优化哈希值的分布。通过对原始的 hashCode() 进行额外处理，扰动函数可以减小由于糟糕的 hashCode() 实现导致的碰撞，从而提高数据的分布均匀性

JDK1.8 之后​

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

5. HashMap 的长度为什么是 2 的幂次方​

  • 位运算效率更高：位运算(&)比取余运算(%)更高效。当长度为 2 的幂次方时，hash % length 等价于 hash & (length - 1)。
  • 可以更好地保证哈希值的均匀分布：扩容之后，在旧数组元素 hash 值比较均匀的情况下，新数组元素也会被分配的比较均匀，最好的情况是会有一半在新数组的前半部分，一半在新数组后半部分。
  • 扩容机制变得简单和高效：扩容后只需检查哈希值高位的变化来决定元素的新位置，要么位置不变（高位为 0），要么就是移动到新位置（高位为 1，原索引位置+原容量）。

6. HashMap 多线程操作导致死循环问题​

JDK1.7 及之前版本的 HashMap 在多线程环境下扩容操作可能存在死循环问题，这是由于当一个桶位中有多个元素需要进行扩容时，多个线程同时对链表进行操作，头插法可能会导致链表中的节点指向错误的位置，从而形成一个环形链表，进而使得查询元素的操作陷入死循环无法结束。

为了解决这个问题，JDK1.8 版本的 HashMap 采用了尾插法而不是头插法来避免链表倒置，使得插入的节点永远都是放在链表的末尾，避免了链表中的环形结构。但是还是不建议在多线程下使用 HashMap，因为多线程下使用 HashMap 还是会存在数据覆盖的问题。并发环境下，推荐使用 ConcurrentHashMap 。

7. HashMap 为什么线程不安全？​

JDK1.7 及之前版本，在多线程环境下，HashMap 扩容时会造成死循环和数据丢失的问题。

数据丢失这个在 JDK1.7 和 JDK 1.8 中都存在，这里以 JDK 1.8 为例进行介绍。

JDK 1.8 后，在 HashMap 中，多个键值对可能会被分配到同一个桶（bucket），并以链表或红黑树的形式存储。多个线程对 HashMap 的 put 操作会导致线程不安全，具体来说会有数据覆盖的风险。

8. HashMap 常见的遍历方式?​

1. 使用 entrySet()​

entrySet() 方法返回一个包含所有键值对的集合，可以通过增强的 for 循环遍历。

HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

2. 使用 keySet()​

keySet() 方法返回一个包含所有键的集合，可以遍历键并通过键获取对应的值。

for (String key : map.keySet()) {
    System.out.println("Key: " + key + ", Value: " + map.get(key));
}

3. 使用 values()​

values() 方法返回一个包含所有值的集合，可以直接遍历值。

for (Integer value : map.values()) {
    System.out.println("Value: " + value);
}

4. 使用 Java 8 的 forEach 方法​

Java 8 引入了 forEach 方法，可以使用 Lambda 表达式简化遍历过程。

map.forEach((key, value) -> {
    System.out.println("Key: " + key + ", Value: " + value);
});

5. 使用迭代器​

可以使用 Iterator 遍历 entrySet()、keySet() 或 values()。

Iterator<Map.Entry<String, Integer>> iterator = map.entrySet().iterator();
while (iterator.hasNext()) {
    Map.Entry<String, Integer> entry = iterator.next();
    System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());
}

6. 使用 Stream API​

在 Java 8 及更高版本中，可以使用 Stream API 进行更复杂的操作。

map.entrySet().stream()
    .filter(entry -> entry.getValue() > 1) // 过滤条件
    .forEach(entry -> System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue()));