Java集合框架基础知识点全面解析

🚀前言

大家好！我是 EnigmaCoder。
本文介绍Java中的集合框架部分，从单列集合（Collection）和双列集合（Map）两大类进行解析。

🌟定义与体系结构

• 在 Java 中，集合（Collection） 是一种用于存储、管理多个数据元素的数据结构，它可以动态地存储一组相关的对象，解决了数组长度固定、类型单一的局限性。Java 集合框架（Java Collection Framework, JCF）提供了一套完整的集合接口、实现类和工具类，使得数据操作更加便捷和高效。

• 我们可以将集合大体分为两类，分别是单列集合（Collection）和双列集合（Map）。

🐧Collection

Collection代表单列集合，每个元素（数据）只包含一个值。

注意：虚边框的是接口，实边框的是实现类。

特点：

• List系列集合：添加的元素是有序、可重复、有索引。
  • ArrayList、LinkedList：有序、可重复、有索引。
• Set系列集合：添加的元素的无序、不重复、无索引。
  • HashSet：无序、不重复、无索引。
  • LinkedHashSet：有序、不重复、无索引。
  • TreeSet：按图大小默认升序排序、不重复、无索引。

💯常用功能

Collection是单列集合的祖宗，它规定的方法（功能）是全部单列集合都会继承的。

💯遍历方式

1. 迭代器遍历

迭代器是用来遍历集合的专用方式（数组没有迭代器），在java中迭代器的代表是Iterator。

• Collection集合获取迭代器的方法

• Iterator迭代器中的常用方法

示例：

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<String>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("C++");

        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            String ele = it.next();
            System.out.println(ele);
        }
    }
}

2. 增强for循环

• 增强for可以用来遍历集合或数组。
• 增强for遍历集合，本质就是迭代器遍历集合的简化写法。

格式：

for (元素的数据类型 变量名 : 数组或者集合){

}

示例：

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<String>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("C++");

        for(String s:list){
            System.out.println(s);
        }

        String [] arr = {"hello","world","java","C++"};
        for(String s:arr){
            System.out.println(s);
        }
    }
}

3. Lambda表达式

• 得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单、更直接的方式来遍历集合。

需要使用Collection的如下方法来完成：

示例：

public class Test {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<String>();
        list.add("hello");
        list.add("world");
        list.add("java");
        list.add("C++");

       list.forEach(new Consumer<String>() {
           @Override
           public void accept(String s) {
               System.out.println(s);
           }
       });

       list.forEach(s -> System.out.println(s));

       list.forEach(System.out::println);
    }
}

4. 三种遍历的区别

前置知识： 遍历集合的同时又存在增删集合元素的行为时可能出现业务异常，这种现象被称之为并发修改异常问题。

解决这一问题的方案：

• 如果集合支持索引，可以使用for循环遍历，每删除数据后做i--;或者可以倒着遍历。

// 正向遍历删除
for(int i=0; i<list.size(); i++){
   if(条件){
       list.remove(i);
       i--;
   }
}

// 倒序遍历删除（更优）
for(int i=list.size()-1; i>=0; i--){
   if(条件){
       list.remove(i);
   }
}

• 可以使用迭代器遍历，并用迭代器提供的删除方法删除数据（例如：it.remove();）。

Iterator<String> it = list.iterator();
while(it.hasNext()){
    String item = it.next();
    if(条件){
        it.remove();  // 使用迭代器的remove方法
    }
}
 

注意：增强for循环/Lambda遍历均不能解决并发修改异常问题，因此它们只适合做数据的遍历，不适合同时做增删操作，这就是三种遍历的区别。

💯List集合

List系列集合特点：有序、可重复、有索引。

• ArrayList：有序、可重复、有索引。
• LinkedList：有序、可重复、有索引。

ArrayList与LinkedList特点相同，但底层实现不同，适合的场景不同。

1. List集合继承了Collection的功能，同时也拥有自己的特有功能，这些功能都与索引有关。

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

public class ListExample {
    public static void main(String[] args) {
        // 创建List集合（使用ArrayList实现）
        List<String> fruits = new ArrayList<>();

        // 继承自Collection的功能：添加元素
        fruits.add("Apple");
        fruits.add("Banana");
        fruits.add("Cherry");

        // List特有功能：通过索引插入元素
        fruits.add(1, "Orange"); // 在索引1插入

        // List特有功能：通过索引获取元素
        String fruitAtIndex2 = fruits.get(2);
        System.out.println("索引2的元素: " + fruitAtIndex2);

        // List特有功能：通过索引修改元素
        fruits.set(0, "Mango");
        System.out.println("修改后的List: " + fruits);

        // 继承自Collection的功能：遍历元素
        for (String fruit : fruits) {
            System.out.println(fruit);
        }

        // List特有功能：通过索引删除元素
        fruits.remove(3);
        System.out.println("删除后的List: " + fruits);
    }
}
 

2. ArrayList底层是基于数组存储数据的。

   特点：

   • 查询速度快（注意：是根据索引查询数据块）：查询数据通过地址值和索引定位，查询任意数据耗时相同。
   • 增删数据效率低：可能需要把后面很多的数据进行前移。

