Java 集合框架 | 菜鸟教程
Java 集合框架图

Java 集合类由两个根接口 Collection 、Map 派生而来

Collection 接口又有三个子接口 List、Set、Queue

从功能角度，Java 集合可以大体上分为 List、Set、Queue、Map

• List：有序可重复集合
• Set：无序不可重复集合
• Queue：队列集合
• Map：Key-Value 字典集合

List 可以分为：
1）ArrayList
优点: 底层数据结构是数组，查询快，增删慢。
缺点: 线程不安全，效率高

2）Vector
优点: 底层数据结构是数组，查询快，增删慢。
缺点: 线程安全，效率低

3）LinkedList
优点: 底层数据结构是链表，查询慢，增删快。
缺点: 线程不安全，效率高

Set 可以分为：

• HashSet：底层数据结构采用哈希表实现，元素无序且唯一，线程不安全，效率高，可以存储 null 元素，元素的唯一性是靠所存储元素类型是否重写 hashCode()和 equals()方法来保证的，如果没有重写这两个方法，则无法保证元素的唯一性。
• LinkedHashSet：底层数据结构采用链表和哈希表共同实现，链表保证了元素的顺序与存储顺序一致，哈希表保证了元素的唯一性。
• TreeSet：底层数据结构采用二叉树来实现，元素唯一且已经排好序,唯一性同样需要重写 hashCode 和 equals()方法，二叉树结构保证了元素的有序性。

Queue 可以分为：

• ArrayDeque：是双端队列,当程序中需要使用“栈”这种数据结构时，推荐使用
• PriorityQueue：基于堆，默认小根堆，保存队列元素的顺序并不是按照加入的顺序，而是按照队列元素的大小进行排序的，且不允许插入 NULL

Map 可以分为：

• HashMap：哈希表
• LinkedHashMap：继承了 HashMap，是 Map 接口的哈希表和链接列表实现，它维护着一个双重链接列表，此链接列表定义了迭代顺序，该迭代顺序可以是插入顺序或者是访问顺序。
• TreeMap：实现 SortMap 接口，能够把它保存的记录根据键排序，默认是按键值的升序排序（自然顺序），也可以指定排序的比较器，当用 Iterator 遍历 TreeMap 时，得到的记录是排过序的。基于红黑树

一、算法题常用容器

1. HashSet

基于哈希表的集合，无重复元素、无序（不保证元素存储顺序，与插入顺序无关）
HashSet 底层其实是通过 HashMap 实现的（元素存储在 HashMap 的 key 位置，value 为一个固定的空对象），因此两者的哈希表特性完全一致。

常用构造方法：

// 1. 空构造器（初始容量 16，加载因子 0.75）
HashSet<Integer> set = new HashSet<>();

// 2. 指定初始容量
HashSet<String> set = new HashSet<>(32);

// 3. 用其他集合初始化（将集合中元素去重后存入）
List<Integer> list = Arrays.asList(1,2,2,3);
HashSet<Integer> set = new HashSet<>(list); // 结果：{1,2,3}

常用方法

HashSet<String> set = new HashSet<>();

// 添加元素
set.add("apple");
set.add("banana");
set.add("apple"); // 重复元素，添加失败
System.out.println(set); // 输出：[banana,apple]（顺序不确定）

// 判断存在性
boolean hasBanana = set.contains("banana"); // true

// 删除元素
boolean removed = set.remove("apple"); // true

// 大小与清空
System.out.println(set.size()); // 1
set.clear();
System.out.println(set.isEmpty()); // true

循环遍历：

1. 增强型 for 循环

HashSet<Integer> set = new HashSet<>(Arrays.asList(1,2,3));
for(int num: set) {
    System.out.print(num + " "); // 输出：1 2 3（顺序可能不同）
}

2. 迭代器
   适合需要在循环中遍历删除元素的场景

HashSet<String> set = new HashSet<>(Arrays.asList("a", "b", "c"));
Iterator<String> iterator = set.iterator();
while(iterator.hasNext()) {
    String s = iterator.next();
    if(s.equals("b")) {
        iterator.remove(); // 安全删除元素
    }
    System.out.print(s + " ");
}
System.out.println("\n" + set); // 输出：a c  /  [a,c]

常用场景：

1. 去重操作

int[] nums = {1,2,2,3,4,4};
HashSet<Integer> set = new HashSet<>();
for(int num: nums) {
    set.add(num);
}
// 结果：set = {1,2,3,4}

2. 判断元素是否存在
   例如：两数之和问题中，判断目标值与当前元素的差值是否已出现。

