您现在的位置：程式碼之家 >> 編程語言 > >> Java 程式設計 >> Java 綜合教學

《編寫高質量代碼》第 5 章精讀：ArrayList 子列表機制、排序策略與二分查找陷阱（建議 70-74）

編輯：Java 綜合教學

前言

《編寫高質量代碼：改善 Java 程序的 151 個建議》第 5 章聚焦數組與集合。建議 70-74 涵蓋 subList 視圖機制、局部列表高效處理、併發修改陷阱、Comparator 與 Comparable 排序策略選擇、binarySearch 適用場景五大核心知識點。本文結合 JDK 源碼與實戰案例深度解析。

建議 70：子列表只是原列表的一個視圖

核心結論

List.subList(from, to) 返回的不是新列表，而是原列表的動態視圖。視圖上的任何修改（add、remove、set）直接映射到原列表，且視圖大小隨原列表變化而變化。

源碼級證據

AbstractList.subList() 返回內部類 SubList（或 RandomAccessSubList），其核心字段：

private final AbstractList<E> l;  // 原始列表引用
private final int offset;          // 起始偏移量
private int size;                  // 視圖大小

關鍵方法實現：

public E get(int index) { return l.get(index + offset); }
public void add(int index, E element) { l.add(index + offset, element); /* 更新 size、modCount */ }
public E remove(int index) { E result = l.remove(index + offset); /* 更新 size、modCount */ return result; }

所有操作委託給原列表 l，故視圖與原列表數據始終一致。

對比 String.substring

String.substring() 創建新字符串（或共享 char[] 但不可變），修改不影響原字符串；subList 則是可變視圖，雙向同步。這是因為 List 設計為可變集合，視圖模式避免數據拷貝開銷。

建議 71：推薦使用 subList 處理局部列表

場景：刪除索引 20-30 的元素

傳統循環刪除易出錯（索引偏移），且代碼冗長。利用視圖特性，一行代碼搞定：

list.subList(20, 30).clear();

clear() 內部調用 removeRange(0, size())，最終委託原列表批量刪除，效率高且線程安全（單線程下）。

建議 72：生成子列表後不要再操作原列表

併發修改異常根因

SubList 構造時記錄 expectedModCount = l.modCount。每次視圖操作前調用 checkForComodification() 比對：

if (modCount != l.modCount) throw new ConcurrentModificationException();

若生成視圖後修改原列表，l.modCount 增加，導致視圖後續操作（甚至 size()）拋出 CME。此機制為快速失效，非真正併發檢測。

解決方案

只讀原列表： list = Collections.unmodifiableList(list); 生成視圖後凍結原列表。
拷貝而非視圖： new ArrayList<>(list.subList(from, to)) 產生獨立快照。
單視圖原則： 同一原列表同時存在多個視圖時，任一視圖修改均導致其他視圖失效。

建議 73：使用 Comparator 進行排序——策略模式的經典應用

Comparable vs Comparator

維度	Comparable (內部比較器)	Comparator (外部比較器)
定義位置	實體類內部 `compareTo`	獨立類實現 `compare`
數量限制	一個類僅有一種自然序	可定義無限種排序策略
耦合度	侵入式，修改實體類	非侵入式，符合開閉原則
適用場景	默認/通用排序（如 ID、時間）	業務多維度排序（按部門、薪資、績效）

多鍵排序實戰

先按職位降序，職位相同再按工號升序：

// Employee 實現 Comparable（自然序：按 ID 升序）
@Override public int compareTo(Employee o) {
    return CompareToBuilder.reflectionCompare(this, o, "id");
}

// 外部比較器：職位降序 + ID 升序
class PositionComparator implements Comparator<Employee> {
    @Override public int compare(Employee o1, Employee o2) {
        int posCmp = o2.getPosition().compareTo(o1.getPosition()); // 降序
        return (posCmp != 0) ? posCmp : Integer.compare(o1.getId(), o2.getId());
    }
}

// 使用
Collections.sort(list, new PositionComparator());
// 或臨時倒序
Collections.sort(list, Collections.reverseOrder(new PositionComparator()));

Apache Commons Lang 加持

CompareToBuilder 鏈式調用自動處理空值、多字段排序，代碼更簡潔健壯。

建議 74：不推薦直接對無序列表使用 binarySearch

前提條件：數據必須有序

Collections.binarySearch 基於二分查找，要求列表按自然順序升序排列（或提供一致的 Comparator）。無序列表調用結果不可預期。

案例：查找「廣州」

List<String> cities = Arrays.asList("上海", "廣州", "廣州", "北京", "天津");
// 無序調用
Collections.binarySearch(cities, "廣州"); // 返回 2（中間元素），而非首次出現的 1
// 排序後調用
Collections.sort(cities); // [北京, 廣州, 廣州, 上海, 天津]
Collections.binarySearch(cities, "廣州"); // 返回 1 或 2（任一匹配位置）

性能權衡

indexOf：O(n) 線性掃描，無序列表適用，查找首次出現位置。
binarySearch：O(log n) 對數級，前提是已排序。大數據量（>5000）且頻繁查找時優勢明顯。
工程建議：若列表原本無序且不可排序（業務順序有意義），堅決用 indexOf 或 Stream API；若可接受排序副本，new ArrayList<>(list).sort(...) 後再二分查找。

總結

建議 70-74 揭示了 Java 集合框架的核心設計哲學：視圖而非拷貝（subList）、策略模式解耦排序邏輯（Comparator）、算法前提條件不可忽視（binarySearch 需有序）。實戰中請牢記：生成視圖後凍結原列表、優先用外部比較器擴展排序、無序查找誠用 indexOf。