C++實作無序容器的方法，且可接受重複的元素

此文翻譯自
http://bannalia.blogspot.tw/2013/10/implementation-of-c-unordered_25.html

上次我們介紹了Hash Table各種流行的方法，現在我們來考慮如果元素有重複，要怎麼辦？
(unordered_multiset  , unordered_multimap)

Hash Table跟重複元素，這是兩個不同玩意，不要混在一起。兩個基本問題要解決。

• Hash的負載係數(load factor)是[所有元素]除以[所有桶子]，但因為重複元素會放在同一個桶子。必須要重新設計負載係數，不然陣列會拼命長大，結果大多數桶子都是空 的。
• 演算法複雜度跟負載係數無關，而是跟桶子裡面塞了多少東西有關。

補救負載係數(load factor)非常困難，因為規範對於負載係數定得太死。沒有多少空間可以作弊。一個細心的工程師會同時考慮最大桶子塞了多少東西以及平均每個桶子有多少 東西。我的選擇是在節點上動手腳，遍歷桶子的時候，可以快速的跳過重複的地方(規範要求相同的元素必須放在一起)。跟不重複版本比較，我們希望時間效率一 樣好！

• Dinkumware libc++ , libstdec++ -V3函式庫

對於重複元素，根本沒做任何處理。

• Boost.Unordered

有做一些設計，請看圖

桶子b2裡面有五個相同的元素。往前指的指標改成指向重複元素最後一個。利用這個反向指標，可以把五個元素視為一個大節點。插入或刪除的時候，先找到第一 個元素，利用反向指標直接跳到第五個元素。省去了掃描的麻煩。

• Boost.MultiIndex

與之前文章的設計類似，第一個節點要指回桶子，所以是特殊處理。其餘節點如果是一樣的資料，就把反向指標串好。

定一個節點叫做X，下一個節點叫做Xn，前一個節點叫做Xp。
假設有多個元素重複，全部串在一起。
第一個叫做F
第二個叫做S
倒數第二個叫做P
倒數第一個叫做L

• Sp=L
• Pn=F

第二個元素，[往前指標]會指向最後節點。
倒數第二個元素，[往後指標]會指向最初節點。

推導一些特性

• 如果Xpnn == X，那就是桶子第一個節點
• 如果Xnpn == X，那就是桶子最後節點
• 如果相同元素>=3，串成一個集團，集團第一個節點條件是Xnp != X && Xnppn == X
• 如果相同元素>=3，串成一個集團，集團第二個節點條件是Xpn != X && Xppnn == X
• 如果相同元素>=3，串成一個集團，集團倒數第二個節點條件是Xnp != X && Xnnpp == X
• 如果相同元素>=3，串成一個集團，集團倒數第一個節點條件是Xpn != X && Xpnnp == X

所有特殊位置節點都可以偵測到。整個雙向鏈結還是可以視為一個環狀。插入刪除節點都可以在O(1)。遇到資料相同的集團，可以直接跳到頭或是跳到尾，大幅 度加速。

插入元素的方法：

1. 使用Hash先找到桶子。(常數時間)
2. 檢查桶子裡面的每個元素，遇到集團的時候，只要檢查集團第一個節點即可。(桶子大小線性時間)
3. 如果元素等於某個集團，把元素加入集團內。如果整個桶子沒有相同元素，直接插入在桶子的頭端。
4. 調整桶子的指標。

遇到重複元素集團的時候，直接用Xnp就可跳到集團最尾端。若重複元素的集團長度低於3。則加速方法不適用。

刪除元素的方法：

1. 刪除鏈結裡面的元素，調整前後指標。
2. 調整桶子的指標。

事實上實作非常複雜，因為在插入刪除的時候，雙向鏈結調整指標，必須要偵測到特殊狀態的指標。但是最後效能提升，遍歷桶子不依賴桶子裡面塞了多少元素，而 是看桶子裡面有多少集團。與不重複版本比較(set/map)，可以達到同樣的效能。如果Hash演算法良好，插入就是O(1)。刪除動作不用管考慮 Hash演算法，一定是O(1)。