C++實作無序容器的方法

本文翻譯自 http://bannalia.blogspot.tw/2013/10/implementation-of-c-unordered.html
C++不叫Hash Table，而是取了一個華麗名字叫無序容器(unordered  associative  container)。從2011開始c++提供了四種無序容器。

• unordered_set  ,   unordered_map              (不可接受重複的元素)
• unordered_multiset  , unordered_multimap (可接受重複的元素)

一個常用的方法是採用單向連結。

在這種狀況下，每個桶子內部都是一個指標，指向一個單向序列。如果Hash演算法設計的好，每個鏈結都很短，插入跟刪除效率會接近O(1)。如圖所示， b1,b3只有一個元素，b2有兩個元素。簡單方便，但是在C++不合用，因為規範要求容器必須可以遍歷，必須提供一個iterator，可以讓 iterator從頭到尾掃過一遍。那要如何從b1跳到b2？最明顯的方法是繼續掃描陣列，直到下一個有裝東西的桶子。但這不可用，因為陣列愈大，掃描愈 慢。偏偏規範明定++i;效率要保持O(1)。為了符合規範，只好把所有元素都串在一起。

我們來看一些Hash Table常用的結構。加上一個模仿Boost.MutiIndex的設計。先假設所有元素都不一樣。
(unordered_multiset  , unordered_multimap以後再討論)

假設有N筆資料，陣列有B個桶子。

• Dinkumware函式庫

這是微軟Visual C++的實現方法。請看圖。

(請注意，桶子的順序不一定要跟元素順序一樣。圖片只是為了繪圖方便)

就跟你想的一樣，所有元素都串在一起。使用雙向連結。現在可以用iterator雙向訪問，代價是要多一個指標。好處是刪除元素非常容易。陣列裡面每個桶 子都有兩個指標，指向鏈結的頭跟尾。

插入元素的方法：

1. 使用Hash先找到桶子。(常數時間)
2. 元素如果重複要放棄插入，所以要掃描桶子裡面所有元素。(桶子大小線性時間)
3. 新元素插入在鏈結的頭。(常數時間)
4. 調整桶子裡面的兩個指標。(常數時間)

刪除元素的方法：

1. 使用Hash先找到桶子。(常數時間)
2. 刪除鏈結一個元素，調整前後指標。(常數時間)
3. 調整桶子裡面的兩個指標。(常數時間)

操作效率是O(1)，記憶體消耗，每個元素要兩個指標，每個桶子也要兩個指標。

• 2N+2B

看起來很好，但其實Dinkumware的方法對於刪除元素，有一個嚴重的瑕疵。

1. 使用Hash先找到桶子。(常數時間)

如果Hash函式會丟出例外，今天刪除動作就失敗了。偏偏規範又講明刪除保證要成功，而且不可以丟出任何例外。所以Dinkumware方法其實不符合規 範。

• Boost.Unordered, libc++ , libstdec++ -V3函式庫

Boost.Unordered, libc++函式庫使用類似的資料結構。但設計成單向鏈結。

1. 所有元素用單向鏈結串在一起。
2. 因為刪除動作不可以拋出異常。刪除的時候不可以呼叫Hash函式，所以只好把Hash後的數字也存起來。
3. 因為是單向鏈結，為了刪除方便。桶子裡面的指標不是指向第一筆元素，而是第一筆的前一個。所以圖片中的b2指標指向前一個的b1。

刪除元素的方法：

1. 因為節點裡面已經有Hash值，可直接定位到桶子。(常數時間，不會丟出異常)
2. 鏈結掃過一遍。(桶子大小線性時間)
3. 刪除鏈結一個元素，調整前後指標。(常數時間)
4. 調整桶子裡面的指標。(常數時間)

插入刪除都是O(1)。滿足規範。記憶消耗如下

• 2N+1B

(我們假設Hash的數字，占用大小跟一個指標一樣)

libstdec++ -V3提供了一個最佳化設計。如果Hash函式確定不會丟出異常。(有使用nonexcpt)。函式庫會標記成fast模式。節點裡面不會儲存Hash數 字。我覺得這設計有點危險。代碼裡面使用__is_fast_hash type來標記，基本型態通通設定為true。使用者自訂Hash函式預設是false，除非函式有用nonexcept，才會變成true。

不考慮最佳化的特殊機制，2N+1B似乎已經是好的設計了。但事實上還有更好的方法，不需要再增加任何記憶體。

• 簿記式的資料結構

Boost 1.56 Boost.MutiIndex裡面使用了一種全新的方式。雙向鏈結改用環狀的方式。

定一個節點叫做X，下一個節點叫做Xn，前一個節點叫做Xp。環形鏈結代表

• X = Xnp = Xpn

這個條件永遠成立。
連結往前再往後一定會回到自己。
連結往後再往前一定會回到自己。

我們現在看一下完整的示意圖


把陣列桶子也加進來，做一個小改動。

如果元素是桶子的第一個元素，Xp改成指向桶子自己。

可以導出一些規則。

• 如果Xpn != X，代表X是這個桶子的第一個元素
• 如果Xnp != X，代表X是這個桶子的最後一個元素
• 下一個元素一定可以用Xn取得。
• 前一個元素比較麻煩，如果是桶子的第一個元素，前一個元素就是Xpn，其他元素直接用Xp存取即可。

所有動作都是常數時間，我們可以把它還是當作環形鏈結。只是往前移動需要特殊處理。

刪除元素的方法：

1. 從雙向連結刪除元素，調整前後指標。(常數時間)
2. 調整桶子裡面的指標。(常數時間)

刪除元素不需要把一個桶子都翻遍，就算遇到差勁的Hash演算法也沒差。記憶體不用增加。還是2N+1B。