集合框架

Java 集合框架是 Java 提供的一套用于存储和操作数据的工具类，位于 java.util 包中。它提供了各种类型的集合接口及其实现类，以及相关的工具类，可以方便地存储、检索、操作和管理对象。

集合框架概述

什么是集合？

集合是存储对象的容器，它与数组类似，但提供了更加丰富的操作功能。与数组相比，集合具有以下特点：

• 动态大小：集合的大小可以根据需要自动增长或缩小
• 只能存储对象：不能直接存储基本类型（但可以通过自动装箱/拆箱存储基本类型的包装类）
• 提供丰富的操作方法：如添加、删除、查找、排序等
• 可以存储不同类型的对象：如果不指定泛型约束

集合框架的结构

Java 集合框架主要包含以下几个部分：

1. 接口：定义集合的基本行为
2. 实现类：接口的具体实现
3. 算法：用于操作集合的静态方法
4. 工具类：提供集合操作的辅助方法

集合框架的主要接口

接口	描述	主要实现类
Collection	所有集合的根接口	List, Set, Queue 等子接口
List	有序集合，允许重复元素	ArrayList, LinkedList, Vector
Set	无序集合，不允许重复元素	HashSet, TreeSet, LinkedHashSet
Queue	队列接口，通常按照FIFO顺序处理元素	LinkedList, PriorityQueue
Deque	双端队列接口，允许在两端进行元素操作	LinkedList, ArrayDeque
Map	存储键值对的接口	HashMap, TreeMap, LinkedHashMap, Hashtable

Collection 接口

Collection 是集合框架中的根接口，它定义了所有集合的通用操作。List, Set, Queue 等接口都继承自 Collection。

Collection 接口的主要方法

// 添加元素
boolean add(E e); // 添加单个元素
boolean addAll(Collection<? extends E> c); // 添加集合中的所有元素

// 删除元素
boolean remove(Object o); // 删除单个元素
boolean removeAll(Collection<?> c); // 删除集合中的所有元素
boolean retainAll(Collection<?> c); // 保留与指定集合的交集
void clear(); // 清空集合

// 查询操作
int size(); // 获取集合大小
boolean isEmpty(); // 判断集合是否为空
boolean contains(Object o); // 判断是否包含指定元素
boolean containsAll(Collection<?> c); // 判断是否包含指定集合的所有元素

// 遍历操作
Iterator<E> iterator(); // 获取迭代器

// 转换为数组
Object[] toArray(); // 转换为Object数组
<T> T[] toArray(T[] a); // 转换为指定类型的数组

List 接口

List 是一个有序的集合，允许存储重复的元素。用户可以通过索引（元素在列表中的位置）访问和操作元素。

List 接口的特点

• 有序性：元素按照插入顺序存储
• 允许重复：可以存储相同的元素
• 可以通过索引访问：类似数组的访问方式

List 接口的主要实现类

ArrayList

ArrayList 是基于动态数组实现的 List 接口，提供了快速的随机访问能力。

特点：

• 底层使用数组实现
• 查询速度快（O(1)时间复杂度）
• 插入和删除操作较慢（特别是在中间位置）
• 线程不安全

使用示例：

import java.util.ArrayList;
import java.util.List;

