Containers and Generic⚓︎

Array⚓︎

• 数组是一种特殊类型对象，能够存储固定数量的元素

• 数组应当通过 new 在堆上动态分配或聚合初始化(aggregate initialization) 被创建

  int[] a = new int[10];
  int a[] = new int[10];
  int[] a = {1, 2, 3, 4};
  

• 数组内所有元素类型相同

• 数组是一个对象

  hourCounts = new int[24];
  

  

• 所有数组都有一个内部成员属性 length，表示数组大小

• 合法下标值(valid subscript value)

  • 编译器会检查是否用的是合法下标值，无论用于右值还是左值
  • 一旦程序运行过程中存在非法下标，就可能会出现数据或代码遭破坏，或程序中止 (abort) 的情况
  • 所以 Java 有责任确保程序在运行时只使用合法下标值
  • 关键概念：通过边界检查确保索引用于指代范围内的数组元素

• for-each 语法：

  for ( <type> <variable>: <array> ) {
      // variable...
  }
  

  例子

  public class ArrayLength {
      public static void main(String[] args) {
          int[] a = new int[(int)(Math.random() * 10)];
          for ( int i = 0; i < a.length; ++i )
              a[i] = (int)(Math.random() * 100);
          for ( int val : a )
              System.out.println(val);
          }
  }
  

• 数组变量

  • 是指向数组对象的指针
  • 所以 Java 允许数组间的赋值
  
  例子

  public class ArrayAssignment {
      public static void main(String[] args) {
          int[] a1 = {1, 2, 3, 4, 5};
          int[] a2 = a1;
          for ( int i = 0; i < a2.length; ++i )
              a2[i]++;
          for ( int v : a1 )
              System.out.println(v);
      }
  }
  

• 对象数组

  • 数组可以将对象的引用(references to objects)（句柄 (handle)）作为元素存储

  • 注意：实例化一个对象数组仅预留了存储引用的空间，所以必须要单独实例化每个元素中要存储的对象，比如以下声明：

    String[] words = new String[5];
    

  • 对象数组中的 for-each

    class Value {
        int i;
    }
    
    Value[] a = new Value[5];
    for ( int i = 0; i < a.length; i++ )
        a[i] = i;
    for ( var x: a )
        x.i++;
    for ( var x: a )
        System.out.println(x.i);
    

    • var 可自动推断类型（和 C++ 的 auto 类似）

Collections⚓︎

容器对象(collection object) 是指能存储任意数量的其他对象的对象。常用的容器对象包括：

• List：以特定顺序存储元素
• Set：不允许有重复元素
• Map：一组“键 - 值”对象对

容器类是泛型类(generic class)。

private ArrayList<String> notes;

要定义一个容器类的变量，我们需要指定两种类型：

• 集合本身的类型（此处为 ArrayList）
• 存储在集合中的元素类型（此处为 String）

由于 Java 有类型推断功能，所以无需在 new 中重复表述元素类型：

import java.util.ArrayList;
public class Notebook {
    private ArrayList<String> notes = new ArrayList();
}

相应的对象结构如下：

Iteration⚓︎

在容器对象上迭代：

• 索引

  for ( int i = 0; i < lst.size(); i++ ) {
      s += lst.get(i);
  }
  

• for-each

  for ( var x : lst ) {
      s += x;
  }
  
  public voidlistNotes() {
      for (String note : notes) {
          System.out.println(note);
      }
  }
  

• 迭代器(iterator)

  public void listNotes() {
      Iterator<String> it = notes.iterator();
      while (it.hasNext()) {
          System.out.println(it.next());
      }
  }
  

  • 迭代器是一种对象，它提供了遍历容器对象中所有元素的功能
  • 此时客户端程序员无需了解或关心该被迭代序列的底层结构
  • 迭代器的工作流程：
    1. 通过调用名为 iterator() 的方法，向容器请求一个迭代器；这个迭代器将在首次调用其 next() 方法时，准备好返回序列中的第一个元素
    2. 使用 next() 获取序列中的下一个对象
    3. 要想检查序列中是否还有更多对象，使用 hasNext() 方法
    4. 利用 remove() 移除迭代器最后返回的元素

Implementation⚓︎

容器实现：实现集合接口的类通常以 <Implementation-style><Interface> 的形式命名。下表总结了常见容器的实现：

容器相关术语

Utilities⚓︎

Collections 类的静态成员：

• min(Collection)，max(Collection)
• reverse()
• copy(List dest, List src)
• fill(List list, Object o)

Lists⚓︎

常用的 List 容器有：

