Java 集合框架核心篇：Vector、BitSet、Stack、Hashtable 與枚舉器深度解析

前言：早期集合類的歷史與現狀

Java 1.0/1.1 提供的集合類雖然已被 Java 2 Collections Framework（List/Set/Map 接口體系）取代，但在存量代碼、面試考察、理解演進歷史方面仍具重要價值。本文深度解析 Vector、BitSet、Stack、Hashtable/Dictionary 及 Enumeration 的原理、源碼陷阱與現代替代方案。

一、Vector：同步的動態數組

核心特性

• 實現 List 接口，底層 Object[] elementData，容量自動增長（默認 2 倍）。
• 所有公共方法同步（synchronized），線程安全但性能較差。
• 保留歷史方法：addElement()、elementAt()、elements() 返回 Enumeration。

toString() 遞歸陷阱實戰

public class CrashJava {
    public String toString() {
        return "CrashJava address: " + this + "\n"; // this 觸發 toString 遞歸
    }
    public static void main(String[] args) {
        Vector v = new Vector();
        for (int i = 0; i < 10; i++) v.addElement(new CrashJava());
        System.out.println(v); // Vector.toString() 遍歷調用元素 toString() → StackOverflowError
    }
}

根因："str" + this 隱式調用 String.valueOf(this) → this.toString() 形成無限遞歸。

修正：super.toString() 獲取 ClassName@hashCode，或顯式 Integer.toHexString(hashCode())。

現代替代

• 單線程：ArrayList（非同步、擴容 1.5 倍）。
• 多線程：Collections.synchronizedList(new ArrayList()) 或 CopyOnWriteArrayList（讀多寫少）。

二、BitSet：位級壓縮存儲

核心特性

• 邏輯上是「無限長位向量」，物理上按 long[] words 存儲（每 64 位一塊）。
• 適合海量布爾標誌（如布隆過濾器基礎、稀疏集合、狀態壓縮 DP）。
• 最小分配 64 位，小規模數據（<64 位）不如 int/long 位運算高效。

關鍵操作

BitSet bs = new BitSet();
bs.set(100);           // 置 1
bs.clear(100);         // 置 0
bs.get(100);           // 讀取
bs.flip(100);          // 取反
bs.cardinality();      // 統計 1 的個數
bs.and(other);         // 位與（原地修改）
bs.or(other);          // 位或
bs.xor(other);         // 位異或
bs.andNot(other);      // 位與非

Java 1.0 擴容 Bug 歷史

早期版本 set(index) 若 index > 當前容量*2 會拋出 ArrayIndexOutOfBoundsException，需先 set(中間索引) 觸發擴容。Java 1.1 已修復，現代版本自動無縫擴容。

三、Stack：繼承 Vector 的 LIFO 結構

設計缺陷

• 繼承而非組合：Stack extends Vector 違反「組合優於繼承」原則，暴露 addElement()、elementAt() 等非棧語義方法。
• 同步開銷同 Vector。

核心 API

Stack<String> st = new Stack<>();
st.push("A"); st.push("B"); st.push("C");
st.peek();   // "C" 不移除
st.pop();    // "C" 移除
st.empty();  // false
st.search("A"); // 從頂部算起的 1-based 索引，返回 3

現代替代

• Deque 接口：ArrayDeque（非同步、雙端、性能最優）、LinkedList（同樣實現 Deque）。
• 官方文檔明確推薦：Deque<E> stack = new ArrayDeque<>();

四、Hashtable / Dictionary：同步的鍵值映射

Dictionary 抽象類

• 純抽象，定義 put/get/remove/size/isEmpty/keys/elements。
• 僅有 Hashtable 一個 JDK 實現。

Hashtable 核心機制

• 底層 Entry<K,V>[] table 數組 + 鏈表解決衝突（Java 7 以前無樹化）。
• 全方法 synchronized，線程安全但並發度低。
• 鍵值均不允許 null（HashMap 允許一個 null key、多個 null value）。
• 默認容量 11，負載因子 0.75，擴容 2*old+1（質數策略）。
• Enumeration<K> keys()、Enumeration<V> elements() 返回枚舉器。

Hashtable<Integer, Counter> ht = new Hashtable<>();
for (int i = 0; i < 10000; i++) {
    Integer r = (int)(Math.random() * 20);
    ht.computeIfAbsent(r, k -> new Counter()).increment();
}
System.out.println(ht); // {19=489, 18=510, ...}

class Groundhog {
    int id;
    Groundhog(int n) { id = n; }
    // 錯誤：繼承 Object 默認 hashCode=地址，equals=地址比較
    // 導致 new Groundhog(3) 無法命中 ht.put(new Groundhog(3), ...)
}

class Groundhog2 {
    int id;
    Groundhog2(int n) { id = n; }
    @Override public int hashCode() { return id; }
    @Override public boolean equals(Object o) {
        return o instanceof Groundhog2 && id == ((Groundhog2)o).id;
    }
}

public interface Enumeration<E> {
    boolean hasMoreElements();
    E nextElement();
}

static void print(Enumeration<?> e) {
    while (e.hasMoreElements()) 
        System.out.println(e.nextElement().toString());
}

// 同一打印邏輯複用 Vector、Hashtable、自定義集合
Vector<Mouse> vm = ...;
Hashtable<Integer, Hamster> hm = ...;
print(vm.elements());
print(hm.elements());