如果說 1950 年代是電腦的「史前時代」，那麼 1960 年代就是電腦科學的「古典時代」。這十年風起雲湧：IBM 推出了劃時代的 System/360 主機，實現了軟硬體兼容；COBOL 和 FORTRAN 語言開始統治商業與科學計算；人類憑藉阿波羅計畫的導引電腦登上了月球；而「作業系統」(Operating System) 這個概念的出現，更意味著電腦不再是次只做一件事的機器，而是需要同時管理多個任務的複雜中樞。
隨著軟體規模的擴大，程式設計師們的「痛苦」也隨之加劇。他們發現，光靠「陣列」和「鏈結串列」這兩把石器時代的斧頭，已經無法建造起宏偉的軟體大教堂。問題變得更尖銳了：
- 編譯器如何理解 FORTRAN 程式碼的複雜巢狀結構？
- 作業系統如何管理上百個檔案的層級目錄？
- 資料庫（當時的雛形）如何從一百萬筆員工紀錄中，快速找到「Ho Tse Wen」的薪資？
這些問題，都指向了比「線性儲存」更高級的需求——「關係」的表達與「效率」的極致。正是在這個需求背景下，電腦科學正式分野。一群學者試圖為其建立數學般的嚴謹理論；而另一群工程師，則在記憶體的限制中，尋找通往速度的捷徑。
一、 理論的奠基：高德納 (Donald Knuth) 與《電腦程式設計藝術》
1. 一個領域的「聖經」
在 1960 年代之前，程式設計更像是一種「手藝」或「黑魔法」。程式設計師們各自憑藉經驗和直覺，寫出各種巧妙（或糟糕）的程式碼。這個領域缺乏系統性的理論，沒有共同的語言來分析「好」與「壞」。直到一位名叫高德納 (Donald Knuth) 的年輕數學家出現，一切都改變了。1962 年，他開始著手撰寫一本關於「編譯器」的書，但很快發現，在談論編譯器之前，必須先釐清「程式設計」本身的基本原理。
這個計畫最終演變成一套鴻篇巨著——《電腦程式設計藝術》(The Art of Computer Programming, TAOCP)。1968 年，第一卷《基本演算法》(Fundamental Algorithms) 出版。這本書的問世，其意義不亞於牛頓的《自然哲學的數學原理》之於物理學。它首次將程式設計從「手藝」提升到了「科學」的高度。高德納用嚴謹的數學工具，系統性地分析了演算法的效率。
他並未「發明」大部分的資料結構，但他扮演了更關鍵的角色：「定義者」與「分析者」。他引入（或至少是普及了）「大O表示法」(Big O notation)，讓程式設計師終於有了一把客觀的尺子，去衡量一個演算法在處理大量資料時的「時間複雜度」和「空間複雜度」。這本書成為了往後數十年電腦科學系學生的「聖經」，它確立了「演算法分析」這門學科的核心地位。
2. 抽象化：從「怎麼存」到「是什麼」
高德納在 TAOCP 中的最大貢獻之一，就是將資料結構「抽象化」。他不再把「鏈結串列」僅僅看作是「節點+指標」的實作技巧，而是將其定義為一種「線性列表」(List) 的抽象概念，並分析其「搜尋」、「插入」、「刪除」等操作的數學特性。同理，他也嚴謹地定義了「堆疊」(Stack，後進先出) 和「佇列」(Queue，先進先出) 這些在 50 年代末已零星出現的結構。
這種抽象化，是電腦科學的第一次思想飛躍。它意味著程式設計師可以先專注於「邏輯」層面：我需要一個什麼樣的結構來解決我的問題？ 是需要「後進先出」（例如編譯器在解析函式呼叫時），還是「先進先出」（例如作業系統在管理列印任務時）？決定了邏輯需求後，才去考慮「實作」層面：我該用「陣列」還是「鏈結串列」來實作這個堆疊？
高德納的嚴謹分析，將資料結構從硬體記憶體的束縛中解放出來。他關心的是這些結構的「邏輯特性」與「數學效率」，而非它們在某台特定機器上的位元排列。正是這種對抽象邏輯的重視，為「理論派」開闢了廣闊的天地，使他們得以從古老的數學分支中汲取靈感。
二、 關係的具象化：「樹」(Tree) 與「圖」(Graph) 的引入
1. 超越線性：用「樹」表達層級
1960 年代的程式設計師面臨的最大困境，是如何表達「非線性」的關係。世界並不是一條直線。家族有族譜，公司有組織圖，文章有章節，檔案系統有目錄和子目錄。這些都是「層級」(Hierarchy) 關係。使用「陣列」或「鏈結串列」來儲存這些資料，會變得極其複雜且效率低下。
為此，理論家們從數學的「圖論」(Graph Theory) 中借用了「樹」(Tree) 結構。樹狀結構由「節點」(Node) 和「邊」(Edge) 組成，它有一個頂端的「根節點」(Root)，每個節點可以有多個「子節點」，但除了根節點外，每個節點都只有一個「父節點」。這種「一對多」的層級特性，完美地對應了現實世界中的許多問題。
在 1960 年代，「樹」結構迅速在兩個關鍵領域紮根。第一個是編譯器：程式碼中的數學表達式（如 (a + b) * c）或程式區塊（如 if-then-else），可以被完美地轉換成一棵「抽象語法樹」(Abstract Syntax Tree, AST)，編譯器可以透過遍歷這棵樹來理解程式的邏輯。第二個是檔案系統：早期的作業系統（如 Multics，Unix 的前身）開始使用樹狀結構來組織檔案，創造了我們今天所熟知的「目錄」和「子目錄」概念。
2. 萬物相連：「圖」的終極抽象
如果說「樹」是「圖」的一個特例（一種沒有迴圈的、連通的圖），那麼「圖」(Graph) 結構就是對「關係」的終極抽象。「圖」只由兩種東西構成：代表「實體」的「頂點」(Vertex) 和代表「關係」的「邊」(Edge)。它既可以表達「樹」那樣的層級關係，也可以表達更複雜的「多對多」網路關係。
在 1960 年代，「圖」的應用在理論上更為活躍。它被用於「作業研究」(Operations Research) 領域，解決諸如「如何規劃最短的送貨路徑」（Dijkstra 演算法，1959 年底提出，60 年代普及）或「如何在網路中找到最大流量」等問題。它也被用於電子電路設計（EDA），模擬晶片上不同元件的連接。
這個時期，「圖」在很大程度上仍是「邏輯模型」的巔峰。它是一種用來分析問題的數學工具，而不是一種常見的儲存資料的工程結構（因為它在記憶體中實作起來相對複雜）。程式設計師使用「圖論」來思考，但他們在實作時，往往需要更接地氣、更關心記憶體效率的工具。這就催生了「應用派」的偉大發明。
三、 效率的混合體：二元樹的應用
1. 搜尋的兩難：陣列 vs. 鏈結串列
「應用派」工程師面臨一個尖銳的矛盾。當資料被儲存在一個「已排序的陣列」中時，使用「二分搜尋法」(Binary Search) 查找非常快，時間複雜度是 O(log n)。但是，「插入」一個新元素卻是一場災難，因為你可能需要移動陣列中的一半元素O(n)。反之，「鏈結串列」插入很快O(1)，但搜尋卻只能從頭到尾一個個找，慢如蝸牛O(n)。
工程師們渴望一種「魚與熊掌兼得」的結構：既能像「二分搜尋」一樣快速查找，又能像「鏈結串列」一樣快速插入和刪除。答案，就藏在「樹」結構中。1962 年，P. F. Windley、A. J. T. Colin 和 T. N. Hibbard 等人分別獨立提出了「二元搜尋樹」(Binary Search Tree, BST) 的概念。
BST 是一種特殊的「二元樹」（每個節點最多有兩個子節點）。它規定：對於任何一個節點，其「左子樹」上所有節點的值，都必須「小於」該節點的值；而其「右子樹」上所有節點的值，都必須「大於」該節點的值。這個簡單的規則，卻創造了奇蹟。在 BST 中「插入」一個新元素，就像在樹中「搜尋」它的位置一樣，你只需要從根節點開始，比大小，然後往左或往右走，直到找到空位插入即可。這個過程的平均時間複雜度是 O(log n)。
2. 排序與優先權：「堆積」(Heap) 的誕生
BST 解決了「動態搜尋」的問題，但還有另一個問題：排序。更準確地說，是「優先權」問題。在 1960 年代的作業系統中，多個程式（行程）需要共享 CPU。當 CPU 空閒時，系統該選擇哪個行程來執行？顯然，應該選擇「優先權最高」的那個。這就催生了「優先權佇列」(Priority Queue) 的需求：它需要能快速「插入」一個新任務，並且能隨時「取出」優先權最高的任務。
1964 年，J. W. J. Williams 發明了「堆積」(Heap) 結構，並在同年提出了著名的「堆積排序」(HeapSort) 演算法。Heap 又是「二元樹」的一種巧妙應用。它規定：任何一個「父節點」的值，都必須「大於等於」（或小於等於）其所有「子節點」的值。這被稱為「堆積屬性」。
這個屬性精妙地保證了「根節點」永遠是最大（或最小）的那個元素。因此，「取出最高優先權」的操作，永遠是 O(1) 的（只需抓取根節點）。取出後，為了維持堆積屬性，需要進行一番調整（稱為 heapify），這個調整的時間是 O(log n)。而「插入」一個新元素，也只需要 $O(log n) 的時間。Heap 完美地解決了優先權佇列的問題，至今仍是作業系統排程器的核心結構之一。
3. 邏輯與儲存的首次交會
二元搜尋樹 (BST) 和堆積 (Heap)，是 1960 年代最偉大的發明之一。它們的誕生，標誌著「邏輯模型」與「儲存模型」的第一次完美交會。它們都是「樹」這種抽象邏輯結構，但它們被設計出來的唯一目的，是為了解決「搜尋」和「排序」這兩個最核心的「儲存效率」問題。
然而，BST 很快暴露出一個嚴重缺陷：它在「平均情況」下表現良好 ($O(\log n)$)，但在「最壞情況」下（例如，當你按順序插入 1, 2, 3, 4, 5...），BST 會「退化」成一條傾斜的「鏈結串列」，其所有操作的效率都會掉到 $O(n)$。這個「平衡」問題，成為了 60 年代末的未解難題（如 AVL 樹在 1962 年被提出，但尚未普及），也直接引爆了 70 年代「平衡樹」的黃金年代。
四、 效率的極致：雜湊表 (Hash Table) 的勝利
- O(1) 的終極夢想
當理論家們還在為 BST 的 O(log n) 效率歡呼時，一群更講求「實用」和「速度」的工程師，正在追求一個更瘋狂的夢想：我們能不能像「陣列」一樣，在 $O(1)$（常數時間）內，完成搜尋、插入和刪除？ 換句話說，我不管資料有多少（一千筆或一億筆），我都要在「一步」之內找到它。
這個夢想聽起來像天方夜譚。陣列之所以能 O(1) 存取，是因為資料的「鍵」(Key)（即它的索引 index）和它的「儲存位置」(Address) 是一致的。但如果我的鍵是「Tse Wen」這樣的字串呢？我總不能在記憶體中創造一個「Tse Wen」號地址吧？
「雜湊表」(Hash Table) 的發明，就是為了實現這個夢想。這個概念的起源可以追溯到 1953 年 IBM 的 Hans Peter Luhn，但它真正在 1960 年代被工程師們發揚光大。其核心思想被稱為「雜湊」(Hashing)：使用一個「雜湊函式」(Hash Function)，將任意的「鍵」(Key) 轉換成一個固定範圍的「整數」，並以此整數作為「陣列」的「索引」。
2. 魔法的代價：「碰撞」(Collision)
雜湊表的運作原理，就像一個魔法分類帽。當一筆新資料（例如，學號 S123456，姓名 Ho Tse Wen）進來時，你只看它的鍵 S123456。你把這個鍵丟進「雜湊函式」（例如，f(key) = key % 997），函式吐出一個數字，比如 123。於是，你就把 Ho Tse Wen 的資料，儲存到一個大陣列的第 123 號位置。
下次，當你要「搜尋」S123456 時，你根本不需要遍歷。你只需要重複一次這個計算，f(S123456) = 123，然後直奔陣列的第 123 號位置，資料就在那裡。這就是 $O(1)$ 的魔力。這使得雜湊表成為 1960 年代「編譯器」開發者的最愛。編譯器需要一張「符號表」(Symbol Table) 來儲存程式中所有的變數名稱（如 x, temp, my_function），它需要極快地查詢這些變數的資訊，雜湊表是完美的不二之選。
然而，這個魔法是有代價的。如果 S123456 算出來是 123，而另一筆資料 S654321 算出來也是 123 怎麼辦？這就是「碰撞」(Collision)。1960 年代的工程師們圍繞「碰撞」發展了兩大解決策略：一是「鏈結法」(Chaining)，在陣列的第 123 號位置掛一個「鏈結串列」，把所有雜湊到 123 的資料都串在後面；二是「開放定址法」(Open Addressing)，如果 123 被佔了，就去試 124、125，直到找到空位為止。
3. 「儲存模型」的極致體現
雜湊表是「儲存模型」哲學的極致體現。它在「邏輯」上是混亂的：它完全打亂了資料的原始順序，S123456 和 S123457 可能被儲存在記憶體中兩個相距十萬八千里的位置。它在「空間」上是浪費的：為了減少碰撞，雜湊表通常需要保持 30% 以上的「空閒」空間。
它犧牲了「順序性」和「空間」，只為了換取「速度」這一個目標。它不關心資料的「抽象關係」，只關心資料在「記憶體中的物理位置」。它不是數學家眼中優雅的藝術品，而是工程師手中那把最快、最有效率的鐵鎚。雜湊表的巨大成功，深刻地體現了 1960 年代「實用主義」的工程精神。
五、 雙軌的並行
1960 年代，是電腦科學的「成年禮」。這個十年，以一個巨大的「分歧」作為標誌。
- 「邏輯模型」（理論派）：由高德納集大成，他們關心「抽象」與「數學」。他們從圖論中帶來了「樹」和「圖」，試圖為世界的「關係」建模。他們追求的是嚴謹、優雅與「可分析性」。
- 「儲存模型」（應用派）：由無數的系統工程師推動，他們關心「效率」與「硬體」。他們在記憶體的限制中，創造了「二元搜尋樹」、「堆積」和「雜湊表」。他們追求的是速度、速度、還是速度。
這兩條軌道，看似背道而馳，實則缺一不可。沒有「邏KA輯模型」的抽象，程式設計將永遠停留在手工作坊階段，無法建造複雜的系統；沒有「儲存模型」的效率，再優雅的理論也無法在物理硬體上真正運行。
1960 年代奠定了這兩條軌道。進入 1970 年代，這兩條軌道將開始更深層的交織。理論家們將著手解決 BST 的「平衡」問題，而工程師們則會把這些結構「封裝」起來，一場名為「抽象資料型態」(ADT) 的革命，即將來臨。