• List（接口）：以特定顺序维护元素
• ArrayList：使用数组实现，插入和删除偏慢
• LinkedList：插入和删除成本低，但随机访问慢

Collection
├─ List <- 有序、可重复、带索引
│ ├─ ArrayList
│ ├─ LinkedList <- 同时也实现了 Deque
│ └─ Vector
│     └─ Stack <- Vector 的子类（古老、同步、官方不推荐）
├─Queue <- 一端进、一端出，典型 FIFO
│  ├─ Deque <- 双端队列，两头都能进出
│  │   ├─ ArrayDeque <- 数组实现，非同步，最快
│  │   └─ LinkedList <- 链表实现，也能当 List 用
│  │
│  ├─ PriorityQueue <- 按优先级出队，不是 FIFO
│  └─ ConcurrentLinkedQueue...（并发包里的实现）

ArrayList⚓︎

官方文档：https://docs.oracle.com/javase/8/docs/api/java/util/ArrayList.html

下面罗列 ArrayList 常用的 API：

• 添加

  boolean add(E e)
  void add(int index, E element)
  boolean addAll(Collection<? extends E> c)
  boolean addAll(int index, Collection<? extends E> c)
  

• 删除

  E remove(int index)
  boolean remove(Object o)
  boolean removeAll(Collection<?> c)
  boolean removeIf(Predicate<? super E> filter)
  protected void removeRange(int fromIndex, int toIndex)
  void clear()
  boolean retainAll(Collection<?> c)
  

• 修改

  E set(int index, E element)
  void replaceAll(UnaryOperator<E> operator)
  

• 查找

  E get(int index)
  int indexOf(Object o)
  int lastIndexOf(Object o)
  boolean contains(Object o)
  boolean containsAll(Collection<?> c)
  

• 信息

  boolean isEmpty()
  int size()
  

• 容量

  void ensureCapacity(int minCapacity)
  void trimToSize()
  

• 生成

  Object[] toArray()
  <T> T[] toArray(T[] a)
  Object clone()
  void sort(Comparator<? super E> c)
  List<E> subList(int fromIndex, int toIndex)
  

• 迭代

  Iterator<E> iterator()
  ListIterator<E> listIterator()
  ListIterator<E> listIterator(int index)
  

• 流

  Stream<E> stream()
  Stream<E> parallelStream()
  void forEach(Consumer<? super E> action)
  

Sets⚓︎

常用的 Set 容器有：

• Set（接口）：加入 Set 的所有元素都是唯一的
• HashSet：对象必须定义 hashCode()
• TreeSet：由树结构支持的有序集合

import java.util.HashSet;
import java.util.Iterator;
//...
HashSet<String> mySet = new HashSet<String>();
mySet.add("one");
mySet.add("two");
mySet.add("three");
Iterator<String> it = mySet.iterator();
while(it.hasNext()) {
    //call it.next() to get the next object
    //do something with that object
}

如何选择合适的 Sets？

• 日常去重：HashSet
• 去重 + 插入顺序：LinkedHashSet
• 去重 + 排序 / 区间：TreeSet（单线程）或 ConcurrentSkipListSet（并发）
• 并发去重：首选 ConcurrentHashMap.newKeySet()（JDK8 + 工厂方法），或 ConcurrentSkipListSet
• 读多写少且集合小：CopyOnWriteArraySet
• enum 专用：EnumSet.allOf(MyEnum.class)

如果要将用户自定义对象放入 Set 中，需注意：

• 必须

  • 正确覆写 equals()，包括以下约定（Object 规范节选）：

    • 自反：x.equals(x) 必须 true
    • 对称：x.equals(y) <=> y.equals(x)
    • 传递：x.equals(y) && y.equals(z) => x.equals(z)
    • 一致：多次调用结果不变
    • 与 null 比较必须返回 false
    实现模板（字段比较 + null安全）

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (!(o instanceof MyKey)) return false;
        MyKey other = (MyKey) o;
        return Objects.equals(this.name, other.name) && this.age == other.age;
    }
    

  • 一致地覆写 hashCode()

    • 规则：相等对象必须返回相同哈希值，不相等对象尽量分散
    • 一旦对象进入 HashSet ，不要修改参与hash / equals的字段，否则“内存泄漏”式丢失对象
    实现模板

    @Override
    public int hashCode() {
        return Objects.hash(name, age);  // 内部调用 Arrays.hashCode
    }
    

• 可选（若想让TreeSet / ConcurrentSkipListSet能排序，以下两者二选一即可）

  • 实现 Comparable<T>

    class MyKey implements Comparable<MyKey> {
        public int compareTo(MyKey o) {
            int c = this.name.compareTo(o.name);
            return (c != 0) ? c : Integer.compare(this.age, o.age);
        }
    }
    

  • 提供外部 Comparator

    Set<MyKey> set = new TreeSet<>(
        Comparator.comparing(MyKey::getName)
            .thenComparingInt(MyKey::getAge));
    

