泛型 | 集合

Java核心基础卷6

泛型程序设计

教科书式解析：Java 泛型程序设计

一、为什么要使用泛型程序设计？

1. 类型安全（Type Safety）

   • 编译时类型检查，避免ClassCastException
   • 消除强制类型转换，减少运行时错误

   // 非泛型：存在类型转换风险
   List list = new ArrayList();
   list.add("text");
   Integer num = (Integer) list.get(0); // 运行时ClassCastException
   
   // 泛型：编译时捕获错误
   List<String> safeList = new ArrayList<>();
   safeList.add("text");
   // safeList.add(100);  // 编译错误

2. 代码复用（Code Reusability）

   • 编写通用算法，适用于多种数据类型
   • 避免为不同类型重写相同逻辑

   // 泛型方法可处理任意类型
   public <T> T getFirst(List<T> list) {
       return list.get(0);
   }

3. 代码清晰度（Code Clarity）

   • 显式声明容器元素类型
   • 增强代码可读性和可维护性

   Map<String, List<Student>> school = new HashMap<>(); // 明确键值类型

4. API设计优化

   • 集合框架（Collection Framework）基于泛型
   • 提供类型安全的容器接口

二、定义泛型类

public class Box<T> {      // T: 类型参数
    private T content;     // 泛型字段

    public void set(T content) { 
        this.content = content;
    }

    public T get() {       // 返回泛型类型
        return content;
    }
}

使用示例：

Box<String> stringBox = new Box<>();
stringBox.set("Hello");
String value = stringBox.get(); // 无需强制转换

Box<Integer> intBox = new Box<>();
intBox.set(100);

三、泛型方法

// 类型参数声明在返回类型前
public static <T> T findMax(T[] array, Comparator<T> comparator) {
    T max = array[0];
    for (T item : array) {
        if (comparator.compare(item, max) > 0) {
            max = item;
        }
    }
    return max;
}

类型推断：

String[] words = {"apple", "banana", "pear"};
String maxWord = findMax(words, String::compareTo); // 自动推断T为String

四、类型变量的限定

// T必须实现Comparable接口
public static <T extends Comparable<T>> T max(T a, T b) {
    return a.compareTo(b) > 0 ? a : b;
}

// 多限定：类在前，接口在后
public static <T extends Number & Comparable<T>> T clamp(T val, T min, T max) {
    if (val.compareTo(min) < 0) return min;
    if (val.compareTo(max) > 0) return max;
    return val;
}

限定规则：

• extends 表示上界（类/接口）
• 最多一个类限定，多个接口用&连接
• 类型变量不能有下界限定

五、泛型代码和虚拟机（类型擦除）

1. 类型擦除（Type Erasure）

   • 编译时擦除类型参数，替换为限定类型
   • 无限定类型替换为Object

   // 编译前
   Box<String> box = new Box<>();
   // 编译后（字节码）
   Box box = new Box(); // 原始类型

2. 桥方法（Bridge Methods）

   • 编译器生成合成方法保持多态性

   // 泛型类
   class Node<T> {
       public void setData(T data) {...}
   }
   
   // 子类
   class IntNode extends Node<Integer> {
       // 编译器生成桥方法：
       // public void setData(Object data) {
       //    setData((Integer) data);
       // }
   }

六、限制与局限性

1. 不能用基本类型实例化

   // List<int> list; // 错误
   List<Integer> list; // 正确

2. 运行时类型查询无效

   if (box instanceof Box<String>) {...} // 编译错误

3. 不能创建参数化类型数组

   // Box<String>[] boxes = new Box<String>[10]; // 错误
   Box<String>[] boxes = (Box<String>[]) new Box<?>[10]; // 警告

4. 不能实例化类型变量

   public class Box<T> {
       // private T obj = new T(); // 错误
       private T obj = (T) new Object(); // 不安全
   }

5. 泛型类不能继承Throwable

   // class Problem<T> extends Exception {...} // 错误

七、泛型类型的继承规则

1. 参数化类型无协变性

   // 错误示例
   List<String> strList = new ArrayList<>();
   // List<Object> objList = strList; // 编译错误

2. 原始类型兼容性

   List rawList = new ArrayList<String>(); // 警告