int[] nums = {2,7,11,15};
int target = 9;
HashSet<Integer> set = new HashSet<>();
for(int num: nums) {
    int complement = target - num;
    if(set.contains(complement)) {
        return new int[]{complement,num}; // 找到结果
    }
    set.add(num);
}

3. 判断唯一性
   如：判断某一字符串中，是否所有字符均唯一

public boolean isUnique(String s) {
    HashSet<Character> set = new HashSet<>();
    for(char c: s.toCharArray()) {
        if(set.contains(c)) {
            return false; // 有重复字符
        }
        set.add(c);
    }
    return true;
}

注意事项：

若存储自定义元素，必须重写  hashCode() 和  equals()，否则无法正确判断重复（HashSet 先通过  hashCode() 定位哈希桶，再通过  equals() 比较内容）。

2. HashMap

哈希表

常用构造方法

// 1. 空构造器（初始容量 16，加载因子 0.75）
HashMap<String,Integer> map = new HashMap<>();

// 2. 指定初始容量
HashMap<Integer,String> map = new HashMap<>(32);

// 3. 用其他 Map 初始化
Map<String,Integer> otherMap = new HashMap<>();
otherMap.put("a",1);
HashMap<String,Integer> map = new HashMap<>(otherMap); // 复制其他 Map 的键值对

常用方法：

HashMap<String,Integer> map = new HashMap<>();

// 插入键值对
map.put("apple",5);
map.put("banana",3);
map.put("apple",10); // 覆盖原有 value，返回 5

// 获取 value
int appleCount = map.get("apple"); // 10
int orangeCount = map.getOrDefault("orange",0); // 键不存在时返回默认值 0

// 判断存在性
boolean hasBanana = map.containsKey("banana"); // true
boolean hasValue3 = map.containsValue(3); // true

// 删除元素
int removedValue = map.remove("banana"); // 3

// 大小与清空
System.out.println(map.size()); // 1（仅剩"apple"）
map.clear();
System.out.println(map.isEmpty()); // true

循环遍历

1. 通过集合来遍历所有 key，通过 key 获取 value

HashMap<String,Integer> map = new HashMap<>();
map.put("a",1);
map.put("b",2);

// 获取 key 集合
Set<String> keys = map.keySet();
for(String key: keys) {
    Integer value = map.get(key);
    System.out.println(key + ": " + value);
}

2. 同时遍历 key、value 键值对（效率最高，推荐）

Set<Map.Entry<String,Integer>> entries = map.entrySet();
for(Map.Entry<String,Integer> entry: entries) {
    String key = entry.getKey();
    Integer value = entry.getValue();
    System.out.println(key + ": " + value);
}

3. 迭代器遍历
   一般用于遍历时需要删除元素的场景

常用场景

1. 计数统计
   例如：统计字符串中每个字符的出现次数。

String s = "abacbc";
HashMap<Character,Integer> countMap = new HashMap<>();
for(char c: s.toCharArray()) {
    // 若 key 存在则+1，否则设为 1
    countMap.put(c,countMap.getOrDefault(c,0) + 1);
}
// 结果：{a:2,b:2,c:2}

2. 映射关系存储
   例如：两数之和问题中，存储 “值→索引” 的映射，快速查找补数。

int[] nums = {2,7,11,15};
int target = 9;
HashMap<Integer,Integer> map = new HashMap<>();
for(int i = 0;i < nums.length;i++) {
    int complement = target - nums[i];
    if(map.containsKey(complement)) {
        return new int[]{map.get(complement),i}; // 找到两个数的索引
    }
    map.put(nums[i],i); // 存储“值→索引”
}

3. 缓存中间结果
   例如：斐波那契数列的记忆化递归（避免重复计算）。

HashMap<Integer,Integer> cache = new HashMap<>();
public int fib(int n) {
    if(n <= 1)return n;
    if(cache.containsKey(n)) {
        return cache.get(n); // 直接返回缓存结果
    }
    int result = fib(n-1) + fib(n-2);
    cache.put(n,result); // 缓存中间结果
    return result;
}

4. 快速查找替换
   例如：根据映射关系替换字符串中的字符（如密码替换）。

String pattern = "abba";
String s = "dog cat cat dog";
String[] words = s.split(" ");
HashMap<Character,String> map = new HashMap<>();
for(int i = 0;i < pattern.length();i++) {
    char c = pattern.charAt(i);
    String word = words[i];
    if(map.containsKey(c)) {
        if(!map.get(c).equals(word))return false; // 映射不一致
    } else {
        if(map.containsValue(word))return false; // 不同 key 映射同一 value
        map.put(c,word);
    }
}

注意事项

