一、为什么要有集合？

Student[] arr = new Student[10];
//问题：长度不可变
arr[11] = new Student();  // 数组越界
//不便于删除、添加
arr.remove();  // 数组没有remove方法
arr.add();     // 数组没有add方法

二、集合的体系结构

Collection接口：单列集合的顶级接口
    |--List接口：有序
        |--ArrayList类：底层是动态数组，set和get速度快，add和remove速度慢因为要移动数据
        |--Vector类：线程安全的ArrayList
        |--LinkedList类：底层是双向链表，add和remove速度快，set和get速度慢因为没有下标
        
Map接口：双列集合的顶级接口
    |--HashMap类
    |--TreeMap类
    |--Hashtable类

三、Collection接口

是什么？

单列集合的顶级接口

方法：

boolean add(E e)         // 添加元素e
boolean remove(Object o) // 删除元素o
int size()              // 返回集合中元素个数
boolean isEmpty()        // 判断集合是否为空
boolean contains(Object obj)  // 判断集合中是否包含obj
Iterator iterator()     // 返回迭代器对象

四、List接口

是什么？

它是一个元素存取有序的集合

方法：

void add(int index,E element)  // 把元素添加到指定下标的位置，其他元素后移
E get(int index)               // 返回指定下标的元素
E set(int index,E element)     // 修改指定下标处的元素
E remove(int index)            // 删除指定下标的元素

案例：

   List<String> stringlist = new ArrayList<>();
//        增加数据
        stringlist.add("aaaa-1");
        stringlist.add("aaaa-2");
        stringlist.add("aaaa-3");
        stringlist.add(0,"bbb-4");

        System.out.println("增强for循环");
        for (String s : stringlist) {
            System.out.println(s);
        }
//        修改数据
        System.out.println("修改");
        stringlist.set(1,"bbb-3");
        System.out.println("for循环遍历");
        for (int i = 0; i <stringlist.size() ; i++) {
//            查询数据
            System.out.println(stringlist.get(i));
        }
//        删除数据
        System.out.println("删除");
        for (int i = stringlist.size()-1; i >=0 ; i--) {
           stringlist.remove(i);
        }
        stringlist.clear();
        System.out.println("迭代器遍历");
        Iterator<String> iterator = stringlist.iterator();
        while (iterator.hasNext()){
            String str =iterator.next();
            System.out.println(str);
        }

五、ArrayList类

特点：

• 基于动态数组实现

• 查询快（get、set），增删慢

• 线程不安全

• 可以存储null

• 有扩容机制

扩容机制：

// JDK 1.8
int newCapacity = oldCapacity + (oldCapacity >> 1);  // 1.5倍扩容

常用方法：

// 继承自Collection和List的方法
add(E e)
remove(Object o)
get(int index)
set(int index, E element)

// 特有方法
ensureCapacity(int minCapacity)  // 确保最小容量
trimToSize()                     // 调整容量到实际大小

示例：

  List<String> stringlist = new ArrayList<>();
//        增加数据
        stringlist.add("jack");
        stringlist.add("rost");
        stringlist.add("lisi");
        stringlist.add("zhangsan");
        stringlist.add("lisi");
        stringlist.add("jetty");

        int oneIndex = -1;
        int lastIndex = -1;
        for (int i = 0; i <stringlist.size() ; i++) {

            if ("lisi".equals(stringlist.get(i))){
                if (oneIndex == -1){
                    oneIndex = i;
                }
                lastIndex = i;
            }

        }
        System.out.println("list第一次出现的下标"+oneIndex+" "+"list最后一次出现的下标"+lastIndex);


        stringlist.remove(0);
        stringlist.remove(stringlist.size()-1);
        for (String str:stringlist) {
            System.out.println(str);
        }
    }

六、Vector类

特点：

• 基于动态数组实现

• 线程安全（synchronized修饰方法）

• 查询快，增删慢

