小編精選 - 技術文章翻譯 · 07月15日

# 用 Rails 學習資料結構入門～陣列、雜湊、樹、圖其實每天都在用～

お疲れ様です！

前回是處理了「加密與雜湊」。這次稍微往回拉一點，來做一次電腦科學基礎——資料結構 的總整理。

因為到目前為止的「DFS / BFS」「時間複雜度（Big-O）」「資料庫索引」——其實這三篇，全部都在講 資料結構。

DFS/BFS → 堆疊與佇列
時間複雜度 → 各資料結構的 O(1) / O(n) / O(log n)
索引 → B-tree

這次要把這些整理成一張地圖。你可能會想：「資料結構不就是演算法課上才會碰到的東西嗎？」但其實，只要你在寫 Rails，就每天都在用 👇

先看整體地圖：記住的是「擅長與不擅長」

資料結構不是死背，而是 「什麼快、什麼慢」的取捨表。

資料結構	特性	時間複雜度的目安
陣列（Array）	連續記憶體。索引存取很快	存取 O(1)、在開頭插入/刪除 O(n)
鏈結串列	用指標串起來。開頭/結尾插入刪除很快	存取 O(n)、插入/刪除 O(1)
堆疊	LIFO（後進先出）	push / pop O(1)
佇列	FIFO（先進先出）	enqueue / dequeue O(1)
雜湊表	可由鍵直接存取	平均 O(1)
樹（Tree）	具有父子關係的階層結構	依種類而定（搜尋樹通常 O(log n)）
圖（Graph）	節點與邊的集合	依表示方式而定

「陣列和鏈結串列的擅長領域完全相反」 是第一個重點。陣列擅長存取，鏈結串列擅長插入刪除。

陣列 vs 鏈結串列：為什麼會完全相反？

陣列：       [ A | B | C | D ]   ← 在記憶體中連續排列
              ↑ 透過起始位址 + n×大小 一次算出 → 存取 O(1) 🙆
              但如果在開頭插入，所有元素都得往後移一格 → O(n) 😤

鏈結串列： A → B → C → D   ← 每個元素都持有「下一個是誰」的指標
              ↑ 如果想要第 3 個，只能從頭一路走過去 → 存取 O(n) 😤
              但插入時只要重新接上指標 → O(1) 🙆

Ruby 的 Array（內部實作上是動態陣列）就是這邊的「陣列」那一側。ary[3] 很快、ary.unshift 很慢，原因就是這個。

ary = (1..1_000_000).to_a
ary[999_999]      # O(1)：立即回應
ary.unshift(0)    # O(n)：100 萬筆都要往後移一格 💥
ary.push(0)       # 末尾新增是 O(1)（攤銷）

堆疊與佇列：Rails 裡在哪裡出現？

這是 DFS / BFS 那篇裡出現的組合。差別只有「取出的順序」，是很單純的結構，但出現的地方非常主流。

結構	順序	在 Rails 中的常見位置
堆疊（LIFO）	後進先出	呼叫堆疊（例外的 backtrace 本身就是堆疊）、Rack 的 middleware stack
佇列（FIFO）	先進先出	Sidekiq / ActiveJob 的 job queue、連線池等待隊列

# 堆疊：方法呼叫會往上疊，返回時再往下退（所以是 backtrace）
# 佇列：先 enqueue 的 job 會先執行
SomeJob.perform_later(user.id)  # ← 送進 Redis 的 queue（FIFO）

rails middleware 看到的那個列表也被稱為「stack」。request 由上往下，response 再由下往上返回，正是後進先出的概念。

雜湊表：Rails 裡最常工作的結構 🔑

由鍵計算雜湊值，直接跳到儲存位置 的結構，所以平均是 O(1)。

"user_id" ──雜湊函式──> 42 號箱子 ──> 直接存取（不用到處找）🙆

Ruby 的 Hash 本身就是這個結構，在 Rails 裡幾乎像空氣一樣到處在用。