与 HashSet 类似，若 key 是自定义对象，必须重写 hashCode() 和  equals()，否则无法正确定位和比较键（哈希表通过  hashCode() 定位桶位置， equals() 比较内容）。

3. ArrayList

ArrayList 是 Java 集合框架中最常用的 List 接口实现类，基于动态数组实现，支持随机访问和动态扩容，是算法题中处理动态序列、模拟数组操作的核心工具。其查询效率高（时间复杂度 O(1)），尾部插入 / 删除效率高，但中间插入 / 删除效率较低（需移动元素，O(n)）。
初始容量为 10（默认），当元素满时自动扩容为原容量的 1.5 倍（通过复制数组实现）。

常用构造方法

// 1. 空构造器（初始容量 10，添加元素时自动扩容）
ArrayList<Integer> list = new ArrayList<>();

// 2. 指定初始容量（避免频繁扩容，适合已知大致数据量的场景）
ArrayList<String> list = new ArrayList<>(100);

// 3. 用其他集合初始化（将集合元素按顺序存入）
List<Integer> otherList = Arrays.asList(1,2,3);
ArrayList<Integer> list = new ArrayList<>(otherList); // 结果：[1,2,3]

常用方法

ArrayList<String> list = new ArrayList<>();

// 添加元素
list.add("Java");
list.add("Python");
list.add(1, "C++"); // 在索引 1 处插入，结果：[Java,C++,Python]

// 获取与修改
String first = list.get(0); // "Java"
String old = list.set(2, "JavaScript"); // 替换索引 2 的元素，返回"Python"

// 查找与删除
int index = list.indexOf("C++"); // 1
boolean removed = list.remove("Java"); // true，结果：[C++,JavaScript]
String removedElem = list.remove(0); // 删除索引 0 的元素，返回"C++"

// 大小与清空
System.out.println(list.size()); // 1（仅剩"JavaScript"）
list.clear();
System.out.println(list.isEmpty()); // true

循环遍历

1. 普通 for 循环（通过索引，支持修改元素）

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(10,20,30));
for(int i = 0;i < list.size();i++) {
    System.out.print(list.get(i) + " "); // 10 20 30
    list.set(i,list.get(i) + 5); // 修改元素（15,25,35）
}

2. 增强 for 循环（foreach，简洁，只读）

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(15,25,35));
for(int num: list) {
    System.out.print(num + " "); // 15 25 35（修改后的值）
}

3. 迭代器
   适合需在遍历中删除元素时使用

ArrayList<Integer> list = new ArrayList<>(Arrays.asList(15,25,35));
Iterator<Integer> iterator = list.iterator();
while(iterator.hasNext()) {
    int num = iterator.next();
    if(num > 20) {
        iterator.remove(); // 安全删除元素（仅 25、35 会被删除）
    }
}
System.out.println(list); // [15]

4. LinkedList

LinkedList 是 Java 集合框架中基于双向链表实现的集合类，同时实现了 List 和 Deque 接口，因此既既可以作为列表（List）使用，也可以作为双端队列（Deque）或栈（Stack）使用。其特点是增删操作（尤其是中间位置）效率高，但随机访问效率低（需从头/尾遍历）。

常用构造方法

// 1. 空构造器（创建空链表）
LinkedList<Integer> list = new LinkedList<>();

// 2. 用其他集合初始化（按集合迭代顺序添加元素）
List<String> otherList = Arrays.asList("a", "b", "c");
LinkedList<String> list = new LinkedList<>(otherList); // 结果：[a,b,c]

常用方法

作为 List 的核心方法（索引相关）

作为双端队列（Deque）的核心方法（首尾操作）

作为单端队列常用方法：

通用方法

循环遍历

LinkedList 不支持高效的随机访问，遍历方式需根据场景选择：

1. 增强 for 循环（推荐，简洁）
   适用于仅遍历元素，无需索引的场景：

LinkedList<String> list = new LinkedList<>(Arrays.asList("a", "b", "c"));
for(String s: list) {
    System.out.print(s + " "); // a b c
}

2. 迭代器（Iterator）
   支持在遍历中安全删除元素（避免 ConcurrentModificationException）：

Iterator<String> iterator = list.iterator();
while(iterator.hasNext()) {
    String s = iterator.next();
    if(s.equals("b")) {
        iterator.remove(); // 安全删除
    }
}
System.out.println(list); // [a,c]

3. 列表迭代器（ListIterator，支持双向遍历）
   可向前/向后遍历，还能在遍历中添加/替换元素：