• 历史遗留类，不推荐使用

与ArrayList的区别：

1. 线程安全性：Vector线程安全，ArrayList非线程安全

2. 扩容机制：Vector默认扩容2倍，ArrayList扩容1.5倍

3. 性能：Vector有同步开销，性能较低

常用方法：

// Vector特有的方法
addElement(E obj)    // 添加元素
elementAt(int index) // 获取指定位置元素
elements()           // 返回枚举

示例：

public static void main(String[] args) {
        List<Integer> intList = new Vector<>();
        intList.add(1);
        intList.add(2);
        intList.add(3);
        intList.add(4);
        intList.add(5);
        System.out.println(intList);
        intList.set(3,23);
        System.out.println(intList);
        Integer integer = intList.get(2);
        System.out.println(integer);
        intList.remove(1);
        System.out.println(intList);
    }

七、LinkedList类

特点：

• 基于双向链表实现

• 增删快（add、remove），查询慢

• 实现了List和Deque接口

• 线程不安全

• 每个元素包含前驱和后继指针

底层结构：

private static class Node<E> {
    E item;         // 数据
    Node<E> next;   // 后继节点
    Node<E> prev;   // 前驱节点
}

常用方法：

// List接口方法
add(E e)
get(int index)
remove(int index)

// 链表特有方法
addFirst(E e)      // 头部添加
addLast(E e)       // 尾部添加
getFirst()         // 获取头部元素
getLast()          // 获取尾部元素
removeFirst()      // 删除头部元素
removeLast()       // 删除尾部元素

// 队列方法
offer(E e)         // 添加到队列尾部
poll()             // 移除并返回头部元素
peek()             // 查看头部元素

示例：

LinkedList<String> list = new LinkedList<>();
list.add("Java");
list.addFirst("C++");  // 头部添加
list.addLast("Python");  // 尾部添加
String first = list.getFirst();  // "C++"
String last = list.getLast();    // "Python"
list.removeFirst();  // 删除头部

八、HashSet类详解 ⚡

8.1 什么是HashSet？

HashSet是Set接口最常用的实现类，基于HashMap实现。它存储唯一的元素，但不保证迭代顺序。

// HashSet的声明
public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

8.2 核心特点

• ✅ 无序性：不保证元素的存储顺序

• ✅ 唯一性：不允许重复元素

• ✅ 允许null：可以存储一个null元素

• ✅ 高性能：添加、删除、查找都是O(1)时间复杂度

• ❌ 非线程安全：多线程环境下需要同步

8.3 底层实现原理 🔍

HashSet底层实际上是HashMap：

// HashSet源码关键部分
public class HashSet<E> {
    // 底层使用HashMap存储
    private transient HashMap<E,Object> map;
    
    // 虚拟的value值
    private static final Object PRESENT = new Object();
    
    // 构造方法
    public HashSet() {
        map = new HashMap<>();  // 默认初始容量16，加载因子0.75
    }
    
    // 添加元素 - 实际上是把元素作为key放入HashMap
    public boolean add(E e) {
        return map.put(e, PRESENT) == null;
    }
}

哈希表工作原理：

// 简化版的工作流程
public boolean add(E element) {
    // 1. 计算hashCode
    int hash = element.hashCode();
    
    // 2. 通过哈希算法计算索引位置
    int index = (hash & 0x7FFFFFFF) % table.length;
    
    // 3. 如果该位置为空，直接放入
    if (table[index] == null) {
        table[index] = new Node<>(hash, element);
        return true;
    }
    
    // 4. 如果该位置不为空，遍历链表/红黑树
    // 比较hashCode，如果相同再调用equals()方法
    // 如果equals()返回true，表示元素已存在，不添加
    // 如果equals()返回false，添加到链表末尾
}

8.4 使用示例 📝

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

