java 集合

xuyong2024年12月27日大约 7 分钟

java 集合相关内容

1. 集合框架概述

Java 集合框架提供了一套性能优良、使用方便的接口和类，用于存储和操作对象组。它位于 java.util 包下，集合框架主要解决了以下问题：

提供了对对象的存储、检索、修改等通用操作，避免了开发者重复造轮子。
不同类型的集合适用于不同场景，方便开发者根据需求选择最合适的数据结构，提高程序性能。

集合框架主要接口有 Collection、List、Set、Map，其中 Collection 是集合层次结构中的根接口，List 和 Set 继承自它，Map 是独立的接口用于存储键值对。

2. Collection 接口

2.1. 特点

Collection 是最基本的集合接口，它定义了一些通用的集合操作方法，如添加元素、删除元素、判断元素是否存在、遍历集合等。它不包含关于元素存储顺序或是否包含重复元素的假设，这些特性由具体的子接口和实现类来定义。

2.2. 常用方法

boolean add(E e); // 向集合中添加元素，成功返回 true，若集合不允许添加重复元素且已存在相同元素则返回 false
boolean remove(Object o); // 从集合中移除指定元素，若元素存在并移除成功返回 true，否则返回 false
boolean contains(Object o); // 判断集合是否包含指定元素，包含返回 true，否则返回 false
int size(); // 返回集合中元素的个数
boolean isEmpty(); // 判断集合是否为空，为空返回 true，否则返回 false
Iterator<E> iterator(); // 返回一个迭代器，用于遍历集合中的元素

3. List 接口及实现类

3.1. 特点

List 是有序的集合，元素可以重复。用户可以通过索引（位置）来访问、插入、删除和替换列表中的元素，索引从 0 开始。

3.2. 常用实现类

ArrayList：
- 底层基于数组实现，查询效率高，时间复杂度为 O(1)，因为可以通过数组下标直接定位元素。
- 插入和删除操作相对较慢，平均时间复杂度为 O(n)，因为需要移动数组元素。
- 动态扩容机制：当数组容量不足时，会自动创建一个更大的新数组，并将原数组元素复制过去。初始容量默认为 10，扩容因子为 1.5 倍。

ArrayList<String> arrayList = new ArrayList<>();
arrayList.add("apple");
arrayList.add("banana");
String element = arrayList.get(0); // 获取索引为 0 的元素，即 "apple"

LinkedList：
- 底层基于双向链表实现，插入和删除操作效率高，时间复杂度为 O(1)，只需修改节点间的引用关系。
- 查询效率低，时间复杂度为 O(n)，因为需要遍历链表查找元素。
- 提供了一些操作链表头部和尾部的便捷方法，如 addFirst、addLast、removeFirst、removeLast 等。

LinkedList<Integer> linkedList = new LinkedList<>();
linkedList.add(1);
linkedList.add(2);
linkedList.addFirst(0); // 在链表头部添加元素 0

4. Set 接口及实现类

4.1. 特点

Set 是不包含重复元素的集合，它的实现类通常基于某种数据结构保证元素的唯一性。元素无序（部分实现类有特殊排序规则，如 TreeSet）。

4.2. 常用实现类

HashSet：
- 基于哈希表实现，通过 hashCode 和 equals 方法来确定元素的唯一性。添加、删除、查询操作的平均时间复杂度接近 O(1)。
- 不保证元素的顺序，迭代时元素的顺序可能与添加顺序不同。

HashSet<Character> hashSet = new HashSet<>();
hashSet.add('a');
hashSet.add('b');
hashSet.add('a'); // 重复元素，不会被添加

TreeSet：
- 基于红黑树实现，元素默认按照自然顺序（实现 Comparable 接口定义的顺序）或自定义比较器 Comparator 进行排序。
- 插入、删除、查询操作的时间复杂度为 O(log n)，性能相对稳定。适用于需要对元素排序的场景。

TreeSet<Integer> treeSet = new TreeSet<>();
treeSet.add(3);
treeSet.add(1);
treeSet.add(2); 
// 元素按升序排列，遍历结果为 1, 2, 3

5. Map 接口及实现类

5.1. 特点

Map 用于存储键值对（key-value）形式的数据，键具有唯一性，一个键对应一个值。通过键可以快速检索、更新和删除对应的值。

5.2. 常用实现类

HashMap：
- 基于哈希表实现，提供了快速的插入、删除和查找操作，时间复杂度接近 O(1)。
- 允许键和值为 null，键最多只能有一个 null 值，因为键必须唯一。
- 当哈希冲突严重时，性能可能会下降，哈希冲突指不同键计算出相同的哈希码。

HashMap<String, Integer> hashMap = new HashMap<>();
hashMap.put("apple", 1);
hashMap.put("banana", 2);
Integer value = hashMap.get("apple"); // 获取键 "apple" 对应的值 1

TreeMap：
- 基于红黑树实现，键按照自然顺序或自定义比较器排序，遍历 TreeMap 时会按照键的顺序输出。
- 插入、删除、查找操作的时间复杂度为 O(log n)，适用于需要按键排序输出的场景。键不能为 null，否则会抛出 NullPointerException。

TreeMap<String, Double> treeMap = new TreeMap<>();
treeMap.put("orange", 3.5);
treeMap.put("grape", 2.0);
// 按键升序遍历，输出顺序与键的排序一致

6. 迭代器（Iterator）

迭代器用于遍历集合中的元素，它提供了一种统一的方式来访问集合元素，而不需要了解集合的内部结构。

Collection<String> collection = new ArrayList<>();
collection.add("one");
collection.add("two");
Iterator<String> iterator = collection.iterator();
while (iterator.hasNext()) {
    String element = iterator.next();
    System.out.println(element);
}

通过 hasNext 方法判断是否还有下一个元素，next 方法获取下一个元素并将迭代器指针后移一位。注意，在迭代过程中，不能使用集合的修改方法（如 add、remove），否则可能会抛出 ConcurrentModificationException，如需修改，推荐使用迭代器自身的 remove 方法。

7. 面试题

7.1. ArrayList 和 LinkedList 的区别？

数据结构：ArrayList 基于数组，LinkedList 基于双向链表。
访问效率：ArrayList 查询快（O(1)），LinkedList 查询慢（O(n)）。
插入删除效率：ArrayList 插入删除中间元素慢（O(n)），LinkedList 头部或尾部插入删除快（O(1)）。
内存占用：ArrayList 连续内存空间，LinkedList 节点除数据额外存储前后节点引用，内存占用稍高。

class MyKey {
    private int id;
    private String name;

    public MyKey(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass()!= o.getClass()) return false;
        MyKey myKey = (MyKey) o;
        return id == myKey.id && Objects.equals(name, myKey.name);
    }
}

确保 hashCode 返回值能均匀分布，且 equals 方法能准确判断两个对象的逻辑相等性，这样 HashMap 才能正确处理自定义键的存储、检索和唯一性判断。