最好的存儲和散列方式<int, int> key（C++）

我的目標是創建一個有效的結構來存儲一個矩陣的最相關的條目，這個條目在沒有內存限制的世界中大約爲10^5 x 10^5並充滿雙打。矩陣是對稱的，所以它實際上只包含（10^10）/ 2個值。最好的存儲和散列方式<int, int> key（C++）

我需要在我的模擬中多次訪問條目，所以快速檢索是至關重要的。

爲了保持結構的可管理性，我將刪除不太可能使用的成員。如果索引是（int_x1，int_x2），我經常想要刪除包含例如x1的所有對。

該任務的最佳結構或結構是什麼？什麼是兩個整數的好散列？

爲了便於攜帶，我想避免使用Boost。我目前正在程序的其他地方使用TR1的unordered_map。我正在考慮使用密鑰對再次使用unordered_map，但我不確定如何以這種方式高效地刪除條目，並且我不知道什麼是好的哈希函數。

我是一個開始的程序員，所以請陳述明顯。

來源

2009-11-02 Sarah

您是否還需要像所有x1成員一樣頻繁地刪除所有x2成員？ – jmucchiello 2009-11-02 23:33:25

您是否考慮過使用標準稀疏矩陣存儲方案，如CSR？根據您需要在矩陣上執行的操作，它可能正常工作。 – mch 2009-11-02 23:40:41

爲了便於攜帶，你想避免提升？增強是相當便攜，並有輕量級，可以做你所需要的。 – Patrick 2009-11-03 09:22:47

如果數據相當稀疏，可以使用散列表數組。

hash_map<int,double> matrix[] = new hash_map<int,double>[10000]; 
for (int i = 0; i < 10000; i++) matrix[i] = new hash_map<int,double>();

然後要查找值（x，y），可以用x索引數組並在哈希表中查找y。

有幾件事情需要注意的：

刪除可以得到相當昂貴的，因爲你必須通過大量的哈希表進行迭代。
隨着您刪除/插入，總存儲量可能會增加，您應該偶爾修剪（）您的hash_maps。
應該很容易利用對稱性。

來源

2009-11-02 23:58:32

這個是合理的，但是對於我來說做一個哈希表向量可能會更好，因爲我事先不知道數組的大小。是否有理由不使用哈希表哈希表？ – Sarah 2009-11-03 16:21:04

您能否也解釋一下你的意思是trim（）？這似乎不是TR1的unordered_map或我發現的任何其他哈希映射的成員函數。我目前有一個用於x1索引的哈希表，其中x1> x2。每個條目都指向一個單獨的哈希表，其中包含所有x2 Sarah 2009-11-03 19:47:56

散列表的散列表將會很好，但有點矯枉過正，因爲1維中的索引幾乎肯定會很密集。是的，一個向量會很好。對不起，修剪是一般的概念，而不是一個特定的功能。大多數實現在插入時自動增長哈希表，但不要在刪除時自動縮小哈希表。您可能需要定期修剪您的hash_maps以節省一些內存（取決於您的插入/刪除模式）。在C++中沒有這種方法，但是如果size（）比bucket_count（）小得多，只需將數據複製到一個新的hash_map並刪除舊的。 – 2009-11-04 23:13:41

最好的存儲和散列方式<int, int> key（C++）

回答

相關問題