public class HashSetExample {
    public static void main(String[] args) {
        // 1. 创建HashSet
        Set<String> fruitSet = new HashSet<>();
        
        // 2. 添加元素
        fruitSet.add("Apple");
        fruitSet.add("Banana");
        fruitSet.add("Orange");
        fruitSet.add("Apple");  // 重复元素，不会被添加
        fruitSet.add(null);     // 可以添加null
        
        System.out.println("集合内容: " + fruitSet);
        System.out.println("集合大小: " + fruitSet.size());  // 4
        
        // 3. 判断是否包含
        System.out.println("是否包含Apple: " + fruitSet.contains("Apple"));  // true
        
        // 4. 删除元素
        fruitSet.remove("Banana");
        System.out.println("删除Banana后: " + fruitSet);
        
        // 5. 遍历HashSet
        System.out.println("\n=== 遍历方式 ===");
        // 方式1: 增强for循环
        for (String fruit : fruitSet) {
            System.out.println(fruit);
        }
        
        // 方式2: 迭代器
        java.util.Iterator<String> iterator = fruitSet.iterator();
        while (iterator.hasNext()) {
            System.out.println(iterator.next());
        }
        
        // 方式3: forEach (Java 8+)
        fruitSet.forEach(System.out::println);
    }
}

8.5 存储自定义对象 📦

重要：存储自定义对象必须重写hashCode()和equals()方法！

import java.util.HashSet;
import java.util.Objects;

class Student {
    private String id;
    private String name;
    
    public Student(String id, String name) {
        this.id = id;
        this.name = name;
    }
    
    // 必须重写hashCode和equals方法
    @Override
    public int hashCode() {
        // 使用Objects工具类生成hashCode
        return Objects.hash(id, name);
    }
    
    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return Objects.equals(id, student.id) && 
               Objects.equals(name, student.name);
    }
    
    @Override
    public String toString() {
        return "Student{id='" + id + "', name='" + name + "'}";
    }
}

public class CustomObjectExample {
    public static void main(String[] args) {
        Set<Student> studentSet = new HashSet<>();
        
        Student s1 = new Student("001", "张三");
        Student s2 = new Student("002", "李四");
        Student s3 = new Student("001", "张三");  // 与s1相同
        
        studentSet.add(s1);
        studentSet.add(s2);
        studentSet.add(s3);  // 不会被添加，因为与s1相同
        
        System.out.println("学生集合: " + studentSet);
        System.out.println("集合大小: " + studentSet.size());  // 2
    }
}

---

九、LinkedHashSet类详解 🔗

9.1 什么是LinkedHashSet？

LinkedHashSet是HashSet的子类，在HashSet的基础上维护了元素的插入顺序。

// LinkedHashSet的声明
public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable

9.2 核心特点

• ✅ 有序性：保证元素的插入顺序

• ✅ 唯一性：不允许重复元素

• ✅ 允许null：可以存储一个null元素

• ✅ 性能良好：接近HashSet的性能

• ❌ 内存占用稍大：需要维护链表结构

9.3 底层实现原理 🏗️

LinkedHashSet底层是LinkedHashMap：

// LinkedHashSet源码关键部分
public class LinkedHashSet<E> extends HashSet<E> {
    // 调用父类构造器，创建LinkedHashMap
    public LinkedHashSet() {
        super(16, .75f, true);
    }
}

// HashSet中的构造器
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

数据结构：数组 + 双向链表

索引   元素链表
 0  -> null
 1  -> Entry1("A") <-> Entry2("B")  // 双向链表保持顺序
 2  -> Entry3("C")

9.4 与HashSet的对比 📊

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

public class LinkedHashSetExample {
    public static void main(String[] args) {
        System.out.println("=== HashSet（无序）===");
        Set<String> hashSet = new HashSet<>();
        hashSet.add("Banana");
        hashSet.add("Apple");
        hashSet.add("Orange");
        hashSet.add("Grape");
        
        for (String fruit : hashSet) {
            System.out.println(fruit);  // 顺序不确定
        }
        
        System.out.println("\n=== LinkedHashSet（有序）===");
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("Banana");
        linkedHashSet.add("Apple");
        linkedHashSet.add("Orange");
        linkedHashSet.add("Grape");
        
        for (String fruit : linkedHashSet) {
            System.out.println(fruit);  // 输出：Banana, Apple, Orange, Grape
        }
    }
}

