1. 從鏈表到容器為什么這章是所有算法課的基石如果你翻過《算法第4版》Algorithms_4th大概率會和我一樣在第一章就被三種最基礎(chǔ)的抽象數(shù)據(jù)類型ADT卡住過——Bags背包、Queues隊列、Stacks棧。表面上它們只是三種裝東西的盒子但如果你把整本書往后翻會發(fā)現(xiàn)后面所有的高級結(jié)構(gòu)樹、圖、哈希表、排序算法、最短路徑……幾乎每一個都在這三種容器之上做文章。這一章不是熱身而是整本教材真正的起跑線。這一章解決的核心問題很樸素在Java里寫算法時我們怎么存儲、怎么訪問數(shù)據(jù)數(shù)組可以嗎可以但數(shù)組的長度固定、插入刪除麻煩而且一旦涉及泛型就有各種類型擦除的坑。鏈表呢鏈表靈活但手動管理指針容易出錯。于是這章給出了三個標準答案——Bag、Queue、Stack用它們各自的訪問順序規(guī)則覆蓋算法中最常見的幾種數(shù)據(jù)訪問模式先進先出、后進先出、只收集不回頭。適合誰來讀說實話不只是正在啃這本書的學生。哪怕你是工作兩三年的開發(fā)者如果你發(fā)現(xiàn)自己在寫代碼時經(jīng)常糾結(jié)到底是拿數(shù)組還是拿鏈表、這個隊列到底該用LinkedList還是ArrayDeque那你在這章里會找到一套特別清晰的判斷依據(jù)。我當年是工作后回頭補算法基礎(chǔ)才讀的這章讀完之后最大的感受是以前寫業(yè)務(wù)代碼靠感覺選容器現(xiàn)在有了一整套理論支撐。這章的原理解釋非常教科書但正因為教科書很多細節(jié)都是暗線。我會把這章拆成兩條線來講一條是設(shè)計思路解釋為什么這章要把三種容器放在一起講另一條是實現(xiàn)細節(jié)把教科書里點到為止的鏈表實現(xiàn)、動態(tài)數(shù)組擴容、迭代器設(shè)計這些坑都給填上。在動手過一遍源碼之后你會發(fā)現(xiàn)這一章的量其實很足足夠你消化一陣子的。2. 三種容器設(shè)計思路拆解訪問順序決定一切2.1 為什么是包、隊列、棧三兄弟一起講在講解實現(xiàn)之前我想先聊聊一個很多人忽略的問題為什么這三種容器要放在同一節(jié)里它們的用途差異其實非常大但存在一個共同的數(shù)學結(jié)構(gòu)——它們都是集合都支持兩個最基本的操作插入insert和刪除delete。區(qū)別只有一個刪除哪一個。Bag只插入不刪除或者說不關(guān)心刪除順序。Queue刪除最先進來的那一個FIFOFirst-In-First-Out。Stack刪除最近進來的那一個LIFOLast-In-First-Out。你看僅僅一個刪除策略的差異就讓三個容器走上了完全不同的道路。這就好比餐廳的出餐口你排隊點單先來的先做這是隊列你往書包里塞書最后塞進去的反而最容易抽出來這是棧你把一堆物品丟進一個袋子之后想拿哪個拿哪個這是背包。教材把這三種容器放在一起是想讓你建立一種抽象思維底層數(shù)據(jù)結(jié)構(gòu)鏈表或數(shù)組是通用的但通過不同的接口暴露就變成了行為完全不同的容器。這也是面向?qū)ο笤O(shè)計里封裝和接口隔離最經(jīng)典的教學案例。后面你寫代碼時如果需要一個只進不出的緩沖區(qū)不該用List而應該用Bag如果需要處理嵌套結(jié)構(gòu)優(yōu)先想到Stack如果需要處理公平調(diào)度優(yōu)先想到Queue。2.2 數(shù)組實現(xiàn) vs 鏈表實現(xiàn)的核心取舍教科書在實現(xiàn)這三種容器時用了兩種底層物理結(jié)構(gòu)數(shù)組Array和鏈表Linked List。這是算法生涯里第一個重要的二選一我建議你從這章開始就建立一套自己的判斷體系。數(shù)組實現(xiàn)的優(yōu)勢是內(nèi)存連續(xù)索引訪問O(1)CPU緩存友好。劣勢是插入和刪除非尾部是O(n)且擴容時需要整體搬運。鏈表實現(xiàn)的優(yōu)勢是插入和刪除已知前驅(qū)節(jié)點時是O(1)無需連續(xù)內(nèi)存擴容零成本。劣勢是隨機訪問O(n)且每個節(jié)點要額外存儲下一個節(jié)點的指針內(nèi)存占用更高。一個很關(guān)鍵的點教材里沒有明說但實現(xiàn)里隱含了用數(shù)組實現(xiàn)棧是最優(yōu)解用鏈表實現(xiàn)棧和隊列是最符合直覺的解用鏈表實現(xiàn)Bag是最省事的解。為什么因為棧的插入和刪除都發(fā)生在同一端棧頂數(shù)組的尾部操作就是O(1)配合動態(tài)擴容均攤成本也很低而隊列需要在兩端操作數(shù)組在頭部刪除是O(n)除非用環(huán)形數(shù)組鏈表則天然適合。這些結(jié)論我建議你親手寫一遍實現(xiàn)才會有體感。2.3 泛型和迭代器這章里的隱形主角如果你只是粗讀一遍很容易把泛型Generics和迭代器Iterator當成Java的附屬語法略過。但實際上這一章是整本書第一次系統(tǒng)性使用泛型和迭代器的地方也是大多數(shù)初學者第一次在這里被編譯錯誤勸退的地方。先說泛型。為什么容器必須用泛型因為如果容器只能存Object你取出來就得強轉(zhuǎn)強轉(zhuǎn)就容易ClassCastException而且代碼里全是臟兮兮的強制轉(zhuǎn)換。用了泛型容器在編譯期就能保證類型安全。但Java的泛型是類型擦除實現(xiàn)的這里有一個特別容易踩的坑你不能直接創(chuàng)建泛型數(shù)組。例如T[] items new T[10]是無法編譯的。教材里的解法是創(chuàng)建Object數(shù)組然后強轉(zhuǎn)T[] items (T[]) new Object[10]。這個寫法會有個編譯警告但確實是通用解法。你千萬別試圖用new T[10]那是過不了的。再說迭代器。為什么容器要實現(xiàn)Iterable接口因為Java的for (String s : stack)語法糖本質(zhì)上調(diào)用的就是容器的iterator()方法。這個設(shè)計把遍歷邏輯從容器中解耦出來你可以為同一個容器實現(xiàn)多個不同的迭代器比如正序遍歷、反序遍歷。教材里通過內(nèi)部類實現(xiàn)迭代器并且強調(diào)了一個重要的設(shè)計原則迭代器應該是一個快照或者說它維護的是當前遍歷的狀態(tài)但容器本身不知道迭代器的存在。有一個細節(jié)值得注意迭代器里的remove()方法教材里直接拋了UnsupportedOperationException這是有意為之。因為很多數(shù)據(jù)結(jié)構(gòu)比如Bag壓根不支持刪除與其讓迭代器提供無用操作不如直接禁用。這個設(shè)計思路后來在Java標準庫中被廣泛采納。3. 核心實現(xiàn)細節(jié)與實操要點3.1 鏈表的節(jié)點設(shè)計內(nèi)部類 vs 靜態(tài)內(nèi)部類實現(xiàn)鏈表容器時第一個要決定的事就是節(jié)點類怎么寫。教材里用了非靜態(tài)內(nèi)部類private class Node我見過不少讀者照著敲代碼也能跑通但不清楚為什么不用靜態(tài)內(nèi)部類。非靜態(tài)內(nèi)部類有個隱藏特性每個實例都持有外部類實例的引用。也就是說每個Node節(jié)點都認識它所屬的容器。這在鏈表容器里不是必需的反而會帶來兩個問題一是內(nèi)存多占一個引用字段二是可能造成外部類無法被GC回收如果Node被錯誤地泄露出去。但如果改成靜態(tài)內(nèi)部類private static class Node就沒有這個問題。你可能想問那為什么教材要用非靜態(tài)的因為教學代碼追求的是讀起來簡單。對一個學習者來說Node直接訪問外部類的成員變量是直觀的但實際上靜態(tài)內(nèi)部類也能做到通過參數(shù)傳遞。我的建議是如果你在寫自己的庫用靜態(tài)內(nèi)部類如果你在照著教材學習可以先用非靜態(tài)的理解之后改成靜態(tài)的體會一下差異。這里還有一個細節(jié)節(jié)點類里存的item和next字段在教材里沒有加final。但如果你認真考慮過會意識到next其實在節(jié)點生命周期內(nèi)最多改變一次甚至不改變所以用final修飾next在邏輯上更嚴謹。有些同學喜歡寫防御性代碼這個習慣在算法學習中越早養(yǎng)成越好。3.2 動態(tài)數(shù)組擴容與縮容均攤分析的藝術(shù)數(shù)組實現(xiàn)棧的核心難點不在壓棧和彈棧本身——那就是賦值和指針移動——而在數(shù)組的擴容和縮容策略。這里有兩個經(jīng)典問題什么時候擴容什么時候縮容教材給出的答案是插入時如果數(shù)組滿了擴容為原來的2倍彈出時如果元素個數(shù)只有數(shù)組長度的1/4縮容為原來的一半。這個2倍擴、四分之一縮的設(shè)計很多讀者第一次看會覺得很奇怪為什么不滿了就加10個為什么彈到一半就縮其實這背后是均攤分析Amortized Analysis的思想。如果我們每次滿就加一個固定值比如10那么連續(xù)插入n個元素的時間是11...11011...110...最壞情況是O(n^2)因為每次擴容都要把舊數(shù)據(jù)復制到新數(shù)組。但如果按2倍擴容擴容次數(shù)只有O(log n)次總復制次數(shù)是124...n2n-1均攤到每次插入就是O(1)。為什么縮容選擇1/4而不是1/2因為如果滿時擴容到2倍而你在容量為2N時彈到N就立刻縮容那緊接著你壓入一個元素又會觸發(fā)擴容到2N這樣反復在閾值附近操作會導致頻繁擴容/縮容形成所謂的抖動thrashing。把觸發(fā)線調(diào)到1/4留出了一倍的緩沖空間就避免了這個問題。這是一個非常優(yōu)雅的工程設(shè)計你以后寫任何動態(tài)數(shù)組包括Java的ArrayList都可以參考這個思路。3.3 可迭代容器設(shè)計內(nèi)部迭代器與Fail-Fast機制讓容器實現(xiàn)IterableT接口需要在內(nèi)部提供一個IteratorT的匿名類或內(nèi)部類。這里面有幾個實操細節(jié)值得展開。第一迭代器應該記錄當前節(jié)點的引用而不是返回一個數(shù)組的副本。很多新手寫迭代器時會先把所有元素復制到一個臨時數(shù)組再遍歷數(shù)組——這雖然能跑但空間復雜度O(n)就白費了而且違背了惰性求值的初衷。正確的做法是棧的迭代器用一個Node current first隊列迭代器用Node current first數(shù)組實現(xiàn)的棧則用一個int i N每次調(diào)用next()時相應移動。第二迭代器是否需要fail-fast快速失敗Java標準庫里的ArrayList、HashMap等容器都有fail-fast機制如果在迭代過程中檢測到結(jié)構(gòu)性修改比如調(diào)用add或remove迭代器會拋出ConcurrentModificationException。教材里的迭代器沒有做這個檢查因為這是教學代碼追求最小實現(xiàn)。但如果你在生產(chǎn)環(huán)境寫自己的容器我強烈建議加上modCount計數(shù)器的檢查。這可以幫你盡早發(fā)現(xiàn)一邊遍歷一邊修改這種隱蔽的bug否則會出現(xiàn)難以定位的間歇性錯誤。第三迭代器的hasNext()和next()方法要對邊界情況做防御。比如next()在沒有更多元素時應該拋NoSuchElementException而不是返回 null 或數(shù)組越界。這個細節(jié)雖然小但寫容器庫時接口約定必須明確。3.4 對象游離GC視角下的隱藏內(nèi)存泄漏這一節(jié)我要特別強調(diào)一個章節(jié)里容易一眼帶過的知識點——對象游離Loitering。教材里這樣描述在棧的pop()實現(xiàn)中如果不把彈出的數(shù)組項設(shè)為null那么數(shù)組依然持有這個對象的引用即使外部已經(jīng)不再使用它GC也無法回收它。聽起來很簡單但實際開發(fā)中這個問題極其隱蔽。我給你講一個真實場景。某次我在寫一個簡單的事件處理器時用了一個數(shù)組實現(xiàn)的棧來暫存事件對象。彈出后我直接用return items[--N]沒有把items[N]置為null。功能一切正常但服務(wù)跑了一個月后內(nèi)存曲線穩(wěn)步上升最終OOM。排查了很久才發(fā)現(xiàn)那些已經(jīng)被彈出的事件對象因為數(shù)組中還保留著引用GC永遠無法回收它們。這就是游離對象導致的內(nèi)存泄漏——不是傳統(tǒng)意義上無法訪問的泄漏而是其實還能訪問但永遠不再有用的泄漏。所以無論你用鏈表還是數(shù)組實現(xiàn)容器只要元素是從容器中移除的都應該立刻清除引用。鏈表實現(xiàn)中將first指向下一個節(jié)點并置空舊節(jié)點的item數(shù)組實現(xiàn)中將items[N]置為null。這個習慣養(yǎng)成了你能在未來的開發(fā)中避開一個大坑。4. 實操過程與核心環(huán)節(jié)實現(xiàn)4.1 手寫鏈表實現(xiàn)的棧從節(jié)點類到迭代器現(xiàn)在我們把理論落到代碼上。教材里用鏈表實現(xiàn)棧我在這里給出一個完整可運行的版本加了詳細的注釋并在實現(xiàn)上做了一些生產(chǎn)級優(yōu)化。import java.util.Iterator; import java.util.NoSuchElementException; public class LinkedStackItem implements IterableItem { private NodeItem first; // 棧頂元素 private int n; // 元素數(shù)量 private static class NodeItem { private Item item; private NodeItem next; } public LinkedStack() { first null; n 0; } public boolean isEmpty() { return first null; } public int size() { return n; } public void push(Item item) { NodeItem oldFirst first; first new NodeItem(); first.item item; first.next oldFirst; n; } public Item pop() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); Item item first.item; first first.next; n--; return item; } public Item peek() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); return first.item; } public IteratorItem iterator() { return new LinkedIterator(first); } private class LinkedIterator implements IteratorItem { private NodeItem current; public LinkedIterator(NodeItem first) { current first; } public boolean hasNext() { return current ! null; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); Item item current.item; current current.next; return item; } } }幾個關(guān)鍵點我再重復強調(diào)一遍Node用靜態(tài)內(nèi)部類避免持有外部類引用。predicate檢查isEmpty()要在pop()和peek()中做不然你會在空棧上解引用空指針。迭代器是單鏈方向從棧頂往棧底遍歷。這個順序?qū)碚f是符合直覺的后進先出。push操作里用oldFirst暫存舊節(jié)點再新建節(jié)點指向它。頭插法O(1)。這里pop()我其實沒有把first.item置為null因為鏈表節(jié)點會被GC回收如果外部不再引用。但如果你保存了彈出的Node引用請記得置空。這就是我在上一節(jié)提到的游離對象問題在鏈表實現(xiàn)中的變體。4.2 數(shù)組實現(xiàn)的棧動態(tài)擴容和縮容的完整代碼鏈表實現(xiàn)的棧邏輯簡單但每個節(jié)點要存一個引用內(nèi)存開銷大。數(shù)組實現(xiàn)更緊湊但需要處理擴容。下面是完整的數(shù)組棧實現(xiàn)import java.util.Iterator; import java.util.NoSuchElementException; public class ResizingArrayStackItem implements IterableItem { private Item[] items; private int n; public ResizingArrayStack() { items (Item[]) new Object[2]; n 0; } public boolean isEmpty() { return n 0; } public int size() { return n; } private void resize(int capacity) { Item[] temp (Item[]) new Object[capacity]; for (int i 0; i n; i) { temp[i] items[i]; } items temp; } public void push(Item item) { if (n items.length) { resize(2 * items.length); } items[n] item; } public Item pop() { if (isEmpty()) throw new NoSuchElementException(Stack underflow); Item item items[n - 1]; items[n - 1] null; // 避免對象游離 n--; if (n 0 n items.length / 4) { resize(items.length / 2); } return item; } public IteratorItem iterator() { return new ReverseArrayIterator(); } private class ReverseArrayIterator implements IteratorItem { private int i n; public boolean hasNext() { return i 0; } public Item next() { if (!hasNext()) throw new NoSuchElementException(); return items[--i]; } } }這份代碼里有幾個細節(jié)值得你反復琢磨resize方法里創(chuàng)建新數(shù)組后要手動拷貝所有舊元素。這里我用了一個循環(huán)某些書籍里會建議用System.arraycopy性能更好。但在學習階段手寫循環(huán)更能加深理解。push里的擴容條件是n items.length。注意此時數(shù)組中所有位置都已被占用再插入就必須擴容。擴容倍率2這是時間與空間的平衡點。擴容后舊數(shù)組會被GC回收新的數(shù)組長度是原來的2倍。pop里的縮容條件是n 0 n items.length / 4。這里有一個n 0的守衛(wèi)防止空棧時items.length為0的情況理論上不會發(fā)生因為初始容量是2但防御性代碼總是好的。迭代器實現(xiàn)的是從棧頂?shù)綏５椎谋闅v。因為棧是LIFO迭代器方向應該從最近的元素開始也就是數(shù)組尾部。我記得有一次寫迭代器時方向搞反了導致輸出順序完全不對調(diào)試了半天才發(fā)現(xiàn)。這個方向細節(jié)很值得記下來。4.3 隊列的鏈表實現(xiàn)頭尾雙指針怎么維護隊列比棧多一個限制入隊在一端出隊在另一端。用鏈表實現(xiàn)時我們需要維護兩個指針first指向隊頭出隊端last指向隊尾入隊端。public class LinkedQueueItem implements IterableItem { private NodeItem first; private NodeItem last; private int n; private static class NodeItem { private Item item; private NodeItem next; } public boolean isEmpty() { return first null; } public int size() { return n; } public void enqueue(Item item) { NodeItem oldLast last; last new NodeItem(); last.item item; last.next null; if (isEmpty()) { first last; } else { oldLast.next last; } n; } public Item dequeue() { if (isEmpty()) throw new NoSuchElementException(Queue underflow); Item item first.item; first first.next; n--; if (isEmpty()) { last null; // 避免游離對象 } return item; } }有個細節(jié)我特別想強調(diào)在enqueue時如果隊列為空first和last必須同時指向新節(jié)點。如果不處理這個分支老節(jié)點oldLast是null直接oldLast.next last就會空指針。這個邊界條件是鏈表隊列最常見的bug來源。在dequeue時刪除的是first節(jié)點。但要注意如果刪除后隊列空了last仍然指向舊的隊尾節(jié)點這個引用是游離的必須把last置為null。這就是對象游離在鏈表實現(xiàn)中的又一個變體。教科書代碼里我見過不處理這個分支的版本功能上不報錯但嚴格來說內(nèi)存管理有瑕疵。隊列的迭代器實現(xiàn)和棧類似只是從first開始遍歷。這里不再贅述。4.4 背包的實現(xiàn)最簡容器但隱藏了迭代器的強大背包Bag是所有容器里最簡單的一種只往里加東西不給刪除的方法。但別小看它在后面的圖算法和統(tǒng)計計算中背包非常常用——比如你可能需要收集圖中所有頂點的鄰居然后遍歷一遍統(tǒng)計信息但你并不關(guān)心訪問順序。public class BagItem implements IterableItem { private NodeItem first; private int n; private static class NodeItem { private Item item; private NodeItem next; } public void add(Item item) { NodeItem oldFirst first; first new NodeItem(); first.item item; first.next oldFirst; n; } public boolean isEmpty() { return first null; } public int size() { return n; } public IteratorItem iterator() { return new LinkedIterator(first); } }背包的add直接采用頭插法不需要維護last指針因為訪問順序不重要。你注意到?jīng)]有它的實現(xiàn)其實和鏈表棧的push一模一樣。唯一的區(qū)別是接口層沒有pop方法。這正好印證了我前邊說的底層物理結(jié)構(gòu)可以復用但通過接口約束出不同的抽象數(shù)據(jù)類型。背包在算法中的一個典型應用場景是圖的鄰接表。當你用BagInteger[] adj來存儲每個頂點的相鄰頂點時你只關(guān)心能枚舉所有鄰居不關(guān)心鄰居的順序。這時候用一個只支持添加和遍歷的容器從語義上就避免了誤用。我在實際項目里見過用ArrayList當只讀集合的代碼但從接口層面就禁止刪除明顯是更好的設(shè)計。5. 常見問題與排查技巧實錄5.1 編譯錯誤泛型數(shù)組創(chuàng)建失敗現(xiàn)象T[] arr new T[10]編譯直接報錯。原因Java的泛型通過類型擦除實現(xiàn)運行時并不知道T的具體類型因此無法創(chuàng)建泛型數(shù)組。解法可以按下面幾種方式來// 方法1創(chuàng)建Object數(shù)組后強轉(zhuǎn)教材做法 T[] arr (T[]) new Object[10]; // 方法2使用Array.newInstance反射創(chuàng)建更靈活但更繁瑣 T[] arr (T[]) Array.newInstance(clazz, capacity);我建議初學階段用方法1簡潔且夠用。要提醒的是強轉(zhuǎn)會有一個unchecked警告這是正常的。但如果你用方法2雖然能拿到精確類型的數(shù)組代碼復雜度會上升學習時沒必要引入。還有一個小技巧如果你在類里聲明的是private T[] items在構(gòu)造函數(shù)里可以用items (T[]) new Object[capacity]。這個寫法在resize方法里同樣適用。5.2 空棧/空隊操作NoSuchElementException還是返回null現(xiàn)象在空棧上調(diào)用pop()在空隊列上調(diào)用dequeue()程序崩潰或行為異常。原因?qū)崿F(xiàn)時沒有做空指針檢查或者檢查了但拋的異常不明確。解法我建議在pop()、peek()、dequeue()的開頭都顯式檢查isEmpty()如果為空則拋出NoSuchElementException。這樣做有兩個好處一是報錯信息明確Stack underflow二是把異常行為統(tǒng)一到標準庫接口上——java.util.Stack的pop()在空棧時會拋EmptyStackException而java.util.ArrayDeque會拋NoSuchElementException。如果你在寫自己的容器庫遵循Java標準庫的異常約定是最好的選擇。5.3 迭代器中修改容器ConcurrentModificationException還是靜默錯誤現(xiàn)象在遍歷一個棧/隊列的過程中突然插入或刪除了元素程序出現(xiàn)各種詭異行為。原因迭代器已經(jīng)保存了當前節(jié)點的引用但容器結(jié)構(gòu)變了迭代器的狀態(tài)和容器不一致。解法如果你希望快速失敗可以在容器中維護一個modCount計數(shù)器每次結(jié)構(gòu)性修改push/pop/enqueue/dequeue都自增。迭代器保存創(chuàng)建時的modCount每次調(diào)用next()時檢查當前的modCount是否一致不一致就拋ConcurrentModificationException。教材里省略了這個機制但Java標準庫ArrayList的做法就是這樣。如果你在學習階段就理解了這個設(shè)計以后看JDK源碼會輕松很多。5.4 鏈表 vs 數(shù)組的性能選擇什么場景選哪個這是我在評論區(qū)最常被問的問題。這里給一個比較直接的速查表場景推薦實現(xiàn)理由需要頻繁隨機訪問按下標取元素數(shù)組索引訪問O(1)頻繁在頭部插入/刪除鏈表頭部操作O(1)數(shù)組頭部操作O(n)頻繁在尾部插入/刪除數(shù)組均攤O(1)需要頻繁擴容且不確定最終大小數(shù)組動態(tài)擴容均攤O(1)內(nèi)存敏感且節(jié)點數(shù)量巨大數(shù)組鏈表每個節(jié)點多一個引用字段需要頻繁合并兩個容器鏈表只需調(diào)整指針有一個經(jīng)驗法則如果你不確定選哪個優(yōu)先用數(shù)組實現(xiàn)。因為數(shù)組對CPU緩存友好在現(xiàn)代硬件上通常比鏈表快一個量級。鏈表的O(1)插入優(yōu)勢很多時候會被緩存不命中的代價抵消。這一點在后續(xù)學習樹和圖的時候會更明顯。5.5 對象游離導致的隱性內(nèi)存泄漏怎么排查排查內(nèi)存泄漏最直接的辦法就是用內(nèi)存分析工具比如VisualVM、MAT看堆轉(zhuǎn)儲。如果你發(fā)現(xiàn)一個數(shù)組容器里的對象遲遲不能被回收而代碼邏輯上它們已經(jīng)不再需要那十有八九就是對象游離問題?？梢园聪旅鎺撞娇焖倥挪闄z查所有pop()、dequeue()、remove()方法確認刪除元素后是否將數(shù)組槽位置為null。檢查所有臨時引用是否清理干凈。比如你保存了Node引用刪除后要把node.item置為null。檢查容器縮容時擴縮容方法是否完整拷貝有效元素并丟棄舊數(shù)組引用。我自己的習慣是寫完一個容器之后用-Xmx16m跑一個小堆內(nèi)存的測試腳本往里壓幾百萬個對象再全彈出來看內(nèi)存是否回落到初始水平。如果內(nèi)存不回落說明有游離引用。這個方法簡單有效適合你自己寫容器的自測。5.6 邊寫邊測的單元測試模板最后分享一個我用來測試這些容器的單元測試模板。別小看測試這些容器雖然代碼不長但邊界條件非常多。public class StackTest { Test public void testPushPopOrder() { LinkedStackInteger stack new LinkedStack(); stack.push(1); stack.push(2); stack.push(3); assertEquals(3, stack.pop().intValue()); assertEquals(2, stack.pop().intValue()); assertEquals(1, stack.pop().intValue()); assertTrue(stack.isEmpty()); } Test public void testResizingArrayStackManyElements() { ResizingArrayStackInteger stack new ResizingArrayStack(); for (int i 0; i 10000; i) { stack.push(i); } for (int i 9999; i 0; i--) { assertEquals(i, stack.pop().intValue()); } assertTrue(stack.isEmpty()); } Test(expected NoSuchElementException.class) public void testPopEmptyStack() { LinkedStackInteger stack new LinkedStack(); stack.pop(); } Test public void testQueueOrder() { LinkedQueueString queue new LinkedQueue(); queue.enqueue(a); queue.enqueue(b); queue.enqueue(c); assertEquals(a, queue.dequeue()); assertEquals(b, queue.dequeue()); assertEquals(c, queue.dequeue()); assertTrue(queue.isEmpty()); } Test public void testIterator() { LinkedStackInteger stack new LinkedStack(); stack.push(1); stack.push(2); int sum 0; for (int x : stack) { sum x; } assertEquals(3, sum); } }這套模板覆蓋了順序性、擴容場景、空容器操作、迭代器四條基本路徑。你可以在這些基礎(chǔ)上增加性能測試比如壓入100萬個元素看耗時來對比鏈表和數(shù)組實現(xiàn)的差距。6. 從這章延伸出去你在為后面的算法鋪路講了這么多具體實現(xiàn)最后我想跳出來談?wù)勥@一章在更大知識圖譜中的位置。很多人學《算法第4版》會犯一個錯誤急著往后翻圖算法和字符串算法覺得容器是常識不需要細看。但我可以負責任地說后面所有算法章節(jié)都會用到這章的知識而且用的方式往往是組合拳。圖算法里深度優(yōu)先搜索DFS本質(zhì)上就是用?；蜻f歸遞歸就是隱式棧實現(xiàn)的廣度優(yōu)先搜索BFS則是用隊列實現(xiàn)的。你要是沒把棧和隊列的實現(xiàn)搞清楚后面理解DFS、BFS會非常吃力。堆排序、優(yōu)先隊列這些本質(zhì)上是在數(shù)組上實現(xiàn)的一棵完全二叉樹你在這一章學到的動態(tài)數(shù)組擴容和對象游離處理全部會復用到優(yōu)先隊列的實現(xiàn)中。符號表那章用鏈表實現(xiàn)順序查找其實就是這一章鏈表實現(xiàn)的直接延伸只是節(jié)點里多存了一個鍵值對。我自己學這章時做過一件小事把這三種容器的鏈表實現(xiàn)和數(shù)組實現(xiàn)各寫了一遍然后跑了一組對比測試記錄了插入10萬、100萬、1000萬個元素的時間。結(jié)果讓我印象深刻在1000萬規(guī)模下數(shù)組實現(xiàn)比鏈表實現(xiàn)快大約一個數(shù)量級。這個數(shù)據(jù)讓我以后在選擇容器時有了更強的直覺。我建議你也做一次類似的實驗這會讓你對算法的常數(shù)因子有切身體會。這章還有一個價值我很少見人提起但它實際很重要它是對抽象數(shù)據(jù)類型這個概念最好的入門訓練。理解了物理存儲結(jié)構(gòu)鏈表/數(shù)組和邏輯訪問規(guī)則LIFO/FIFO/無序是兩回事你就擁有了和數(shù)據(jù)結(jié)構(gòu)的本質(zhì)打交道的能力。以后你看任何高級數(shù)據(jù)結(jié)構(gòu)比如跳表、紅黑樹、B樹本質(zhì)上都是某種物理結(jié)構(gòu)服務(wù)于某種訪問規(guī)則的產(chǎn)物。有了這個思維模型你會走得更遠。