public final class MyKey implements Comparable<MyKey> {
    private final String name; // 参与 hash/equals/compare
    private final int age;

    public MyKey(String name, int age) {
        this.name = name;
        this.age = age;
    }

    @Override
    public boolean equals(Object o) { /* 见上 */ }

    @Override
    public int hashCode() { /* 见上 */ }

    @Override
    public int compareTo(MyKey o) { /* 见上 */ }
    }

Maps⚓︎

常用的 Map 容器有（和 Set 类似）：

• Map（接口）
• HashMap
• TreeMap

HashMap <String, String> phoneBook = new HashMap<String, String>();
phoneBook.put("Charles Nguyen", "(531) 9392 4587");
phoneBook.put("Lisa Jones", "(402) 4536 4674");
phoneBook.put("William H. Smith", "(998) 5488 0123");
String phoneNumber = phoneBook.get("Lisa Jones");
System.out.println(phoneNumber);

哈希 (hashing) 和哈希码 (hash code)：

• 键需要有 hashCode() 方法
• 要想将用户自定义类作为 HashMap 的键，必须覆写 equals() 和 hashCode()

Generic⚓︎

关于泛型(generic)：

• 泛型提供了一种向编译器传递容器类型信息的方式，以便进行类型检查
• 除了枚举、匿名内部类和 Exception 类之外，所有类型都可以拥有泛型参数

泛型类(generic class) 必须指定两种类型：集合本身的类型（此处为 ArrayList），以及存储在集合中的元素类型（此处为 String）。

private ArrayList<String> notes;

将类型作为参数：

class Pair<T> {
    T first;
    T second;
}

• T 是占位符，生成对象时传具体类型
• 实际上 Java 常用占位符为 E 而非 T（E 代表 element）

多类型参数：类型参数数量不限制，按位置对应

class Triple<A, B, C> { }
Triple<String, Integer, Double> t = new Triple<>("Hi", 42, 3.14);

接口可能也会用到泛型类型：

interface Codec<T> {
    T decode(String s);
}

enum IntCodec implements Codec<Integer> {
    INSTANCE;
    public Integer decode(String s) {
        return Integer.valueOf(s);
    }
}

定义一个简单的泛型类：

public interface List<E> {
    void add(E x);
    Iterator<E> iterator();
}

public interface Iterator<E> {
    E next();
    boolean hasNext();
}

泛型类里的静态方法：

• 方法前写 <T> ，编译器帮你推

public static <T> List<T> asList(T... a) {
    return Arrays.asList(a);
}

// 类型推断
List<String> names = asList("A", "B");

public final class Box<T> {
    private T value;
    public Box(T value) { this.value = value; }
    public T get() { return value; }
    public void set(T value){ this.value = value;}

    // 静态泛型工厂，方便创建
    public static <E> Box<E> of(E value) { return new Box<>(value); }

    public static void main(String[] args) {
        Box<String> sBox = Box.of("Hello");
        System.out.println(sBox.get()); // Hello
        Box<Integer> iBox = new Box<>(42);
        iBox.set(iBox.get() + 1);
        System.out.println(iBox.get()); // 43
    }
}

Java 的泛型方式：

• 代码没有多个副本
• 泛型类型声明一次性编译，并转换为一个单独的类文件
• 泛型声明有形式类型参数
• 为形式类型参数使用简洁（如果可能的话，单字符）且富有启发性的名称

泛型与子类型 (subtyping)：如果 Foo 是 Bar 的一个子类型（子类或子接口），而 G 是某种泛型类型声明，那么 G<Foo> 并不是 G<Bar> 的子类型。

List<String> ls = new ArrayList<String>();
List<Object> lo = ls;
lo.add(new Object());
String s = ls.get(0);

通配符(wildcard)：

void printCollection(Collection<?> c) {
    for (Object e : c) {
        System.out.println(e);
    }
}

Collection<?> c = new ArrayList<String>();
c.add(new Object());

例子

以下代码实现 Shape 类及其子类：

public abstract class Shape {
    public abstract void draw(Canvas c);
}

public class Circle extends Shape {
    private int x, y, radius;
    public void draw(Canvas c) { ... }
}

public class Rectangle extends Shape {
    private int x, y, width, height;
    public void draw(Canvas c) { ... }
}

// To draw them on a canvas
public void draw(Shape s) {
    s.draw(this);
}