ListIterator<String> listIt = list.listIterator();
// 向后遍历
while(listIt.hasNext()) {
    System.out.print(listIt.next() + " "); // a c
}
// 向前遍历
while(listIt.hasPrevious()) {
    System.out.print(listIt.previous() + " "); // c a
}

4. 普通 for 循环（不推荐，效率低）
   通过 get(index) 遍历，每次调用需从头/尾重新查找，时间复杂度 O(n²)：

for(int i = 0;i < list.size();i++) {
    System.out.print(list.get(i) + " "); // 效率低，不建议
}

常用场景

1. 需要频繁在中间/首尾插入删除的场景
   例如：实现链表数据结构、日志链表（频繁在头部添加新日志）、实现 undo/redo 操作（在链表中间插入历史记录）。

2. 作为双端队列（FIFO）使用
   例如：广度优先搜索（BFS）的队列实现（但性能略逊于 ArrayDeque）、任务调度队列（需在头部/尾部添加任务）。

3. 作为栈（LIFO）使用
   例如：用 addFirst() 和 removeFirst() 模拟栈的 push/pop 操作（替代 Stack 类，Stack 是遗留类，性能差）。

4. 实现队列的特殊操作
   例如：需要查看/删除队尾元素的场景（ArrayDeque 也支持，但 LinkedList 兼容性更好）。

注意事项

1. 随机访问效率低
   get(index)、 add(index,e) 等操作需遍历到指定索引，时间复杂度 O(n)，因此不适合需要频繁按索引访问的场景（此类场景优先用 ArrayList）。

2. 允许 null 元素
   LinkedList 可以添加 null 元素（如 list.add(null)），但可能导致后续 contains(null) 或遍历判断时的混淆，需谨慎使用。

3. 与 ArrayDeque 的选择
   若作为队列/栈使用，优先选 ArrayDeque（基于数组，性能更优）；仅当需要链表特有的中间插入/删除或兼容旧代码时，才用 LinkedList。

4. 线程不安全
   多线程环境下并发修改会导致 ConcurrentModificationException，需手动同步（如 Collections.synchronizedList()）或使用线程安全类（如 ConcurrentLinkedDeque）。

5. 内存开销较大
   每个元素需额外存储前驱/后继节点的引用，内存占用比 ArrayList 高（ArrayList 仅需存储元素本身）。

总结

LinkedList 是基于双向链表的多功能集合，核心优势是首尾操作 O(1) 效率和中间插入删除灵活，但随机访问性能差。适合场景包括：频繁在中间增删的列表、双端队列、栈等。使用时需避开随机访问操作，优先用迭代器或增强 for 循环遍历，且在队列/栈场景下，ArrayDeque 通常是更优选择。

二、接口定义的方法

Java 集合框架中的 List、Deque 等接口定义了一系列规范方法，不同实现类（如 ArrayList、LinkedList、ArrayDeque）需遵循这些方法的语义。以下是核心接口的方法分类及说明：

1. Collection 接口（所有集合的根接口）

List、Set、Queue 等均继承自 Collection，定义了集合的通用操作：

2. List 接口（有序可重复集合）

继承 Collection，新增索引相关操作，支持按位置访问元素：

3. Queue 接口（队列，FIFO 特性）

继承 Collection，定义先进先出（FIFO） 操作，用于实现队列：

