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

ilove690

此文是翻譯文章

網頁版
http://gamehevenhome.blogspot.tw/2015/08/c.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.調整桶子裡面的兩個指標。(常數時間)
4.操作效率是O(1)，記憶體消耗，每個元素要兩個指標，每個桶子也要兩個指標。

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

使用Hash先找到桶子。(常數時間)
如果Hash函式會丟出例外，今天刪除動作就失敗了。偏偏規範又講明刪除保證要成功，而
且不可以丟出任何例外。所以Dinkumware方法其實不符合規 範。

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


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