3. LinkedList底层是基于双链表存储数据的。

   特点：

   • 链表中的数据是一个一个独立的结点组成的，结点在内存中是不连续的，每个结点包含数据值和下一个结点的地址。
   • 查询慢，无论查询哪个数据都要从头开始找。
   • 链表增删相对快。
   • LinkedList新增了很多首尾操作的特定方法：

LinkedList可以用来实现栈和队列。

（1）实现栈（LIFO结构）
栈是一种后进先出（Last-In-First-Out）的数据结构，LinkedList可以通过以下方式模拟栈操作：

• 压栈（Push）：使用addFirst()方法在链表头部插入元素

  LinkedList<Integer> stack = new LinkedList<>();
  stack.addFirst(1);  // 栈顶元素变为1
  stack.addFirst(2);  // 栈顶元素变为2
  

• 弹栈（Pop）：使用removeFirst()方法移除并返回头部元素

  int top = stack.removeFirst();  // 返回2并移除
  

• 查看栈顶（Peek）：使用getFirst()方法
• 典型应用场景：函数调用栈、浏览器后退功能、表达式求值等

（2）实现队列（FIFO结构）
队列是一种先进先出（First-In-First-Out）的数据结构，可以通过以下方式实现：

• 入队（Enqueue）：使用addLast()方法在尾部添加元素

  LinkedList<String> queue = new LinkedList<>();
  queue.addLast("A");  // 队首
  queue.addLast("B");
  

• 出队（Dequeue）：使用removeFirst()方法从头部移除元素

  String first = queue.removeFirst();  // 返回"A"
  

• 查看队首元素：使用getFirst()方法
• 典型应用场景：消息队列、多线程任务调度、BFS算法实现等

（3）实现双端队列（Deque）
LinkedList本身就实现了Deque接口，因此可以直接作为双端队列使用：

Deque<Integer> deque = new LinkedList<>();
deque.addFirst(1);    // 前端插入
deque.addLast(2);     // 后端插入
int front = deque.removeFirst();  // 移除前端元素
int rear = deque.removeLast();    // 移除后端元素

（4） 性能考虑

• 相比ArrayList，LinkedList在头部插入/删除操作上有O(1)的时间复杂度
• 但随机访问需要O(n)时间，因为需要遍历链表
• 在内存使用上，每个元素需要额外的空间存储前后节点引用

（5） 线程安全注意事项
标准LinkedList实现不是线程安全的，多线程环境下建议使用：

List<String> syncList = Collections.synchronizedList(new LinkedList<>());

通过这些实现方式，LinkedList可以灵活地满足不同场景下栈和队列的需求，特别是当需要频繁在数据结构两端进行操作时，其性能优势尤为明显。

💯Set集合

Set集合特点：无序：添加数据的顺序和获取出的数据顺序不一致；不重复；无索引；

• HashSet：无序、不重复、无索引。（底层原理：数组+链表+红黑树）
• LinkedHashSet：有序、不重复、无索引。（底层原理：数组+双链表+红黑树）
• TreeSet：排序、不重复、无索引。（底层原理：红黑树）

注意：Set要用到的常用的方法，基本上就是Collection提供的，自己几乎没有额外新增一些功能。JDK8开始，当链表长度超过8，且数组长度>=64时，HashSet自动将链表转为红黑树。

1. HashSet集合元素的去重操作

• 去重原理 HashSet的去重机制主要通过以下方式实现：

  • 当向HashSet添加元素时，会先计算元素的hashCode值
  • 根据hashCode值确定元素的存储位置
  • 如果该位置已有元素，则调用equals()方法比较
  • 如果equals()返回true，则视为重复元素，不会被添加

• 如果希望Set集合认为2个内容一样的对象是重复的，必须重写对象的hashCode()和equals()方法。(自定义对象去重复)

 class Student {
    private String id;
    private String name;
    
    // 构造方法等其他代码
    
    @Override
    public int hashCode() {
    //保证了不同的学生对象，如果内容一样返回的哈希值一定是一样的。
        return Objects.hash(id, name);
    }
    
    //只要两个对象的内容一样结果一定是true
    @Override
    public boolean equals(Object obj) {
        // 实现比较逻辑
    }
}

// 使用示例
Set<Student> studentSet = new HashSet<>();
studentSet.add(new Student("001", "王五"));
studentSet.add(new Student("001", "王五")); // 不会重复添加

2. TreeSet底层是基于红黑树（Red-Black Tree）实现的有序集合，它能够保证元素始终处于排序状态。红黑树是一种自平衡的二叉查找树，通过特定的着色规则和旋转操作来维护树的平衡，确保插入、删除和查找操作的时间复杂度都是O(log n)。

注意：

