Skip to content

集合框架 ​

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 接口的主要方法 ​

java
// 添加元素
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)时间复杂度)
  • 插入和删除操作较慢(特别是在中间位置)
  • 线程不安全

使用示例:

java
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)时间复杂度)
  • 线程不安全

使用示例:

java
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()实现线程安全

使用示例:

java
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元素
  • 线程不安全
  • 具有良好的存取和查找性能

使用示例:

java
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)

使用示例:

java
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,但可以维护元素顺序

使用示例:

java
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 接口的主要方法 ​

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

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

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

Queue 接口的主要实现类 ​

LinkedList ​

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

使用示例:

java
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)

使用示例:

java
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 接口的主要方法 ​

java
// 添加或更新键值对
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值
  • 线程不安全
  • 具有良好的存取和查找性能

使用示例:

java
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)

使用示例:

java
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,但可以维护元素顺序

使用示例:

java
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实现线程安全

使用示例:

java
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 常用方法 ​

排序操作 ​

java
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);
    }
}

查找操作 ​

java
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));
    }
}

线程安全操作 ​

java
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<>());
    }
}

不可变集合 ​

java
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编程的重要基础,合理地使用集合可以使代码更加简洁、高效。