3. 通配符继承关系

     graph TD
     A[List<?>] --> B[List<? extends Number>]
     A --> C[List<? super Integer>]
     B --> D[List<Integer>]
     C --> D
   

八、通配符类型（Wildcard Types）

1. 上界通配符（? extends T）

   // 可读取为T类型，不能写入（null除外）
   void process(List<? extends Number> list) {
       Number num = list.get(0); // 安全
       // list.add(10); // 错误
   }

2. 下界通配符（? super T）

   // 可写入T类型，读取为Object
   void addNumbers(List<? super Integer> list) {
       list.add(100); // 安全
       Object obj = list.get(0); // 需强制转换
   }

3. 无限定通配符（?）

   // 只允许null操作
   void printList(List<?> list) {
       for (Object elem : list) {
           System.out.println(elem);
       }
   }

PECS原则（Producer-Extends, Consumer-Super）：

• 生产者用? extends T（输出数据）
• 消费者用? super T（输入数据）

关键概念总结

泛型程序设计是Java类型系统的核心进步，通过编译时类型检查显著提升程序健壮性，同时保持与旧代码的兼容性。掌握泛型机制对开发高质量Java程序至关重要。

// 安全读取Number及其子类
void printNumbers(List<? extends Number> list) {
    for (Number n : list) {  // 安全读取
        System.out.println(n.doubleValue());
    }
    // list.add(10); // 编译错误！不能写入
}

// 安全写入Integer及其父类
void addIntegers(List<? super Integer> list) {
    list.add(100);    // 安全写入Integer
    list.add(200);
    // Integer num = list.get(0); // 编译错误！只能读取为Object
    Object obj = list.get(0);  // 必须转为Object
}

// T必须实现Comparable
class SortedContainer<T extends Comparable<T>> {
    private T value;

    public boolean isGreaterThan(T other) {
        return value.compareTo(other) > 0;  // 可调用Comparable方法
    }
}

// 正确应用PECS
public static <T> void copy(
    List<? extends T> src,  // PRODUCER: 提供T对象
    List<? super T> dest    // CONSUMER: 消费T对象
) {
    for (T item : src) {
        dest.add(item);  // 安全读写
    }
}

  graph TD
    Object -->|super| Number[Number super]
    Number -->|super| Integer[Integer]

    Producer[Producer: ? extends Number] -->|接受| Integer
    Producer -->|接受| Double[Double]

    Consumer[Consumer: ? super Integer] -->|接受| Number
    Consumer -->|接受| Object

    Generic[泛型形参: T extends Number] -->|约束| Integer
    Generic -->|约束| Double

集合

Java 集合框架（Collections Framework）全面解析

一、框架设计目标

1. 统一架构：提供标准化的集合操作接口
2. 高复用性：解耦接口与实现
3. 算法复用：通用算法（排序/查找）独立于数据结构
4. 类型安全：泛型支持（JDK5+）
5. 性能优化：针对不同场景提供多种实现

二、核心接口层次

  graph TD
    Iterable --> Collection
    Collection --> List
    Collection --> Set
    Collection --> Queue
    Set --> SortedSet
    Queue --> Deque
    Map --> SortedMap

1. 根接口：

   • Iterable：支持迭代器（iterator()）
   • Collection：所有集合的基接口（add/remove/size）

2. 核心子接口：

   • List：有序可重复集合（索引访问）
   • Set：无序唯一元素集合
   • Queue：队列（FIFO/LIFO）
   • Deque：双端队列
   • Map：键值对集合（独立于Collection体系）

三、关键实现类对比

1. List 实现

2. Set 实现

3. Queue/Deque 实现

4. Map 实现

四、核心算法工具类

1. Collections 工具类

// 排序
Collections.sort(list); 

// 线程安全包装
List<String> syncList = Collections.synchronizedList(new ArrayList<>());

// 不可变集合
List<String> unmodifiable = Collections.unmodifiableList(list);

// 二分查找
int index = Collections.binarySearch(sortedList, key);

2. Arrays 工具类

// 数组转集合
List<String> list = Arrays.asList("A", "B", "C");

// 快速排序
Arrays.sort(arr);

// 并行操作
Arrays.parallelSetAll(arr, i -> i * 2);

