15
優化我有一個哈希表，其中在運行時，絕大多數的訪問遵循以下模式之一：哈希表的完整的迭代+鍵更換
- 迭代通過所有鍵/值對。 （這個操作的速度很關鍵。）
- 修改鍵（即刪除一個鍵/值對&添加另一個具有相同的值，但不同的鍵。檢測重複鍵&結合值，如有必要）。這是在一個循環，影響成千上萬的密鑰，但沒有其他操作干預。
我也希望它消耗盡可能少的內存。
其他標準操作必須可用，儘管它們使用較少，例如，
- 插入一個新的鍵/值對
- 給定一個鍵，查找相應的值
- 變化與現有的關鍵
當然所有的「標準」哈希表相關聯的值包括大多數高級語言的標準庫在內的實現具有所有這些功能。我正在尋找的是爲第一個列表中的操作優化的實現。
與常見的實現問題：
- 大多數哈希表實現使用分離鏈這工作，但我希望的東西，有更好的地方佔用的內存更少（即，每個桶的鏈接列表。）參考。注意：我的密鑰很小（每個13個字節，填充爲16個字節）。
- 大多數開放尋址方案對我的應用程序有一個主要缺點：密鑰被刪除並在大型組中被替換。這留下了增加載入因子的刪除標記，需要經常重建表格。
方案即工作，但低於理想：每桶
- 分離鏈與陣列（而不是一個鏈表）：
的參考普爾局部性，從內存碎片導致因爲小陣列被多次重新分配 - 線性探測/二次哈希/雙哈希（有或沒有布倫特變化）：
錶快速填充刪除標記 - 杜鵑散列
只適用於< 50％的加載因子，我想要一個高LF來節省內存並加速迭代。
是否有專門的散列方案可以很好地適用於這種情況？
注：我有一個很好的哈希函數，既素表大小的功率爲2的和行之有效的，可用於雙散列，所以這不應該是一個問題。
你似乎做了大量的研究，所以我沒有一個真正的答案。然而，我確實質疑你的參考地點的目標。當然，這取決於你的表的大小和你的實現語言，但我的經驗是，你只能保持哈希數組緩存（然後只有當你幸運）。對你來說，它可能有一個包含鍵和指向該值的指針的結構數組;即每個20字節，或2MB緩存約100,000個條目。當然，你需要一種能夠給你佈局控制的語言。而且負載因數相對較低。 – Anon 2011-05-12 18:46:48
如果你確實擁有一個足夠容納整個表的緩存，它不會真的傷害你（太多），因爲沒有指針的散列數組，而是在第二個連續的內存塊中使用鏈表免費列表來恢復已刪除的條目）。 – Anon 2011-05-12 18:53:46
您希望在表中存儲多少個元素，以及您希望在每次批次密鑰更新操作期間修改多少個密鑰？ – 2011-05-13 03:51:20