通過大量（均勻分佈式）整數來存儲和查找空間高效的數據結構

我需要在內存中保存和查找一百萬個均勻分佈的整數。我的工作量非常強烈。
我目前的實現使用HashSet（Java）。我看到很好的查找性能，但內存使用情況並不理想（幾十MB）。
你能想到更高效的（內存）數據結構嗎？
編輯：該解決方案將需要支持少量的數據結構添加。通過大量（均勻分佈式）整數來存儲和查找空間高效的數據結構

背景：
上述整數問題如下問題簡單化：
我有一套100萬的字符串（我的「說文解字」），我想告訴字典是否包含給定的字符串，或不。
字典太大而不適合內存，所以我願意犧牲一點精度來減少內存佔用。我將通過切換到包含每個字符串的哈希碼值（整數）的字典而不是實際的字符來實現。我假設每個字符串發生碰撞的可能性僅爲1M/2^32。

來源

2012-03-17 Gili Nachum

可能是一個[布隆過濾器]的作業（http://en.wikipedia.org/wiki/Bloom_filter）？ – 2012-03-17 21:28:50

你需要一個'insert'操作還是一次構建的字典，並且在查找過程中不再修改？ – 2012-03-17 21:34:30

@Gareth Rees：你爲什麼不把它作爲答案發布，因此可以提高？ – meriton 2012-03-17 21:47:36

聽起來像你可以只是保持排序int[]，然後做二進制搜索。擁有一百萬的價值觀，即20個比較來達到任何價值 - 會不會足夠快？

來源

2012-03-17 21:19:34

但是這應該與HashSet具有相同的內存佔用空間，不是嗎？ – user949300 2012-03-17 21:22:27

@ user949300：不，因爲'HashSet'必須爲每個值分配一個Integer對象（大小差異很大！），*和*它不會像我建議的*和*那樣密集填充，它將不得不爲每個值保留哈希碼*，*它將爲每個值（它將包含哈希碼，當然，因此有點重複計數）具有一個「Entry」對象。當然，所有這些都會讓緩存更加糟糕，同時也會佔用更多的內存。 – 2012-03-17 21:25:49

@ user949300不，HashSet由HashMap支持，並且有很多空單元，這取決於您存儲的實際值。 – Jochen 2012-03-17 21:25:53

對於可用的基元有一些IntHashSet實現。

快速谷歌搜索了我this one。還有一個Apache的[開源]實現IntHashSet。我更喜歡apache實現，雖然它有一些開銷[它被實現爲IntToIntMap]

來源

2012-03-17 21:27:23 amit

您可能想看看BitSet Lucene中使用的那個更像標準Java實現，因爲它更快忽略了一些標準的邊界檢查。

來源

2012-03-17 21:44:16

我的第一個迴應wqas一個位集，但後來認識到，由於散列碼高達2^31，如果包括非常低的值（接近0）和大（接近MAXINT），大小可能是巨大的。 Alsom，你需要兩個Bitset，一個用於正數，一個用於負數，一個用於負數 – user949300 2012-03-18 03:04:45

@ user949300，如果你需要兩個BitSets，那麼每個將保存一半位，並且存儲2^32位需要2^29個字節 - 大但不是不可能。我認爲布盧姆過濾器從不同的答案將是一個更好的解決方案，因爲它可以實現更低的內存使用率和更高的拒絕誤報率。 – 2014-12-17 22:19:32

儘管Jon Skeet的回答爲小投資節省了很多錢，但我認爲你可以做得更好。既然你的數字是相當均勻分佈的，你可以使用內插搜索來更快的查找（大概O（log log N）而不是O（log N））。對於一百萬個項目，您大概可以計劃大約4個比較，而不是大約20個。

如果您想再做一點工作以將內存（大致）再次削減一半，則可以將其構建爲兩個級查找表，基本上是一種簡單版本的trie。

enter image description here

你會打破你的（大概）32位整數分成兩個16位部分。您將使用前16位作爲查找表第一級的索引。在這個級別上，你會有65536個指針，每個可能的16位值用於你的整數部分。那會帶你到桌子的第二層。對於這一部分，我們將在所選指針和下一個指針之間進行二進制或內插搜索 - 即第二級中所有在前16位具有相同值的值。然而，當我們查看第二個表格時，我們已經知道該值的16位 - 因此，不是存儲該值的所有32位，我們只需要存儲該值的其他012位數據的其他012位存儲器位。

這意味着，而不是第二級佔用4兆字節，我們已經減少到2兆字節。除此之外，我們需要第一級表，但它只有65536x4 = 256K字節。

這幾乎肯定會提高整個數據集二進制搜索的速度。在最壞的情況下（使用二進制搜索第二級），我們可以進行多達17次比較（1 + log 65536）。但平均值會比這更好 - 因爲我們只有一百萬個項目，所以每個第二級「分區」中的平均值只能是1_000_000/65536 =〜15個項目，給出大約1 + log （ 16）= 5比較。在第二級使用內插搜索可能會進一步減少這一點，但是當您僅從5次比較開始時，就沒有太多餘地進行真正的重大改進。由於第二級平均只有15個項目，所以你使用的搜索類型不會有太大的變化 - 即使是線性搜索也會非常快。

當然，如果你想要更進一步，可以使用4級表（而不是整數中的每個字節）。然而，這是否會爲你節省更多的費用以避免麻煩，這是值得商榷的。至少從目前來看，我的猜測是你會做相當多的額外工作以節省很少的成本（只是存儲百萬個整數的最後一個字節顯然佔用1兆字節，並且三個級別的表導致了這一點佔用相當多的金額，所以你可以將數量增加一倍，以節省大約半個兆字節的數量。如果你處於一個稍微節省一點的情況下會產生巨大影響的情況，那就去做吧 - 但除此之外，我懷疑返回是否會證明額外投資。

來源

2012-03-17 22:47:11

確實很好的優化。我想，一旦我的數據量增加了一個/兩個數量級，它就會派上用場。 – 2012-03-19 22:42:54