五、并发集合（java.util.concurrent）

1. 锁分离技术：

   • ConcurrentHashMap：分段锁（JDK7），CAS+红黑树（JDK8+）
   • ConcurrentSkipListMap：跳表实现

2. 阻塞队列：

   BlockingQueue<String> queue = new ArrayBlockingQueue<>(10);
   queue.put("item");  // 阻塞插入
   String item = queue.take(); // 阻塞获取

3. 写时复制：

   • CopyOnWriteArrayList：适合读多写少场景
   • 修改时创建新数组，不影响读操作

4. 并发工具：

   • ConcurrentLinkedQueue：无锁队列
   • ConcurrentSkipListSet：并发有序集合

六、性能选型指南

七、最佳实践与注意事项

1. 泛型初始化：

   // 菱形语法（JDK7+）
   List<String> list = new ArrayList<>();

2. 集合判空：

   // 使用isEmpty()而非size()==0
   if (!collection.isEmpty()) { ... }

3. 迭代安全：

   // 使用迭代器删除元素
   Iterator<Integer> it = list.iterator();
   while (it.hasNext()) {
       if (it.next() % 2 == 0) {
           it.remove();  // 安全删除
       }
   }

4. 容量优化：

   // 预分配ArrayList容量
   List<String> largeList = new ArrayList<>(10000);

5. 避免装箱开销：

   // 使用原始类型集合（Trove/GS Collections）
   IntList intList = new TIntArrayList();

6. Map遍历优化：

   // JDK8+ 使用forEach
   map.forEach((k, v) -> System.out.println(k + ": " + v));

八、历史演进

1. JDK 1.0：

   • Vector, Hashtable, Stack（已过时）

2. JDK 1.2：

   • 集合框架诞生（List/Set/Map体系）

3. JDK 5：

   • 泛型支持
   • ConcurrentHashMap引入

4. JDK 7：

   • 分段锁优化
   • 转移表（Transfer）技术

5. JDK 8：

   • HashMap红黑树优化（链表>8转换）
   • 流式API支持集合操作

   list.stream()
       .filter(s -> s.length() > 3)
       .map(String::toUpperCase)
       .collect(Collectors.toList());

6. JDK 9+：

   • 工厂方法创建不可变集合

   List<String> names = List.of("Alice", "Bob", "Charlie");
   Set<Integer> nums = Set.of(1, 2, 3);
   Map<String, Integer> scores = Map.of("Alice", 90, "Bob", 85);

总结

Java集合框架提供了标准化、高性能、可扩展的数据结构实现：

• 基础集合：ArrayList/HashMap/HashSet满足大部分需求
• 特殊场景：LinkedList/TreeMap/LinkedHashMap提供有序或插入顺序保持
• 并发环境：ConcurrentHashMap/CopyOnWriteArrayList保证线程安全
• 工具类：Collections/Arrays提供丰富算法操作

设计原则：

1. 80%场景使用ArrayList+HashMap组合
2. 并发场景优先选择java.util.concurrent实现
3. 只读集合使用不可变集合（JDK9+）
4. 大数据量场景关注初始容量和负载因子

掌握集合框架的选择标准和底层实现原理，是编写高效Java程序的核心能力之一。

Java 集合框架核心接口详解

一、接口层次结构

  graph TD
    Iterable --> Collection
    Collection --> List
    Collection --> Set
    Collection --> Queue
    Set --> SortedSet
    Queue --> Deque
    Map --> SortedMap

二、根接口 Iterable

核心功能：支持迭代器遍历

public interface Iterable<T> {
    Iterator<T> iterator();  // 获取迭代器
    
    // JDK8+ 默认方法
    default void forEach(Consumer<? super T> action) {
        for (T t : this) {
            action.accept(t);
        }
    }
    
    default Spliterator<T> spliterator() { /* 分割迭代器 */ }
}

三、Collection 接口（集合根接口）

核心方法：

public interface Collection<E> extends Iterable<E> {
    // 基本操作
    int size();
    boolean isEmpty();
    boolean contains(Object o);
    boolean add(E e);
    boolean remove(Object o);
    Iterator<E> iterator();
    