public class ArrayListExample {
    public static void main(String[] args) {
        // 创建ArrayList
        List<String> fruits = new ArrayList<>();
        
        // 添加元素
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        
        // 在指定位置添加元素
        fruits.add(1, "Mango");
        
        // 通过索引访问元素
        System.out.println("第二个元素: " + fruits.get(1)); // 输出: Mango
        
        // 修改元素
        fruits.set(0, "Grapes");
        
        // 删除元素
        fruits.remove(2); // 删除索引为2的元素
        fruits.remove("Orange"); // 删除指定元素
        
        // 遍历元素
        System.out.println("遍历ArrayList:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
        
        // 获取大小
        System.out.println("ArrayList大小: " + fruits.size());
        
        // 判断是否包含元素
        System.out.println("是否包含Apple: " + fruits.contains("Apple"));
    }
}

LinkedList

LinkedList 是基于双向链表实现的 List 接口，同时也实现了 Deque 接口。

特点：

• 底层使用双向链表实现
• 插入和删除操作快（O(1)时间复杂度）
• 查询速度较慢（O(n)时间复杂度）
• 线程不安全

使用示例：

import java.util.LinkedList;
import java.util.List;

public class LinkedListExample {
    public static void main(String[] args) {
        // 创建LinkedList
        List<String> names = new LinkedList<>();
        
        // 添加元素
        names.add("Alice");
        names.add("Bob");
        names.add("Charlie");
        
        // 在指定位置添加元素
        names.add(1, "David");
        
        // 通过索引访问元素
        System.out.println("第三个元素: " + names.get(2)); // 输出: Bob
        
        // 修改元素
        names.set(0, "Eve");
        
        // 删除元素
        names.remove(2); // 删除索引为2的元素
        names.remove("Charlie"); // 删除指定元素
        
        // 遍历元素
        System.out.println("遍历LinkedList:");
        for (String name : names) {
            System.out.println(name);
        }
    }
}

Vector

Vector 是基于动态数组实现的 List 接口，与 ArrayList 类似，但它是线程安全的。

特点：

• 底层使用数组实现
• 线程安全（所有方法都有synchronized修饰）
• 性能较低
• 是遗留类，现代Java通常使用ArrayList并配合Collections.synchronizedList()实现线程安全

使用示例：

import java.util.Vector;

public class VectorExample {
    public static void main(String[] args) {
        // 创建Vector
        Vector<Integer> numbers = new Vector<>();
        
        // 添加元素
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        
        // 遍历元素
        System.out.println("遍历Vector:");
        for (Integer number : numbers) {
            System.out.println(number);
        }
    }
}

Set 接口

Set 是一个不包含重复元素的集合，它模拟了数学中的集合概念。

Set 接口的特点

• 无序性：元素没有特定的顺序（某些实现可能保持插入顺序或排序顺序）
• 不允许重复：不能存储相同的元素
• 最多包含一个null元素

Set 接口的主要实现类

HashSet

HashSet 是基于哈希表实现的 Set 接口，提供了最快的访问速度。

特点：

• 底层使用HashMap实现
• 无序集合（元素存储顺序不保证）
• 允许null元素
• 线程不安全
• 具有良好的存取和查找性能

使用示例：

import java.util.HashSet;
import java.util.Set;

public class HashSetExample {
    public static void main(String[] args) {
        // 创建HashSet
        Set<String> colors = new HashSet<>();
        
        // 添加元素
        colors.add("Red");
        colors.add("Green");
        colors.add("Blue");
        colors.add("Red"); // 重复元素，不会被添加
        
        // 遍历元素（顺序不固定）
        System.out.println("遍历HashSet:");
        for (String color : colors) {
            System.out.println(color);
        }
        
        // 判断元素是否存在
        System.out.println("是否包含Yellow: " + colors.contains("Yellow"));
        
        // 删除元素
        colors.remove("Green");
        
        // 清空集合
        // colors.clear();
    }
}

TreeSet

TreeSet 是基于红黑树实现的 Set 接口，它会按照元素的自然顺序或指定的比较器顺序进行排序。

特点：

• 底层使用TreeMap实现
• 有序集合（元素按排序顺序存储）
• 不允许null元素
• 线程不安全
• 插入、删除和查询操作的时间复杂度为O(log n)

使用示例：

import java.util.TreeSet;
import java.util.Set;

public class TreeSetExample {
    public static void main(String[] args) {
        // 创建TreeSet（按自然顺序排序）
        Set<Integer> numbers = new TreeSet<>();
        
        // 添加元素
        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);
        numbers.add(10);
        
        // 遍历元素（按升序排列）
        System.out.println("遍历TreeSet:");
        for (Integer number : numbers) {
            System.out.println(number);
        }
        
        // 创建TreeSet（使用字符串，按字典顺序排序）
        Set<String> names = new TreeSet<>();
        names.add("Charlie");
        names.add("Alice");
        names.add("Bob");
        
        System.out.println("按字典顺序排序的TreeSet:");
        for (String name : names) {
            System.out.println(name);
        }
    }
}

LinkedHashSet

LinkedHashSet 继承自 HashSet，它使用链表来维护元素的插入顺序。

特点：

• 底层使用LinkedHashMap实现
• 保持元素的插入顺序
• 允许null元素
• 线程不安全
• 性能略低于HashSet，但可以维护元素顺序

使用示例：

import java.util.LinkedHashSet;
import java.util.Set;

public class LinkedHashSetExample {
    public static void main(String[] args) {
        // 创建LinkedHashSet
        Set<String> fruits = new LinkedHashSet<>();
        
        // 添加元素
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Orange");
        fruits.add("Apple"); // 重复元素，不会被添加
        
        // 遍历元素（按插入顺序）
        System.out.println("遍历LinkedHashSet:");
        for (String fruit : fruits) {
            System.out.println(fruit);
        }
    }
}

Queue 接口