• 对于数值类型：如Integer、Double等，TreeSet默认按照数值本身的大小进行升序排序。例如：[3, 1, 2]会被排序为[1, 2, 3]。
• 对于字符串类型：默认按照字符串的首字符的Unicode编号升序排序。例如：["banana", "apple", "cherry"]会被排序为["apple", "banana", "cherry"]。
• 对于自定义类型：如Student对象，TreeSet默认是无法直接排序的，因为集合无法确定如何比较两个自定义对象的大小。

解决自定义类型排序的两种方案：

1. 实现Comparable接口：
   • 让自定义类实现Comparable接口，并重写compareTo()方法，定义对象的自然排序规则。
   • 示例：

     class Student implements Comparable<Student> {
         private String name;
         private int age;
     
         @Override
         public int compareTo(Student other) {
             return this.age - other.age; // 按照年龄升序排序
         }
     }
     

this是比较者，other是被比较者。如果要左边大于右边，就返回正整数；如果要左边小于右边，就返回负整数；如果要两边相等，就返回0。

2. 使用Comparator比较器：
   • 在创建TreeSet时传入一个自定义的Comparator比较器对象，定义临时的排序规则。
   • 示例：

     TreeSet<Student> students = new TreeSet<>(new Comparator<Student>() {
         @Override
         public int compare(Student s1, Student s2) {
             return s1.getName().compareTo(s2.getName()); // 按照姓名升序排序
         }
     });
     

🐍Map

Map代表双列集合，每个元素包含两个值（键值对）。

• Map集合也叫做“键值对集合”，格式：key1=value1,key2=value2,key3=value3,...
• Map集合的所有键是不允许重复的，但值可以重复，键和值是一一对应的，每一个键只能找到自己对应的值。

注意：虚边框的是接口，实边框的是实现类。

特点：
Map系列集合的特点都是由键决定的，值只是一个附属品，值是不做要求的。

• HashMap（键决定特点）：无序、不重复、无索引。（用的最多）
• LinkedHashMap（键决定特点）：有序、不重复、无索引。
• TreeMap（键决定特点）：按照大小默认升序排序、不重复、无索引。

💯常用方法

Map是双列集合的祖宗，它的功能是全部双列集合都可以继承来使用的。

💯遍历方式

1. 键找值

先获取Map集合全部的键，再通过遍历键来找值。

Set<String>Keys = map.keySet();

for(String key:keys){
  Integer value = map.get(key);
  System.out.println(key + "=" + value);
}

2. 键值对

把Map集合转换成Set集合，里面的元素类型都是键值对类型（Map.Entry<String,Integer>）。

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. Lambda

需要运用Map的如下方法：

map.forEach((k,v)->{
    System.out.println(key + "--->" + value);
});

💯实现类详解与底层原理

1. HashMap集合的底层原理深入解析

HashMap是Java集合框架中最常用的Map实现类，其底层采用哈希表（数组+链表/红黑树）结构实现。关键特性包括：

• 初始容量默认为16，负载因子0.75
• 当链表长度超过8且数组长度≥64时，链表会转为红黑树
• 通过hash(key.hashCode())计算索引位置

HashSet与HashMap的关系更为明确：

// HashSet的源码实现
public class HashSet<E> 
    implements Set<E> {
    private transient HashMap<E,Object> map;
    
    // 所有值都关联同一个虚拟对象
    private static final Object PRESENT = new Object();
    
    public HashSet() {
        map = new HashMap<>();  // 底层实际使用HashMap存储
    }
    
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

典型应用场景：

• 快速查找（时间复杂度O(1)）
• 去重存储
• 缓存实现

2. LinkedHashMap的底层实现机制

LinkedHashMap继承自HashMap，在哈希表的基础上增加了双向链表维护插入顺序或访问顺序：

// 典型节点结构
static class Entry<K,V> extends HashMap.Node<K,V> {
    Entry<K,V> before, after;  // 双向链表指针
    Entry(int hash, K key, V value, Node<K,V> next) {
        super(hash, key, value, next);
    }
}

有序性实现原理：

• 默认按插入顺序排序（accessOrder=false）
• 设置accessOrder=true时按访问顺序排序（适合实现LRU缓存）
• 通过重写newNode()方法创建带链表指针的节点

LinkedHashSet的实现方式：

public LinkedHashSet() {
    super(16, 0.75f, true);  // 调用HashSet的特定构造器
    // 底层实际使用LinkedHashMap
}

3. TreeMap的红黑树实现详解

TreeMap基于红黑树（自平衡二叉查找树）实现，主要特点：

• 元素默认按key的自然顺序排序
• 可通过Comparator自定义排序规则
• 基本操作时间复杂度为O(log n)

红黑树五大特性：

1. 节点是红色或黑色
2. 根节点是黑色
3. 所有叶子节点(NIL)是黑色
4. 红色节点的子节点必须是黑色
5. 从任一节点到其每个叶子的路径包含相同数目的黑色节点

TreeSet的底层实现：

public TreeSet() {
    this(new TreeMap<E,Object>());  // 使用TreeMap作为存储
}

排序示例：

TreeMap<String, Integer> map = new TreeMap<>((a,b) -> b.length()-a.length());
map.put("apple", 1);
map.put("banana", 2);
// 将按字符串长度降序排列