    // 批量操作
    boolean containsAll(Collection<?> c);
    boolean addAll(Collection<? extends E> c);
    boolean removeAll(Collection<?> c);
    boolean retainAll(Collection<?> c);
    void clear();
    
    // 数组转换
    Object[] toArray();
    <T> T[] toArray(T[] a);
    
    // JDK8+ 流操作
    default Stream<E> stream() { /* 顺序流 */ }
    default Stream<E> parallelStream() { /* 并行流 */ }
}

四、List 接口（有序集合）

特点：元素有序、可重复、支持索引访问

public interface List<E> extends Collection<E> {
    // 位置访问
    E get(int index);
    E set(int index, E element);
    void add(int index, E element);
    E remove(int index);
    
    // 搜索
    int indexOf(Object o);
    int lastIndexOf(Object o);
    
    // 列表迭代器
    ListIterator<E> listIterator();
    ListIterator<E> listIterator(int index);
    
    // 子列表
    List<E> subList(int fromIndex, int toIndex);
    
    // JDK8+ 默认方法
    default void replaceAll(UnaryOperator<E> operator) { /* 元素替换 */ }
    default void sort(Comparator<? super E> c) { /* 排序 */ }
}

五、Set 接口（唯一集合）

特点：元素唯一、无序（部分实现有序）

public interface Set<E> extends Collection<E> {
    // 继承Collection方法
    // 特殊约定：禁止重复元素
    // equals方法实现：比较元素是否相同
}

六、Queue 接口（队列）

特点：先进先出（FIFO）处理模型

public interface Queue<E> extends Collection<E> {
    // 插入
    boolean add(E e);      // 失败时抛异常
    boolean offer(E e);    // 失败时返回false
    
    // 移除
    E remove();            // 空队列抛异常
    E poll();              // 空队列返回null
    
    // 检查
    E element();           // 空队列抛异常
    E peek();              // 空队列返回null
}

七、Deque 接口（双端队列）

特点：支持两端操作

public interface Deque<E> extends Queue<E> {
    // 前端操作
    void addFirst(E e);
    boolean offerFirst(E e);
    E removeFirst();
    E pollFirst();
    E getFirst();
    E peekFirst();
    
    // 后端操作
    void addLast(E e);
    boolean offerLast(E e);
    E removeLast();
    E pollLast();
    E getLast();
    E peekLast();
    
    // 栈操作
    void push(E e);    // = addFirst
    E pop();           // = removeFirst
}

八、Map 接口（键值映射）

特点：键唯一、值可重复

public interface Map<K,V> {
    // 基本操作
    int size();
    boolean isEmpty();
    boolean containsKey(Object key);
    boolean containsValue(Object value);
    V get(Object key);
    V put(K key, V value);
    V remove(Object key);
    
    // 批量操作
    void putAll(Map<? extends K, ? extends V> m);
    void clear();
    
    // 视图集合
    Set<K> keySet();
    Collection<V> values();
    Set<Map.Entry<K,V>> entrySet();
    
    // 嵌套接口
    interface Entry<K,V> {
        K getKey();
        V getValue();
        V setValue(V value);
        // JDK8+ 比较方法
    }
    
    // JDK8+ 默认方法
    default V getOrDefault(Object key, V defaultValue) { /* ... */ }
    default void forEach(BiConsumer<? super K, ? super V> action) { /* ... */ }
    default V putIfAbsent(K key, V value) { /* ... */ }
    default boolean remove(Object key, Object value) { /* ... */ }
    default V compute(K key, BiFunction<? super K, ? super V, ? extends V> remapping) { /* ... */ }
}

九、SortedSet 接口（有序集合）

特点：元素自动排序

public interface SortedSet<E> extends Set<E> {
    // 范围视图
    SortedSet<E> subSet(E fromElement, E toElement);
    SortedSet<E> headSet(E toElement);
    SortedSet<E> tailSet(E fromElement);
    
    // 端点访问
    E first();
    E last();
    
    // 比较器
    Comparator<? super E> comparator();
}

十、SortedMap 接口（有序映射）

特点：键自动排序

public interface SortedMap<K,V> extends Map<K,V> {
    // 范围视图
    SortedMap<K,V> subMap(K fromKey, K toKey);
    SortedMap<K,V> headMap(K toKey);
    SortedMap<K,V> tailMap(K fromKey);
    