Queue 是一种用于存储按照特定顺序处理的元素的集合，通常按照先进先出（FIFO）的顺序处理元素。

Queue 接口的特点

• 通常按照FIFO顺序处理元素（但PriorityQueue例外）
• 提供了在队列头部和尾部添加、删除和检查元素的方法

Queue 接口的主要方法

// 添加元素
boolean add(E e); // 添加元素，如果队列已满则抛出异常
boolean offer(E e); // 添加元素，如果队列已满则返回false

// 删除并返回队列头部元素
E remove(); // 删除并返回头部元素，如果队列为空则抛出异常
E poll(); // 删除并返回头部元素，如果队列为空则返回null

// 返回但不删除队列头部元素
E element(); // 返回头部元素，如果队列为空则抛出异常
E peek(); // 返回头部元素，如果队列为空则返回null

Queue 接口的主要实现类

LinkedList

LinkedList 同时实现了 List 和 Queue 接口，可以作为队列使用。

使用示例：

import java.util.LinkedList;
import java.util.Queue;

public class QueueExample {
    public static void main(String[] args) {
        // 创建队列
        Queue<String> queue = new LinkedList<>();
        
        // 添加元素
        queue.add("First");
        queue.offer("Second");
        queue.offer("Third");
        
        // 查看队列头部元素
        System.out.println("队列头部元素: " + queue.peek()); // 输出: First
        
        // 移除并返回队列头部元素
        System.out.println("移除的元素: " + queue.poll()); // 输出: First
        
        // 遍历队列
        System.out.println("遍历队列:");
        while (!queue.isEmpty()) {
            System.out.println(queue.poll());
        }
    }
}

PriorityQueue

PriorityQueue 是一个基于优先级堆的队列，元素按照其自然顺序或指定的比较器顺序进行排序，具有最高优先级的元素位于队列头部。

特点：

• 不保证FIFO顺序，而是按照元素的优先级排序
• 允许null元素
• 线程不安全
• 插入和删除操作的时间复杂度为O(log n)

使用示例：

import java.util.PriorityQueue;
import java.util.Queue;

public class PriorityQueueExample {
    public static void main(String[] args) {
        // 创建优先级队列（按自然顺序排序）
        Queue<Integer> pq = new PriorityQueue<>();
        
        // 添加元素
        pq.offer(5);
        pq.offer(1);
        pq.offer(9);
        pq.offer(3);
        pq.offer(7);
        
        // 遍历优先级队列（会按优先级顺序出队）
        System.out.println("按优先级顺序出队:");
        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // 输出: 1, 3, 5, 7, 9
        }
    }
}

Map 接口

Map 接口用于存储键值对（key-value pairs），它提供了根据键快速查找值的功能。

Map 接口的特点

• 存储键值对
• 键不能重复，每个键最多映射到一个值
• 值可以重复
• 提供了根据键查找、插入和删除值的方法

Map 接口的主要方法

// 添加或更新键值对
V put(K key, V value); // 添加或更新键值对，返回旧值（如果键已存在）
void putAll(Map<? extends K, ? extends V> m); // 添加指定映射中的所有键值对

// 删除键值对
V remove(Object key); // 删除指定键的键值对，返回对应的值
boolean remove(Object key, Object value); // 只有当键映射到指定值时才删除

// 查询操作
int size(); // 获取键值对数量
boolean isEmpty(); // 判断是否为空
boolean containsKey(Object key); // 判断是否包含指定键
boolean containsValue(Object value); // 判断是否包含指定值
V get(Object key); // 获取指定键对应的值

// 获取集合视图
Set<K> keySet(); // 获取所有键的集合
Collection<V> values(); // 获取所有值的集合
Set<Map.Entry<K, V>> entrySet(); // 获取所有键值对的集合

// 清空映射
void clear(); // 清空所有键值对

Map 接口的主要实现类

HashMap

HashMap 是基于哈希表实现的 Map 接口，提供了最快的访问速度。

特点：

• 底层使用数组和链表/红黑树实现（Java 8+）
• 无序集合（键值对存储顺序不保证）
• 允许null键和null值
• 线程不安全
• 具有良好的存取和查找性能

使用示例：

import java.util.HashMap;
import java.util.Map;