9.5 性能对比表 📈

操作	HashSet	LinkedHashSet
添加元素	O(1)	O(1)
删除元素	O(1)	O(1)
查找元素	O(1)	O(1)
遍历元素	快	稍快（按插入顺序）
内存占用	较小	较大（多存储两个指针）
顺序保证	无	插入顺序

---

十、TreeSet类详解 🌳

8101 什么是TreeSet？

TreeSet是基于红黑树（自平衡二叉查找树）实现的Set，元素会自动排序。

// TreeSet的声明
public class TreeSet<E> extends AbstractSet<E>
    implements NavigableSet<E>, Cloneable, java.io.Serializable

10.2 核心特点

• ✅ 有序性：元素自动排序

• ✅ 唯一性：不允许重复元素

• ❌ 不允许null：不能存储null元素

• ✅ 范围查询：支持子集、头部、尾部视图

• ⚡ 性能：添加、删除、查找都是O(log n)

10.3 排序方式 🎯

方式1：自然排序（元素实现Comparable接口）

import java.util.TreeSet;

// 自定义类实现Comparable接口
class Student implements Comparable<Student> {
    private String name;
    private int score;
    
    public Student(String name, int score) {
        this.name = name;
        this.score = score;
    }
    
    // 按分数降序排序
    @Override
    public int compareTo(Student other) {
        // 分数高的排前面
        int result = other.score - this.score;
        
        // 分数相同按姓名排序
        if (result == 0) {
            result = this.name.compareTo(other.name);
        }
        return result;
    }
    
    @Override
    public String toString() {
        return name + "(" + score + ")";
    }
}

public class NaturalSortExample {
    public static void main(String[] args) {
        TreeSet<Student> treeSet = new TreeSet<>();
        
        treeSet.add(new Student("张三", 85));
        treeSet.add(new Student("李四", 92));
        treeSet.add(new Student("王五", 85));  // 分数相同，按姓名排序
        treeSet.add(new Student("赵六", 78));
        
        System.out.println("按分数排序:");
        for (Student student : treeSet) {
            System.out.println(student);
        }
        // 输出：
        // 李四(92)
        // 王五(85)
        // 张三(85)
        // 赵六(78)
    }
}

方式2：比较器排序（创建时传入Comparator）

import java.util.Comparator;
import java.util.TreeSet;

class Product {
    private String name;
    private double price;
    
    public Product(String name, double price) {
        this.name = name;
        this.price = price;
    }
    
    // getter方法省略...
}

public class ComparatorSortExample {
    public static void main(String[] args) {
        // 方式1：匿名内部类
        TreeSet<Product> treeSet1 = new TreeSet<>(new Comparator<Product>() {
            @Override
            public int compare(Product p1, Product p2) {
                // 按价格升序
                int result = Double.compare(p1.getPrice(), p2.getPrice());
                if (result == 0) {
                    result = p1.getName().compareTo(p2.getName());
                }
                return result;
            }
        });
        
        // 方式2：Lambda表达式（Java 8+）
        TreeSet<Product> treeSet2 = new TreeSet<>(
            Comparator.comparingDouble(Product::getPrice)
                     .thenComparing(Product::getName)
        );
        
        // 方式3：方法引用
        TreeSet<String> treeSet3 = new TreeSet<>(String::compareToIgnoreCase);
    }
}

10.4 TreeSet特有方法 🎁

import java.util.TreeSet;
import java.util.SortedSet;