    // 端点访问
    K firstKey();
    K lastKey();
    
    // 比较器
    Comparator<? super K> comparator();
}

十一、NavigableSet 接口（导航集合）

特点：扩展 SortedSet，支持导航方法

public interface NavigableSet<E> extends SortedSet<E> {
    // 导航方法
    E lower(E e);       // 小于e的最大元素
    E floor(E e);       // 小于等于e的最大元素
    E ceiling(E e);     // 大于等于e的最小元素
    E higher(E e);      // 大于e的最小元素
    
    // 获取并移除
    E pollFirst();      // 获取并移除第一个元素
    E pollLast();       // 获取并移除最后一个元素
    
    // 逆序迭代
    Iterator<E> descendingIterator();
    NavigableSet<E> descendingSet();
}

十二、NavigableMap 接口（导航映射）

特点：扩展 SortedMap，支持导航方法

public interface NavigableMap<K,V> extends SortedMap<K,V> {
    // 键导航
    Map.Entry<K,V> lowerEntry(K key);
    K lowerKey(K key);
    Map.Entry<K,V> floorEntry(K key);
    K floorKey(K key);
    Map.Entry<K,V> ceilingEntry(K key);
    K ceilingKey(K key);
    Map.Entry<K,V> higherEntry(K key);
    K higherKey(K key);
    
    // 获取并移除
    Map.Entry<K,V> pollFirstEntry();
    Map.Entry<K,V> pollLastEntry();
    
    // 逆序视图
    NavigableMap<K,V> descendingMap();
    NavigableSet<K> navigableKeySet();
    NavigableSet<K> descendingKeySet();
}

接口核心特性对比

关键设计原则

1. 接口分离原则：

   • 集合操作（Collection）与映射操作（Map）分离
   • 有序性（List）与唯一性（Set）分离
   • 基础操作与导航操作分离

2. 向后兼容：

   • 通过默认方法（JDK8+）增强接口而不破坏实现

   // JDK8 在Iterable中添加的默认方法
   default void forEach(Consumer<? super T> action)

3. 视图机制：

   • 通过keySet(), entrySet(), values()提供不同视图
   • subList(), subSet()提供部分集合视图

最佳实践

1. 面向接口编程：

   // 声明为接口类型
   List<String> names = new ArrayList<>();
   NavigableMap<Integer, String> scores = new TreeMap<>();

2. 接口选择原则：

   • 需要索引访问 → List
   • 需要元素唯一 → Set
   • 需要键值映射 → Map
   • 需要排序 → SortedSet/SortedMap
   • 需要导航 → NavigableSet/NavigableMap

3. 避免直接实现接口：

   // 不推荐
   class CustomList implements List<String> { ... }
   
   // 推荐：继承抽象类
   class CustomList extends AbstractList<String> { ... }

4. 使用不可变集合（JDK9+）：

   List<String> immutableList = List.of("A", "B", "C");
   Set<Integer> immutableSet = Set.of(1, 2, 3);
   Map<String, Integer> immutableMap = Map.of("A", 1, "B", 2);

重要注意事项

1. 契约一致性：

   • 实现类必须遵守接口定义的契约（如Set不允重复元素）
   • equals()和hashCode()方法需正确实现

2. 视图集合的时效性：

   Map<String, Integer> map = new HashMap<>();
   Set<String> keys = map.keySet();
   
   map.put("newKey", 10);
   System.out.println(keys.contains("newKey")); // true - 视图实时更新

3. 并发修改异常：

   List<String> list = new ArrayList<>(Arrays.asList("A", "B"));
   for (String s : list) {
       list.remove(s); // 抛出ConcurrentModificationException
   }

4. 接口演进：

   • JDK5：引入泛型
   • JDK8：添加流操作和默认方法
   • JDK9：添加工厂方法创建不可变集合

理解这些接口的设计原理和相互关系，是掌握Java集合框架的基础。正确选择和使用接口，可以编写出更灵活、可维护性更高的代码。

List<String> list = List.of("A", "B", "C");

// 标准 Lambda
list.forEach(s -> System.out.println(s));

// 方法引用（推荐）
list.forEach(System.out::println);

