概述#

陣列（Array）與字串（String）的題目在面試中經常可以互換——用陣列描述的題目可能改用字串提問，反之亦然。本章聚焦於幾個核心的底層資料結構，理解它們對解題至關重要。

Hash Tables#

Hash Table 是一種將 key 對應到 value 的資料結構，支援高效率的查找。以下說明一種常見的實作方式：

插入流程#

使用一個 linked list 陣列搭配 hash code 函數，插入步驟如下：

1. 計算 hash code：通常為 int 或 long。注意，不同的 key 可能產生相同的 hash code（因為 key 的數量可以是無限的，但 int 的數量有限）。
2. 對應到陣列索引：例如 hash(key) % array_length。不同的 hash code 也可能對應到同一個索引。
3. 儲存至 linked list：在該索引位置存放 key-value 對。使用 linked list 是因為可能發生碰撞（collision）——兩個 key 有相同的 hash code，或不同的 hash code 對應到同一索引。

查找流程#

從 key 計算 hash code，再從 hash code 取得索引，最後在 linked list 中搜尋對應的 key。

時間複雜度#

• 碰撞極多時：最差為 O(N)，N 為 key 的數量
• 良好實作下（碰撞極少）：查找時間為 O(1)

另一種實作方式是使用平衡二元搜尋樹（balanced binary search tree），查找時間為 O(log N)。優點是佔用空間較小，且可以按順序遍歷所有 key。

ArrayList & Resizable Arrays#

在某些語言（如 Python）中，陣列會自動調整大小。但在 Java 中，陣列是固定長度的，建立時就需指定大小。

ArrayList 是一種在保持 O(1) 存取的前提下，能動態調整大小的陣列實作。當陣列滿了，容量會加倍。

ArrayList<String> merge(String[] words, String[] more) {
    ArrayList<String> sentence = new ArrayList<String>();
    for (String w : words) sentence.add(w);
    for (String w : more) sentence.add(w);
    return sentence;
}

為什麼攤銷插入時間是 O(1)？#

假設陣列大小為 N，往回推算每次擴容時需要複製的元素數：

最後一次擴容：複製 n/2 個元素
前一次擴容：  複製 n/4 個元素
再前一次：    複製 n/8 個元素
...
第二次擴容：  複製 2 個元素
第一次擴容：  複製 1 個元素

總共複製次數約為 n/2 + n/4 + n/8 + ... + 2 + 1，略小於 N。

這就像走一公里的路：先走 0.5 公里，再走 0.25 公里，再走 0.125 公里……你永遠不會超過一公里。

因此，插入 N 個元素的總工作量為 O(N)，每次插入的攤銷時間為 O(1)，即使某些單次插入需要 O(N)。

StringBuilder#

考慮以下字串串接的程式碼：

String joinWords(String[] words) {
    String sentence = "";
    for (String w : words) {
        sentence = sentence + w;
    }
    return sentence;
}

每次串接都會建立一個新的字串副本，逐字元複製。若有 n 個字串，每個長度為 x：

• 第 1 次迭代：複製 x 個字元
• 第 2 次迭代：複製 2x 個字元
• 第 3 次迭代：複製 3x 個字元

總時間為 O(x + 2x + 3x + … + nx) = O(x·n²)。

直接用 + 串接大量字串在效能上非常糟糕，因為 1 + 2 + ... + n = n(n+1)/2，即 O(n²)。

StringBuilder 透過建立一個可調整大小的陣列來儲存所有字串，只在最後需要時才將它們複製回一個字串：

String joinWords(String[] words) {
    StringBuilder sentence = new StringBuilder();
    for (String w : words) {
        sentence.append(w);
    }
    return sentence.toString();
}

練習自己實作 StringBuilder、HashTable 和 ArrayList，是鞏固字串、陣列與資料結構基礎的好方法。

面試題目列表#