Java 编码系列：集合框架（List、Set、Map 及其常用实现类）

🕗 发布于 2024-09-22 23:23 java list map

引言

在 Java 开发中，集合框架是不可或缺的一部分，它提供了存储和操作一组对象的工具。Java 集合框架主要包括 List、Set 和 Map 接口及其常用的实现类。正确理解和使用这些集合类不仅可以提高代码的可读性和性能，还能避免一些常见的错误。本文将深入探讨 Java 集合框架的底层原理，并结合大厂的最佳实践，帮助读者掌握这些核心概念。

1. List 接口及其常用实现类

1.1 基本概念

List 接口表示一个有序的集合，允许重复元素。List 中的每个元素都有一个索引，可以通过索引来访问和修改元素。

1.2 常用实现类

ArrayList：基于动态数组实现，支持快速随机访问，但在中间位置插入或删除元素时性能较差。
LinkedList：基于双向链表实现，支持快速插入和删除操作，但在随机访问时性能较差。
Vector：类似于 ArrayList，但线程安全，性能较差。
Stack：继承自 Vector，实现了栈数据结构。

1.3 底层原理

ArrayList：
- 内部实现：ArrayList 内部使用一个动态数组 Object[] elementData 来存储元素。
- 扩容机制：当数组容量不足时，会自动扩容，新容量通常是原容量的 1.5 倍。
```
ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add("B");
list.add("C");

System.out.println(list); // [A, B, C]
System.out.println(list.get(1)); // B
```
LinkedList：
- 内部实现：LinkedList 内部使用双向链表来存储元素，每个节点包含一个元素值、一个指向前一个节点的引用和一个指向后一个节点的引用。
- 插入和删除：在链表头部或尾部插入和删除元素的时间复杂度为 O(1)，但在中间位置插入和删除元素的时间复杂度为 O(n)。
```
LinkedList<String> list = new LinkedList<>();
list.addFirst("A");
list.addLast("C");
list.add(1, "B");

System.out.println(list); // [A, B, C]
System.out.println(list.get(1)); // B
```

1.4 常见操作

添加元素：

add(E e)：在列表末尾添加元素。
add(int index, E e)：在指定位置插入元素。

ArrayList<String> list = new ArrayList<>();
list.add("A");
list.add(0, "B");

System.out.println(list); // [B, A]

删除元素：

remove(int index)：删除指定位置的元素。
remove(Object o)：删除第一个匹配的元素。

ArrayList<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
list.remove(1);
list.remove("C");

System.out.println(list); // [A]

获取元素：

get(int index)：获取指定位置的元素。

ArrayList<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));
String element = list.get(1);

System.out.println(element); // B

遍历元素：

使用 for 循环：
使用 Iterator：

ArrayList<String> list = new ArrayList<>(Arrays.asList("A", "B", "C"));

// 使用 for 循环
for (int i = 0; i < list.size(); i++) {
    System.out.println(list.get(i));
}

// 使用 Iterator
Iterator<String> iterator = list.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

1.5 最佳实践

选择合适的实现类：
- ArrayList：适用于需要频繁随机访问的场景。
- LinkedList：适用于需要频繁插入和删除操作的场景。
初始化容量：
- ArrayList：如果已知元素数量，可以初始化容量，减少扩容次数。
```
ArrayList<String> list = new ArrayList<>(100);
```
使用 List 接口：
- 代码复用：在方法签名中使用 List 接口，而不是具体的实现类，提高代码的复用性。
```
public void printList(List<String> list) {
    for (String s : list) {
        System.out.println(s);
    }
}
```

2. Set 接口及其常用实现类

2.1 基本概念

Set 接口表示一个不包含重复元素的集合。Set 不保证元素的顺序，也不允许插入重复元素。

2.2 常用实现类

HashSet：基于哈希表实现，不保证元素的顺序，不允许重复元素。
LinkedHashSet：基于哈希表和链表实现，保持元素的插入顺序，不允许重复元素。
TreeSet：基于红黑树实现，保持元素的自然顺序或自定义排序，不允许重复元素。

2.3 底层原理

HashSet：
- 内部实现：HashSet 内部使用 HashMap 来存储元素，键为元素本身，值为一个常量对象。
- 哈希冲突：通过哈希函数计算元素的哈希值，如果发生哈希冲突，使用链地址法解决。
```
HashSet<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("C");

System.out.println(set); // [A, B, C]
```
LinkedHashSet：
- 内部实现：LinkedHashSet 内部使用 LinkedHashMap 来存储元素，保持元素的插入顺序。
- 链表：每个元素不仅有一个哈希桶，还有一个双向链表节点。
```
LinkedHashSet<String> set = new LinkedHashSet<>();
set.add("A");
set.add("B");
set.add("C");

System.out.println(set); // [A, B, C]
```
TreeSet：
- 内部实现：TreeSet 内部使用 TreeMap 来存储元素，保持元素的自然顺序或自定义排序。
- 红黑树：TreeSet 使用红黑树实现，保证元素的有序性。
```
TreeSet<String> set = new TreeSet<>();
set.add("C");
set.add("A");
set.add("B");

System.out.println(set); // [A, B, C]
```

2.4 常见操作

添加元素：

add(E e)：添加元素，如果元素已存在，则不添加。