public class HashMapExample {
    public static void main(String[] args) {
        // 创建HashMap
        Map<String, Integer> studentScores = new HashMap<>();
        
        // 添加键值对
        studentScores.put("Alice", 95);
        studentScores.put("Bob", 87);
        studentScores.put("Charlie", 92);
        studentScores.put("David", 88);
        
        // 获取值
        System.out.println("Bob的分数: " + studentScores.get("Bob"));
        
        // 更新值
        studentScores.put("Bob", 90);
        System.out.println("更新后Bob的分数: " + studentScores.get("Bob"));
        
        // 检查键是否存在
        System.out.println("是否有Alice: " + studentScores.containsKey("Alice"));
        System.out.println("是否有分数为95: " + studentScores.containsValue(95));
        
        // 遍历HashMap（方式1：遍历键集）
        System.out.println("方式1 - 遍历键集:");
        for (String name : studentScores.keySet()) {
            System.out.println(name + ": " + studentScores.get(name));
        }
        
        // 遍历HashMap（方式2：遍历键值对）
        System.out.println("方式2 - 遍历键值对:");
        for (Map.Entry<String, Integer> entry : studentScores.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
        
        // 删除键值对
        studentScores.remove("Charlie");
        
        // 获取大小
        System.out.println("学生数量: " + studentScores.size());
    }
}

TreeMap

TreeMap 是基于红黑树实现的 Map 接口，它会按照键的自然顺序或指定的比较器顺序进行排序。

特点：

• 底层使用红黑树实现
• 有序集合（键值对按键排序）
• 不允许null键，但允许null值
• 线程不安全
• 插入、删除和查询操作的时间复杂度为O(log n)

使用示例：

import java.util.TreeMap;
import java.util.Map;

public class TreeMapExample {
    public static void main(String[] args) {
        // 创建TreeMap（按键的自然顺序排序）
        Map<String, Integer> sortedMap = new TreeMap<>();
        
        // 添加键值对
        sortedMap.put("Charlie", 92);
        sortedMap.put("Alice", 95);
        sortedMap.put("Bob", 90);
        
        // 遍历TreeMap（按键的升序排列）
        System.out.println("按键排序的TreeMap:");
        for (Map.Entry<String, Integer> entry : sortedMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

LinkedHashMap

LinkedHashMap 继承自 HashMap，它使用链表来维护键值对的插入顺序。

特点：

• 底层使用哈希表和链表实现
• 保持键值对的插入顺序
• 允许null键和null值
• 线程不安全
• 性能略低于HashMap，但可以维护元素顺序

使用示例：

import java.util.LinkedHashMap;
import java.util.Map;

public class LinkedHashMapExample {
    public static void main(String[] args) {
        // 创建LinkedHashMap
        Map<String, Integer> linkedMap = new LinkedHashMap<>();
        
        // 添加键值对
        linkedMap.put("Charlie", 92);
        linkedMap.put("Alice", 95);
        linkedMap.put("Bob", 90);
        
        // 遍历LinkedHashMap（按插入顺序）
        System.out.println("按插入顺序的LinkedHashMap:");
        for (Map.Entry<String, Integer> entry : linkedMap.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

Hashtable

Hashtable 是一个遗留类，与 HashMap 类似，但它是线程安全的。

特点：

• 底层使用哈希表实现
• 线程安全（所有方法都有synchronized修饰）
• 不允许null键和null值
• 是遗留类，现代Java通常使用HashMap并配合ConcurrentHashMap或synchronizedMap实现线程安全

使用示例：

import java.util.Hashtable;
import java.util.Map;

public class HashtableExample {
    public static void main(String[] args) {
        // 创建Hashtable
        Map<String, Integer> table = new Hashtable<>();
        
        // 添加键值对
        table.put("One", 1);
        table.put("Two", 2);
        table.put("Three", 3);
        
        // 遍历Hashtable
        System.out.println("遍历Hashtable:");
        for (Map.Entry<String, Integer> entry : table.entrySet()) {
            System.out.println(entry.getKey() + ": " + entry.getValue());
        }
    }
}

Collections 工具类

java.util.Collections 类提供了一系列静态方法，用于操作集合或返回一个新的集合。

Collections 常用方法

排序操作

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(5);
        numbers.add(2);
        numbers.add(8);
        numbers.add(1);
        
        // 排序（升序）
        Collections.sort(numbers);
        System.out.println("排序后: " + numbers); // 输出: [1, 2, 5, 8]
        
        // 排序（降序）
        Collections.reverse(numbers);
        System.out.println("降序: " + numbers); // 输出: [8, 5, 2, 1]
        
        // 随机打乱顺序
        Collections.shuffle(numbers);
        System.out.println("随机打乱: " + numbers);
    }
}

查找操作

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class CollectionsSearchExample {
    public static void main(String[] args) {
        List<Integer> numbers = new ArrayList<>();
        numbers.add(1);
        numbers.add(3);
        numbers.add(5);
        numbers.add(7);
        numbers.add(9);
        
        // 二分查找（必须先排序）
        int index = Collections.binarySearch(numbers, 5);
        System.out.println("元素5的索引: " + index); // 输出: 2
        
        // 最大值
        System.out.println("最大值: " + Collections.max(numbers));
        
        // 最小值
        System.out.println("最小值: " + Collections.min(numbers));
    }
}

线程安全操作

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Set;
import java.util.HashMap;
import java.util.HashSet;

public class CollectionsSynchronizedExample {
    public static void main(String[] args) {
        // 创建线程安全的List
        List<String> syncList = Collections.synchronizedList(new ArrayList<>());
        
        // 创建线程安全的Set
        Set<String> syncSet = Collections.synchronizedSet(new HashSet<>());
        
        // 创建线程安全的Map
        Map<String, Integer> syncMap = Collections.synchronizedMap(new HashMap<>());
    }
}

不可变集合

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class CollectionsUnmodifiableExample {
    public static void main(String[] args) {
        List<String> list = new ArrayList<>();
        list.add("A");
        list.add("B");
        
        // 创建不可变List
        List<String> unmodifiableList = Collections.unmodifiableList(list);
        
        // 创建不可变Set
        Set<String> unmodifiableSet = Collections.unmodifiableSet(new HashSet<>(list));
        
        // 创建不可变Map
        Map<String, Integer> map = new HashMap<>();
        map.put("A", 1);
        Map<String, Integer> unmodifiableMap = Collections.unmodifiableMap(map);
        
        // 尝试修改会抛出UnsupportedOperationException
        // unmodifiableList.add("C"); // 抛出异常
    }
}

集合框架的选择

List、Set、Map 的选择

• List：当需要存储有序、可重复的元素，并且需要通过索引访问元素时使用
• Set：当需要存储无序、不可重复的元素时使用
• Map：当需要存储键值对，并且需要通过键快速查找值时使用

具体实现类的选择

List 实现类的选择

• ArrayList：适用于频繁的随机访问操作，对插入和删除操作要求不高的场景
• LinkedList：适用于频繁的插入和删除操作，对随机访问要求不高的场景，或者需要作为队列使用的场景
• Vector：已经过时，不推荐使用，除非需要线程安全的集合（可以使用Collections.synchronizedList()代替）

Set 实现类的选择

• HashSet：适用于大多数需要Set的场景，提供最快的访问速度
• LinkedHashSet：当需要保持元素的插入顺序时使用
• TreeSet：当需要对元素进行排序时使用

Map 实现类的选择

• HashMap：适用于大多数需要Map的场景，提供最快的访问速度
• LinkedHashMap：当需要保持键值对的插入顺序时使用
• TreeMap：当需要按键排序时使用
• Hashtable：已经过时，不推荐使用，除非需要线程安全的集合（可以使用ConcurrentHashMap代替）

集合框架的性能考量

1. ArrayList vs LinkedList

   • ArrayList：随机访问快（O(1)），插入删除慢（特别是中间位置，O(n)）
   • LinkedList：随机访问慢（O(n)），插入删除快（O(1)，只需修改指针）

2. HashSet vs TreeSet vs LinkedHashSet

   • HashSet：添加、删除、查询操作最快（平均O(1)）
   • TreeSet：添加、删除、查询操作时间复杂度为O(log n)，但可以保持排序
   • LinkedHashSet：性能略低于HashSet，但可以保持插入顺序

3. HashMap vs TreeMap vs LinkedHashMap

   • HashMap：添加、删除、查询操作最快（平均O(1)）
   • TreeMap：添加、删除、查询操作时间复杂度为O(log n)，但可以保持按键排序
   • LinkedHashMap：性能略低于HashMap，但可以保持插入顺序

4. 线程安全问题

   • 大多数集合类不是线程安全的，在多线程环境中需要额外的同步措施
   • 可以使用Collections.synchronizedXXX()方法或并发集合类（如ConcurrentHashMap）

小结

• Java 集合框架提供了丰富的数据结构，包括List、Set、Queue、Map等
• 集合框架分为接口、实现类和工具类
• List接口的主要实现类有ArrayList、LinkedList、Vector
• Set接口的主要实现类有HashSet、TreeSet、LinkedHashSet
• Map接口的主要实现类有HashMap、TreeMap、LinkedHashMap、Hashtable
• Collections工具类提供了丰富的静态方法来操作集合
• 选择合适的集合类可以提高程序的性能和可维护性

掌握Java集合框架是Java编程的重要基础，合理地使用集合可以使代码更加简洁、高效。