public void drawAll(List<Shape> shapes) {
    for (Shape s: shapes) {
        s.draw(this);
    }
}

// Bounded wildcards
public void drawAll(List<? extends Shape> shapes) { ...}
double sum(List<? extends Number> nums) { /* 只读 */ }
void fill(List<? super Integer> ints) { /* 只写 */ }

List<? extends Integer> upper = new ArrayList<Integer>();
Integer i = upper.get(0);  // 读
upper.add(3);              // 编译失败，不知道具体是 Integer 的哪一级子类型

List<? super Integer> lower = new ArrayList<Number>();
lower.add(3);              // 写
Number n = lower.get(0);   // 读出只能是 Object/Number，丢失具体类型

运行时擦除：

• 泛型只存在于编译期
• 编译后擦除到 Object 或通配上限

class Pair<T> {
    T first;
    T second;
}

$ javap -c -v -p Pair

T first; // 字节码里 T 被擦成 Object
descriptor: Ljava/lang/Object;

对于：

class NumBox<T extends Number> { private T v; }

private java.lang.Number v; // 擦除到 Number，而非 Object

OpenJDK 24 的 javap -p -v （ 或 -c -v ）为了可读性 ，把擦除后的Object / Number又显示成原泛型符号 T，但 Signature 属性 Object 和字节码指令里仍然是 Object。

泛型不能做的事：

• new T()：擦除后无构造
• T.class：无具体类型信息
• List<int>：基本类型不能用

Stream⚓︎

ArrayList<Artist> artists = new ArrayList<>();

int cnt = 0;
for (Artist artist : artists) {
    if (artist.isFrom("London")) {
        cnt++;
    }
}
System.out.println(cnt);

long count = artists.stream()
                    .filter(artist -> artist.isFrom("London"))
                    .count();

System.out.println(count);

惰性方式 (lazy way)：

artists.stream()
       .filter(artist -> {
            System.out.println("Checking artist: " + artist.getName());
            return artist.isFrom("London");
       })
       .forEach(artist -> System.out.println("Artist from London: " + artist.getName()));

流的原语 (primitives)：

• 在 java.util.stream 包里，JDK 提供了 4 套专门用于基本类型的流类型，每套都带独立的静态工厂和专用中间 / 终端操作
• 它们全部实现 BaseStream 接口，与 Stream 并列，互不继承

• 没有FloatStream /CharStream / BooleanStream
  • float 被提升为 double，char / boolean用 IntStream 装

流的引用：Stream<T>，任意引用类型 T

Creating Stream⚓︎

• 来自 Collection

  来源	方法	流类型
  java.util.Collection	.stream()，.parallelStream()	Stream<T>
  java.util.Map	.entrySet().stream() ...	Stream<Map.Entry<K,V>>

• 来自数组

  来源	方法	流类型
  任意引用类型数组	Arrays.stream(T[])	Stream<T>
  基本类型数组	Arrays.stream(int[]) ...	IntStream / LongStream / DoubleStream
  指定区间	Arrays.stream(array, start, end)	同上

• 静态工厂方法

  类	方法
  Stream	Stream.of(T…)，Stream.ofNullable(T)
  Stream	Stream.empty()
  Stream	Stream.generate(Supplier<T>)
  Stream	Stream.iterate(T, UnaryOperator<T>)
  Stream	Stream.iterate(T, Predicate<T>, UnaryOperator<T>) （1.9+ 带终止条件）
  IntStream, LongStream, DoubleStream	IntStream.of(int…)，IntStream.range(1, 10)，IntStream.rangeClosed(1, 10)

• Stream 还可以从缓冲字符流（BufferedReader）、文件、正则表达式、随机数发生器、Optional 和并行工具产生

Common Lazy Operations⚓︎

• map 方法

  

  List<String> collected = Stream.of("a", "b", "hello")
                              .map(string -> string.toUpperCase())
                              .collect(toList());
  
  System.out.println(collected);
  

• filter 方法

  

  List<String> beginningWithNumbers
  = Stream.of("a", "1abc", "abc1")
          .filter(value -> Character.isDigit(value.charAt(0)))
          .collect(toList());
  
  System.out.println(beginningWithNumbers);
  

• flatMap 方法

  

  List<Integer> together = Stream.of(Arrays.asList(1, 2), asList(3, 4))
                                 .flatMap(numbers -> numbers.stream())
                                 .collect(toList());
  
  System.out.println(together);
  

Common Eager Operations⚓︎

