→ lNishan: hash function != hash演算法 08/07 05:35
→ lNishan: 然後關於刪除 unconditionally O(1) 覺得不太對 08/07 05:39
→ lNishan: 關於複雜度的部分我覺得看看就好 08/07 05:45
→ lNishan: hashing 效率牽扯到的因素其實不只這樣 08/07 05:48
網頁版
http://gamehevenhome.blogspot.tw/2015/08/c_4.html
C++實作無序容器的方法，且可接受重複的元素
此文是翻譯文章。
上次我們介紹了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)。
--
下列哪個最好笑？ http://gamehevenhome.blogspot.tw/
1.馬英九維護台灣主權 6.徐旭東宣佈投資全面離開台灣
2.江宜樺愛護學生 7.連勝文表示我的一生充滿挫折
3.戴盛益建議沒錢跟父母借 8.慈濟善款全面救助窮人，絕無貪污
4.趙籐雄呼籲大家不要炒房 9.劉黎兒宣稱太陽能比核電便宜
5.施振榮談創新 10.台灣富人呼籲，證所稅/證交稅打趴經濟，應全面廢除
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.25.1.246
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1438832794.A.99B.html