A  
B  
C  

List<Integer> nums = new ArrayList<>(List.of(1, 2, 3));
Iterator<Integer> it = nums.iterator();

while (it.hasNext()) {
    int num = it.next();
    if (num % 2 == 0) {
        it.remove(); // 安全删除当前元素
    }
}
System.out.println(nums); // [1, 3]

Iterator<String> it = List.of("X", "Y", "Z").iterator();

// 剩余元素全部消费
it.forEachRemaining(System.out::println); 

X  
Y  
Z  

List<String> colors = List.of("Red", "Green", "Blue");

for (String color : colors) {
    System.out.print(color + " "); 
}
// 输出：Red Green Blue

List<Integer> numbers = new ArrayList<>(List.of(10, 20, 30, 40));

// 删除所有大于25的元素
numbers.removeIf(n -> n > 25); 
System.out.println(numbers); // [10, 20]

Predicate<String> lengthGt3 = s -> s.length() > 3;
List<String> words = new ArrayList<>(List.of("Java", "C++", "Python"));

words.removeIf(lengthGt3.negate()); // 保留长度>3的单词
System.out.println(words); // [Java, Python]

List<String> data = List.of("apple", "banana", "cherry", "date");

// 过滤 + 转换 + 收集
List<String> result = data.stream()
    .filter(s -> s.length() > 5)     // 长度>5
    .map(String::toUpperCase)        // 转大写
    .toList();                       // 收集为不可修改列表

System.out.println(result); // [BANANA, CHERRY]

// 统计计算
long count = data.stream().filter(s -> s.contains("a")).count();
System.out.println(count); // 4

// 并行流加速
int sum = data.parallelStream()
    .mapToInt(String::length)
    .sum();
System.out.println(sum); // 20 (5+6+6+4)

List、Set、Queue 常用实现类详解

一、List 实现类

1. ArrayList

底层原理：

• 基于动态数组实现（Object[] elementData）
• 初始容量：10（默认）
• 扩容机制：新容量 = 旧容量 × 1.5（int newCapacity = oldCapacity + (oldCapacity >> 1)）
• JDK8+ 优化：延迟初始化存储数组（首次add时创建）

使用示例：

List<String> list = new ArrayList<>(100); // 预分配容量
list.add("Java");
list.add(0, "Python"); // 指定位置插入
String item = list.get(1); // 随机访问
list.remove(0); // 删除元素（后续元素前移）

注意点：

1. 随机访问快：O(1) 时间复杂度

2. 插入/删除慢：

   • 尾部操作：O(1)
   • 中间操作：O(n)（需要移动元素）

3. 线程不安全：多线程环境需同步

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

4. 快速失败机制：迭代中修改集合会抛ConcurrentModificationException

2. LinkedList

底层原理：

• 基于双向链表实现（Node 节点）

• 节点结构：

  private static class Node<E> {
      E item;
      Node<E> next;
      Node<E> prev;
  }

使用示例：

LinkedList<String> list = new LinkedList<>();
list.addFirst("Head"); // 头部插入
list.addLast("Tail");  // 尾部插入
String first = list.pollFirst(); // 移除并返回头部
list.forEach(System.out::println); // 顺序遍历

注意点：

1. 插入删除快：O(1)（已知位置时）
2. 随机访问慢：O(n)（需要遍历链表）
3. 内存开销大：每个元素消耗额外空间存储指针
4. 最佳实践：
   • 频繁在首尾增删时使用
   • 避免使用get(int index)进行随机访问

3. CopyOnWriteArrayList

底层原理：

• 写时复制技术
• 读操作：直接访问当前数组（不加锁）
• 写操作：复制新数组 → 修改 → 替换引用（加锁）

使用场景：

CopyOnWriteArrayList<String> safeList = new CopyOnWriteArrayList<>();
// 读线程（无需同步）
safeList.forEach(System.out::println); 

// 写线程（线程安全）
safeList.add("new element");

注意点：

1. 读多写少：写操作成本高（复制整个数组）
2. 数据弱一致性：迭代器访问的是创建时的快照
3. 内存消耗：写操作可能导致内存占用翻倍
4. 适用场景：监听器列表、配置信息等低频修改场景