public class TreeSetMethods {
    public static void main(String[] args) {
        TreeSet<Integer> numbers = new TreeSet<>();
        
        // 添加元素
        numbers.add(10);
        numbers.add(20);
        numbers.add(30);
        numbers.add(40);
        numbers.add(50);
        
        // 1. 获取第一个和最后一个元素
        System.out.println("第一个元素: " + numbers.first());  // 10
        System.out.println("最后一个元素: " + numbers.last());  // 50
        
        // 2. 获取小于/大于某个值的元素
        System.out.println("小于25的最大元素: " + numbers.lower(25));  // 20
        System.out.println("大于25的最小元素: " + numbers.higher(25));  // 30
        
        // 3. 获取小于等于/大于等于的元素
        System.out.println("小于等于25的最大元素: " + numbers.floor(25));  // 20
        System.out.println("大于等于25的最小元素: " + numbers.ceiling(25));  // 30
        
        // 4. 获取子集
        SortedSet<Integer> headSet = numbers.headSet(30);  // 小于30的元素
        System.out.println("小于30的元素: " + headSet);  // [10, 20]
        
        SortedSet<Integer> tailSet = numbers.tailSet(30);  // 大于等于30的元素
        System.out.println("大于等于30的元素: " + tailSet);  // [30, 40, 50]
        
        SortedSet<Integer> subSet = numbers.subSet(20, 40);  // 20 <= x < 40
        System.out.println("20到40之间的元素: " + subSet);  // [20, 30]
        
        // 5. 删除并返回第一个/最后一个元素
        Integer first = numbers.pollFirst();  // 删除并返回10
        Integer last = numbers.pollLast();    // 删除并返回50
    }
}

10.5 三种Set实现类对比总结 📊

特性	HashSet	LinkedHashSet	TreeSet
底层数据结构​	哈希表	哈希表+双向链表	红黑树
元素顺序​	无序	插入顺序	自然排序/比较器排序
性能​	添加/删除/查找：O(1)	添加/删除/查找：接近O(1)	添加/删除/查找：O(log n)
允许null​	✅ 允许1个	✅ 允许1个	❌ 不允许
线程安全​	❌ 不安全	❌ 不安全	❌ 不安全
内存占用​	小	中	大
使用场景​	需要快速查找，不关心顺序	需要保持插入顺序	需要元素排序

10.6 如何选择合适的Set？ 🤔

// 场景1：只需要去重，不关心顺序
// 推荐：HashSet
Set<String> quickLookupSet = new HashSet<>();

// 场景2：需要去重，且要保持插入顺序
// 推荐：LinkedHashSet
Set<String> insertionOrderSet = new LinkedHashSet<>();

// 场景3：需要去重，且要自动排序
// 推荐：TreeSet
Set<String> sortedSet = new TreeSet<>();

// 场景4：需要线程安全的Set
// 推荐：Collections.synchronizedSet包装
Set<String> synchronizedSet = Collections.synchronizedSet(new HashSet<>());
// 或使用ConcurrentHashMap.newKeySet()（Java 8+）
Set<String> concurrentSet = ConcurrentHashMap.newKeySet();

总结对比

特性	ArrayList	Vector	LinkedList
底层结构	动态数组	动态数组	双向链表
线程安全	不安全	安全	不安全
查询速度	快	快	慢
增删速度	慢	慢	快
内存占用	小	小	大
扩容机制	1.5倍	2倍	不扩容

使用场景

记住选择原则：

1. ArrayList：适合查询频繁，增删较少的场景

2. Vector：多线程环境（但推荐使用Collections.synchronizedList或CopyOnWriteArrayList）

3. LinkedList：适合频繁在头尾增删元素的场景，或用作队列/栈

4. HashSet：最常用，性能最好，但不保证顺序

5. LinkedHashSet：需要保持插入顺序时的选择

6. 要性能 → HashSet

7. 要顺序 → LinkedHashSet

8. 要排序 → TreeSet

   • TreeSet：需要元素排序时的选择