資料結構

一排連續的格子：用索引讀任何一格都只要一步，但在中間插入就得把後面全部往後搬。

一個 64 位元的整數就是 64 個開關：用位元運算一次處理 64 個布林值，集合的交集、聯集都只要一條指令。

後進先出：只能在頂端放和拿。函式呼叫、括號配對、復原上一步，都是它。

先進先出：從尾端排進來、從前端出去。用環狀陣列實作，兩端進出都只要一步，不用搬動任何元素。

讓堆疊或佇列裡的值一直保持遞增或遞減：每個元素只進出一次，就能在 O(n) 內找出「下一個比我大的」或「每個視窗的最大值」。

用雜湊函數把鍵直接算成陣列位置，查找平均只要一步——前提是雜湊函數把鍵分得夠散。

用一排位元和幾個雜湊函數回答「一定不在」或「可能在」：用極少的記憶體，換取一點點可以控制的誤判。

也包含：HyperLogLog 與 Count-Min Sketch

永遠能在一步內拿到最小值的樹，而且整棵樹就存在一個陣列裡。優先佇列就是它。

把東西分成不相交的群組，隨時問「這兩個是不是同一群」。路徑壓縮加上按大小合併，讓每次操作幾乎都是常數時間。

區間總和或最小值要能隨時查、也要能隨時改：前綴和陣列每改一格就得重算 O(n)，線段樹和樹狀陣列（Fenwick tree）把查和改都壓到 O(log n)，而且都存在一個陣列裡。

每個節點記住下一個在哪：在手上的位置插入或刪除只要改兩個指標，但要找第 i 個就得從頭一個一個走。

在排序好的鏈結串列上隨機加幾層快速道路：查找平均只要 log n 步，而且不用像平衡樹那樣旋轉。

左邊都比較小、右邊都比較大的樹：查找、插入、刪除都只走一條路徑，但路徑多長取決於插入的順序。

AVL 取自兩位發明者 Adelson-Velsky 與 Landis 的姓氏。插入或刪除後，只要哪裡左右高度差超過 1 就旋轉一下，讓二元搜尋樹不管輸入順序都保持在 log n 高。

也包含：紅黑樹

依字元一層一層往下分岔的樹：找一個字的成本只和字的長度有關，和收了多少字無關，還能列出所有共同字首的字。

找附近的點：Geohash 把座標變成可以排序、可以比字首的字串，四分樹把擁擠的區域一再切細，都不必逐一計算每個點的距離。

點和連線：用相鄰串列還是相鄰矩陣存，決定了「找鄰居」和「兩點有沒有連」哪個便宜，也決定了要多少記憶體。

LRU 是 Least Recently Used（最近最少使用），滿了就淘汰最久沒用的那一筆。雜湊表負責一步找到資料，雙向串列負責記住誰最久沒用；兩個結構合起來，讀取與淘汰都只要一步。

每個節點放很多個鍵，樹因此又矮又胖：存在磁碟上時，每往下一層就是一次讀取，幾十億筆資料也只要三、四層。