HashSet<String> set = new HashSet<>();
set.add("A");
set.add("B");
set.add("A"); // 不会添加重复元素

System.out.println(set); // [A, B]

删除元素：

remove(Object o)：删除指定的元素。

HashSet<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));
set.remove("B");

System.out.println(set); // [A, C]

检查元素：

contains(Object o)：检查集合中是否包含指定的元素。

HashSet<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));
boolean contains = set.contains("B");

System.out.println(contains); // true

遍历元素：

使用 for-each 循环：
使用 Iterator：

HashSet<String> set = new HashSet<>(Arrays.asList("A", "B", "C"));

// 使用 for-each 循环
for (String s : set) {
    System.out.println(s);
}

// 使用 Iterator
Iterator<String> iterator = set.iterator();
while (iterator.hasNext()) {
    System.out.println(iterator.next());
}

2.5 最佳实践

选择合适的实现类：
- HashSet：适用于不需要保持元素顺序的场景。
- LinkedHashSet：适用于需要保持元素插入顺序的场景。
- TreeSet：适用于需要保持元素有序的场景。
使用 Set 接口：
- 代码复用：在方法签名中使用 Set 接口，而不是具体的实现类，提高代码的复用性。
```
public void printSet(Set<String> set) {
    for (String s : set) {
        System.out.println(s);
    }
}
```

重写 equals 和 hashCode 方法：

确保唯一性：如果自定义对象需要存储在 Set 中，必须重写 equals 和 hashCode 方法，确保对象的唯一性。

class Person {
    private String name;
    private int age;

    public Person(String name, int age) {
        this.name = name;
        this.age = age;
    }

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

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

3. Map 接口及其常用实现类

3.1 基本概念

Map 接口表示一个键值对的集合，每个键最多只能映射到一个值。Map 不保证键值对的顺序，除非使用特定的实现类。

3.2 常用实现类

HashMap：基于哈希表实现，不保证键值对的顺序，允许一个 null 键和多个 null 值。
LinkedHashMap：基于哈希表和链表实现，保持键值对的插入顺序，允许一个 null 键和多个 null 值。
TreeMap：基于红黑树实现，保持键值对的自然顺序或自定义排序，不允许 null 键。
Hashtable：类似于 HashMap，但线程安全，性能较差，不允许 null 键和 null 值。

3.3 底层原理

HashMap：
- 内部实现：HashMap 内部使用一个数组 Node<K,V>[] table 来存储键值对，每个节点包含一个键、一个值、一个哈希值和一个指向下一个节点的引用。
- 哈希冲突：通过哈希函数计算键的哈希值，如果发生哈希冲突，使用链地址法解决。
```
HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

System.out.println(map); // {A=1, B=2, C=3}
```
LinkedHashMap：
- 内部实现：LinkedHashMap 内部使用 HashMap 和双向链表来存储键值对，保持键值对的插入顺序。
- 链表：每个节点不仅有一个哈希桶，还有一个双向链表节点。
```
LinkedHashMap<String, Integer> map = new LinkedHashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("C", 3);

System.out.println(map); // {A=1, B=2, C=3}
```
TreeMap：
- 内部实现：TreeMap 内部使用 TreeMap 来存储键值对，保持键值对的自然顺序或自定义排序。
- 红黑树：TreeMap 使用红黑树实现，保证键值对的有序性。
```
TreeMap<String, Integer> map = new TreeMap<>();
map.put("C", 3);
map.put("A", 1);
map.put("B", 2);

System.out.println(map); // {A=1, B=2, C=3}
```

3.4 常见操作

添加键值对：

put(K key, V value)：添加键值对，如果键已存在，则更新对应的值。

HashMap<String, Integer> map = new HashMap<>();
map.put("A", 1);
map.put("B", 2);
map.put("A", 3); // 更新键 "A" 的值

System.out.println(map); // {A=3, B=2}

删除键值对：

remove(Object key)：删除指定键的键值对。

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

System.out.println(map); // {A=1, C=3}

获取值：

get(Object key)：获取指定键的值。

HashMap<String, Integer> map = new HashMap<>(Map.of("A", 1, "B", 2, "C", 3));
int value = map.get("B");

System.out.println(value); // 2

检查键或值：

containsKey(Object key)：检查集合中是否包含指定的键。
containsValue(Object value)：检查集合中是否包含指定的值。

HashMap<String, Integer> map = new HashMap<>(Map.of("A", 1, "B", 2, "C", 3));
boolean containsKey = map.containsKey("B");
boolean containsValue = map.containsValue(2);

System.out.println(containsKey); // true
System.out.println(containsValue); // true

遍历键值对：

使用 for-each 循环：
使用 Iterator：

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

// 使用 for-each 循环
for (Map.Entry<String, Integer> entry : map.entrySet()) {
    System.out.println(entry.getKey() + ": " + entry.getValue());
}

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

3.5 最佳实践

选择合适的实现类：
- HashMap：适用于不需要保持键值对顺序的场景。
- LinkedHashMap：适用于需要保持键值对插入顺序的场景。
- TreeMap：适用于需要保持键值对有序的场景。

使用 Map 接口：

代码复用：在方法签名中使用 Map 接口，而不是具体的实现类，提高代码的复用性。

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