• 迭代

  方法名	返回类型	说明
  forEach(Consumer)	void	遍历每个元素
  forEachOrdered(Consumer)	void	顺序遍历（适用于并行流）

  例子

  List<String> list = List.of("java", "python", "go");
  list.stream()                       // 拿到流
      .forEach(System.out::println);  // 终端操作：逐行打印
  
  AtomicInteger sum = new AtomicInteger(0);
  IntStream.rangeClosed(1, 5)         // 1 2 3 4 5
          .forEach(sum::addAndGet);  // 累加
  System.out.println(sum.get());     // 15
  
  List.of("a", "b", "c", "d")
      .parallelStream()
      .forEachOrdered(System.out::print);  // 保证按原顺序打印
  

• 收集

  方法名	返回类型	说明
  toArray()	Object[]	转为数组
  toArray(IntFunction<A[]>)	A[]	转为指定类型数组
  collect(Collector)	R	收集元素到集合或其他结构

  例子

  Set<String> origins = album.getMusicians()
                          .filter(artist -> artist.getName().startsWith("The"))
                          .map(artist -> artist.getNationality())
                          .collect(toSet());
  

• 归约：对于一个值集合，生成单一结果

  方法名	返回类型	说明
  reduce(...)	Optional<T> 或 T	归约操作
  min(Comparator)	Optional<T>	最小值
  max(Comparator)	Optional<T>	最大值
  count()	long	元素个数

  例子

  例 1 例 2

  ```java
  int count = Stream.of(1, 2, 3).reduce(0, (acc, element) -> acc + element);
  ```
  
  <div style="text-align: center">
      <img src="images/lec4/11.png" width=30%>
  </div>
  

  List<Track> tracks = asList(new Track("Bakai", 524),
      new Track("Violets for Your Furs", 378),
      new Track("Time Was", 451));
  
  Track shortestTrack = tracks.stream()
                              .min(Comparator.comparing(track -> track.getLength()))
                              .get();
  

• 短路 (short-circuiting)

  方法名	返回类型	说明
  anyMatch(Predicate<T>)	boolean	一旦找到匹配元素，立即返回 true
  allMatch(Predicate<T>)	boolean	一旦遇到不满足的元素，立即返回 false
  noneMatch(Predicate<T>)	boolean	一旦遇到满足的元素，立即返回 false
  findFirst()	Optional<T>	返回第一个元素，找到即停
  findAny()	Optional<T>	返回任意一个元素（并行流中可能更快）

  例子

  例 1 例 2（找素数）

  Stream.iterate(1, i -> i + 1)            // 无限流：1, 2, 3, ...
      .filter(i -> i > 100)
      .findFirst()                       // 短路操作，程序不会无限运行
      .ifPresent(System.out::println);   // 输出 101
  

  // 打印素数个数
  System.out.println(IntStream.range(2, x)
      .filter(i-> {
          System.out.println("Testing " + i);
          return x % i == 0;})
      .count());
  
  // 打印第一个素数
  System.out.println(IntStream.range(2, x)
      .filter(i-> {
          System.out.println("Testing " + i);
          return x % i == 0;})
      .findFirst());
  
  // 并行流
  System.out.println(IntStream.range(2, x)
      .parallel()
      .filter(i-> {
          System.out.println("Testing " + i);
          return x % i == 0;})
      .findAny());
  

Parallel Stream⚓︎

parallelStream() 把“串行流”换成“并行流”，底层开启多线程，对数据进行分片 -> 并行处理 -> 结果合并。

List<Integer> list = List.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);

// 并行求和
int sum = list.parallelStream()
            .mapToInt(Integer::intValue)
            .sum();
System.out.println(sum); // 55

何时使用并行流？

• 数据量小；线程切换开销：计算收益，可能更慢
• 数据量大 + 计算重：明显加速
• 需要顺序：并行后顺序混乱，需要 forEachOrdered 或 sorted 等额外操作
• 有状态 / 锁：容易出现竞态、性能骤降

List.of(1,2,3,4,5).parallelStream().forEach(System.out::print);
// 可能输出 34125，用 forEachOrdered(System.out::print) 或先 sorted()

List<Integer> bad = new ArrayList<>();
list.parallelStream().forEach(bad::add);    // 非线程安全，会丢数据
//用 collect(Collectors.toList()) 或线程安全容器

性能改善？

long t1 = System.nanoTime();
long a = LongStream.rangeClosed(1, 10_000_000).sum();             // 串行
long t2 = System.nanoTime();
long b = LongStream.rangeClosed(1, 10_000_000).parallel().sum();  // 并行
long t3 = System.nanoTime();
System.out.printf("串行: %d ms，并行: %d ms%n", (t2 - t1) / 10_000_000, (t3 - t2) / 10_000_000);

评论区