params[:user_id]          # ← 雜湊表
session[:current_user]    # ← 雜湊表
Rails.cache.read("key")   # ← 快取儲存本質上也是 key-value（雜湊）

集合（Set） 也是同類。它是不允許重複的集合，內部常用雜湊表實作。當你想把 ary.include? 的 O(n) 變成 O(1) 時，這就是很常見的做法。

require 'set'
allowed = Set.new(%w[admin editor viewer])
allowed.include?(role)   # 平均 O(1)。陣列的 include? 是 O(n)

樹（Tree）：種類很多，所以用譜系來記 🌳

樹是「具有父子關係的節點集合」。種類看起來很多，但如果用譜系來看，其實是一條很清楚的路。

二元樹（最多 2 個子節點）
  └ 二元搜尋樹 BST（新增規則：左 < 父 < 右 → 搜尋平均變成 O(log n)）
      └ 平衡二元搜尋樹（AVL 樹、紅黑樹：自動修正偏斜 → 最差也保證 O(log n)）
          └ B-tree（單一節點可放多個 key → 資料庫索引的主角）👑

BST：有了規則，就能一路「比較大小往下走」來搜尋；但如果樹偏斜，會退化得像鏈結串列（O(n)）一樣慢 💥
平衡樹：為了避免這種退化，插入時會自動旋轉，維持高度
B-tree：索引那篇提到的就是它。PostgreSQL 和 MySQL 的 add_index 內部核心就是這個。譜系的終點直接接到 Rails

另外還有兩種樹也很值得記：

Trie（字典樹）：專門用於字串的前綴搜尋。它是一層一層按字元往下走的結構，Rails 的路由引擎（Journey）也會用樹狀結構來做 URL 比對
Heap（堆積）：「父節點一定比子節點小（或大）」的鬆散型樹。因為可以 O(1) 取得最小值（或最大值），所以常用來實作優先佇列

圖（Graph）：樹的老大哥

節點與邊的集合。樹是「沒有環」「每個節點只有一個父節點」這些限制下的圖，所以圖是更一般化的版本。

社群網站的追蹤關係、地圖路徑搜尋、Bundler 的 gem 相依解析 等，都是圖問題
表示方式有兩種：鄰接串列（每個節點都持有相連節點清單）與 鄰接矩陣（N×N 的表格）
走訪方法就是 BFS / DFS。前一篇文章可以直接套用

# 鄰接串列的表示法在 Ruby 裡可以用「Hash + Array」來寫（也就是今天內容的組合技）
graph = {
  "A" => ["B", "C"],
  "B" => ["D"],
  "C" => ["D"],
  "D" => []
}

應用：組合起來更強（LRU 快取）💪

實務上真正考的，通常不是單一結構，而是組合。代表例子就是 LRU 快取（Least Recently Used：容量滿了就先捨棄「最近最少使用」的項目）。

把需求拆開來看，就會發現單一結構不夠。

需求①「想用鍵直接存取」            → 雜湊表（O(1)）
需求②「想管理使用順序，刪掉尾端」  → 雙向鏈結串列（修改 O(1)）

只有雜湊表 → 無法管理順序 😤
只有串列   → 鍵搜尋是 O(n) 😤
兩者一起   → 兩種操作都能 O(1) 🙆

其實 Ruby 的 Hash 會 保留插入順序（內部就做了類似這種組合），所以 LRU 可以很直觀地寫出來：

class LruCache
  def initialize(capacity) = (@cap, @h = capacity, {})

  def get(key)
    return nil unless @h.key?(key)
    @h[key] = @h.delete(key)  # 刪掉再放回去＝當作「最近使用」，移到尾端
  end

  def put(key, value)
    @h.delete(key)
    @h[key] = value
    @h.shift if @h.size > @cap  # 砍掉最前面＝最久沒用的項目
  end
end

Rails.cache 的 MemoryStore 在容量超過時，會從舊的項目開始淘汰，也屬於這個思路。「先懂單一結構的強項，才能設計組合」——今天這張表最有用的地方就在這裡。