4. Deque` 接口（双端队列，支持首尾操作）

继承 Queue，扩展为双端操作，既可以作为队列（FIFO），也可以作为栈（LIFO）：

5. 接口方法的设计特点

1. 规范性：接口仅定义方法签名和语义，具体实现由子类完成（如 ArrayList 和 LinkedList 都实现 List，但 get(index) 效率不同）。
2. 容错性：Queue/Deque 提供「安全方法」（如 offer/poll/peek，返回 boolean 或 null）和「不安全方法」（如 add/remove/element，抛异常），供不同场景选择。
3. 多功能性：Deque 同时覆盖队列、栈、双端操作，实现类（如 LinkedList、ArrayDeque）可灵活适配多种场景。

总结

• Collection：定义集合通用操作（增删查、遍历等）。
• List：新增索引操作，适合有序可重复的序列（如动态数组）。
• Queue：定义 FIFO 队列操作（入队、出队、查看队头）。
• Deque：扩展为双端操作，支持首尾双向增删，兼容队列和栈的需求。

理解这些接口的方法规范，能更好地选择合适的实现类（如 ArrayList 适合 List 随机访问，ArrayDeque 适合 Deque 高效操作）。

三、核心算法工具类

1. Collections(针对集合)

Collections 是专门为 Collection 接口的实现类（如 List、Set）提供算法的工具类，所有方法均为静态方法（直接通过类名调用）。

专门针对集合

1.1 排序算法

• sort(List<T> list)：对 List 集合进行自然排序（要求元素实现 Comparable 接口，如 Integer、String 等）。
• sort(List<T> list,Comparator<?super T> c)：按自定义 Comparator 规则排序（灵活支持任意排序逻辑，无需元素实现 Comparable）。

示例：

import java.util.*;

public class CollectionsDemo {
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(3,1,4,1,5));
        
        // 1. 自然排序（升序，依赖 Integer 实现的 Comparable）
        Collections.sort(list);
        System.out.println("自然排序后：" + list); // [1,1,3,4,5]
        
        // 2. 自定义 Comparator（降序）
        Collections.sort(list, (a,b) -> b - a);
        System.out.println("自定义降序后：" + list); // [5,4,3,1,1]
        
        // 3. 对自定义对象排序（如 Person，按年龄排序）
        List<Person> personList = new ArrayList<>();
        personList.add(new Person("Alice",25));
        personList.add(new Person("Bob",20));
        Collections.sort(personList, (p1,p2) -> p1.getAge() - p2.getAge());
        System.out.println("按年龄升序：" + personList); // [Bob(20),Alice(25)]
    }
    
    static class Person {
        private String name;
        private int age;
        // 构造器、getter、toString 省略
    }
}

1.2 查找算法

• binarySearch(List<?extends Comparable<?super T>> list,T key)：对已排序的 List 进行二分查找（未排序会返回错误结果），找到返回索引，否则返回 -(插入点) - 1 。
• binarySearch(List<?extends T> list,T key,Comparator<?super T> c)：结合自定义 Comparator 的二分查找（需确保 List 已按该 Comparator 排序）。
• max(Collection<?extends T> coll) /  min(Collection<?extends T> coll)：查找集合中的最大 / 最小值（依赖元素的 Comparable）。

List<Integer> sortedList = new ArrayList<>(Arrays.asList(1,3,5,7,9));
int index = Collections.binarySearch(sortedList,5);
System.out.println("5 的索引：" + index); // 2（正确）

int wrongIndex = Collections.binarySearch(sortedList,4);
System.out.println("4 的插入点：" + (-(wrongIndex) - 1)); // 2（4 应插入到索引 2 的位置）

int max = Collections.max(sortedList);
System.out.println("最大值：" + max); // 9

1.3 其他常用算法

List<Integer> list = new ArrayList<>(Arrays.asList(1,2,3));
Collections.reverse(list);
System.out.println("反转后：" + list); // [3,2,1]

Collections.shuffle(list);
System.out.println("随机打乱后：" + list); // 如 [2,3,1]（每次结果不同）

Collections.fill(list,0);
System.out.println("填充 0 后：" + list); // [0,0,0]

2. Arrays(针对数组)

Arrays 与 Collections 功能类似，但专门针对 数组（如  int[]、 String[]、 Object[]）提供算法支持，同样包含排序、查找等核心操作。

2.1 排序算法

• sort(数组类型)：对数组进行自然排序（支持基本类型数组和对象数组）。
• sort(数组类型,Comparator<?super T> c)：对对象数组按自定义 Comparator 排序（基本类型数组不支持，需用包装类）。

import java.util.Arrays;

public class ArraysDemo {
    public static void main(String[] args) {
        // 1. 基本类型数组排序（升序）
        int[] intArr = {3,1,4};
        Arrays.sort(intArr);
        System.out.println("int 数组排序：" + Arrays.toString(intArr)); // [1,3,4]
        
        // 2. 对象数组自定义排序（降序）
        Integer[] integerArr = {5,2,7};
        Arrays.sort(integerArr, (a,b) -> b - a);
        System.out.println("Integer 数组降序：" + Arrays.toString(integerArr)); // [7,5,2]
        
        // 3. 自定义对象数组排序（按姓名长度）
        Person[] personArr = {new Person("Alice"),new Person("Bob"),new Person("Charlie")};
        Arrays.sort(personArr, (p1,p2) -> p1.getName().length() - p2.getName().length());
        System.out.println("按姓名长度排序：" + Arrays.toString(personArr)); 
        // [Bob(3),Alice(5),Charlie(7)]
    }
    
    static class Person {
        private String name;
        // 构造器、getter、toString 省略
    }
}

2.2 查找算法

• binarySearch(数组类型, 查找元素)：对已排序的数组进行二分查找（逻辑与 Collections.binarySearch 一致）。

int[] sortedArr = {1,3,5,7};
int index = Arrays.binarySearch(sortedArr,5);
System.out.println("5 的索引：" + index); // 2

2.3 其他常用算法