沃斯大神說過，程序 = 算法 + 數據結構。
程序君認為，等式的右邊，數據結構的權重要大於算法。數據結構定義好，基本上，你所用的算法也就確定了，算法的時間複雜度也八九不離十。上週，我在 team 內部分享了一個關於數據結構的主題，在這裡，也和諸位分享。
現代的編程語言，內置的數據結構越來越多，從 primitive 的類型：integer, float, boolean， string，一路到 complex 結構，如：array，list，map，set 等。這些結構即插即用，非常順手，可是有時我們也需要了解其內部的實現（內部的數據結構），從而更好地打造高性能的應用。有些「聰明」的語言，如 clojure，會根據使用場景動態地切換內部的結構，比如說 map，當 key 的數量超過某個閾值，便會自動換成更高效的結構來應對需求。
今天，我們就來扒一扒，編程語言中的常見數據類型，其內在究竟是怎麼一回事。
array / tuple
array 或者 tuple，是大家最熟知的容器型的數據類型，其內部可以承載其他數據結構。他們的特點是容器裡的元素被分配在連續的內存中，可以按照 index 隨機訪問，時間複雜度是 O(1)。array 一般要求內部是同構的數據結構，而 tuple 則允許異構。
對函數式編程語言，或者提供 immutable data structure 的語言，高效地處理 array 是個挑戰。如果代碼中修改了 array 中的某個元素，拷貝並重新生成整個 array 的代價太大。我們需要一種合適的數據，能夠在結構上共享大部分不受影響的數據。這種數據結構，便是大部分函數式編程語言使用的 persistent data structure。persistent data structure 用 DAG（一般是一個 Trie）來描述數據，當 DAG 某部分發生改變，只需要重新生成和改變相關的路徑上的節點即可，非常高效。對於 array，我們可以使用 Bit Array Mapped Trie / Index Vector Trie：
通過把 index 的二進制切分並進行 trie 的遍歷，對應的葉子節點就是要找的節點。如果我們要修改這個節點的內容，在原有結構保持不變的情況下，我們只需要生成一個新的 node，並生成這條路徑上一直到根節點的相關中間節點即可。需要額外拷貝的內容僅僅和 trie 的深度有關。
List
大多數編程語言，提及 list，其內部一般是個帶尾指針的雙向鏈表。因而，在頭部或者尾部添加新的節點非常高效，是 O(1) 的操作，然而查找，插入，刪除則需要遍歷鏈表，是 O(n) 的操作。由於是鏈表，獲取鏈表的長度一般而言也需要遍歷，是個 O(n) 的操作，有些編程語言會為其優化，在鏈表的頭部維護鏈表的長度，這樣獲取長度的效率則為 O(1)。請注意弄清楚你用的語言，這個操作的效率如何。對於 erlang，length 函數是 O(n) 的複雜度，因而對大列表的 length 操作不要濫用。
Map
map，在很多語言裡，被稱為 associate array (php)，dict（python）等。他是一個 key/value pair 的容器。理論上可以容納任意數量的 key/value pair。在 map 中，key 是唯一的，key 和 value 一般都可以是任意數據結構。當 key 只能是 string 時，有些語言會使用標準的 trie，或者 patricia trie 來處理。
早期的 map 用 hash array + collision avoidance 實現，典型的 collision avoidance 有 chaining 和 probing。一個 key 經過某個哈希函數後，對應 hash array 中的一個位置，如果這個位置已經有數據，要麼，把數據 用 linklist chain 起來，這是 chaining；要麼，在 array 中隨後的某個固定位置找到（probe）一個空閒的 slot，寫入，這是 probling。
chaining 的問題是如果 key 的數量大大超過 hash array 的長度，衝突會很嚴重，從而大大拉低性能。最壞情況下，時間複雜度是 O(n/k)；probing 的問題是 hash table 必須和 key 空間一樣大，如果 hash 函數選得不好，容易造成大面積的衝突。對於支持動態增減 key 的 map 來說，常常需要擴大 hash table，然後 rehash，內存和計算的代價都不小。python 的 dict 便是使用 hash array + collision avoidance 實現的。
C++ 及很多其他語言使用紅黑樹來支持 map。hash array 和紅黑樹的比較：
如今大部分 FP 語言，其 map 都使用了類似上文提到的 persistent data structure：HAMT (Hash Array Mapped Trie，作者：Phil Bagwell)：
它將 key 通過哈希函數處理後，成為一個數字，然後從這個 hash value 的低位起，一路向下搜索，直到找到葉子節點，如果葉子節點上的數據和 key 匹配，則查找到；否則，沒找到。HAMT 使用 32bit / 64bit 的 hash value（上述僅僅是示意），所以 hash collision 的機率很小，如果衝突發生，葉子節點會轉換為 index node，然後用不同的 hash 方法計算原有的葉子節點和新的節點，並將其掛載到 index node 下。
Tree
Tree 的種類很多，這裡講講常用的 AVL, Trie 和近期比較熱門的 Merkle tree。
AVL 是一種比較簡單的 tree，左右兩棵子樹層級不超過 1。如果新加入的節點打破了這個平衡，則需要翻轉（可能多次）使其達到新的平衡。
Trie 是一種前綴樹，可以用來做路由查詢。erlang 的 pattern matching 機制，就是將使用 pattern matching 的代碼轉化成類似 Trie 的代碼結構。
Merkle tree 脫胎於加密算法，可以驗證 tree 的任何部分的正確性，被廣泛用於文件系統（ZFS），文件分塊下載（BT），block chain 等。
在 Merkle tree 裡，每個數據單元生成一個 hash，相鄰的 hash 湊在一起再生成 hash，這樣兩兩結合，一直到根（如果數據單元的總數是奇數，那麼最後一個的 hash 和自己結合）。
舉個文件同步校驗的例子。假設本地磁盤和網盤有 128 個文件（2^7），各自生成一個 Merkle tree，我們只需要從根節點一路比較下來，O(logN) 的效率，就可以找到有差異的文件。
原文出處：程序人生/陳天