最佳的數據結構來存儲大量的一位數據

Question

我要存儲大量數據，使

1. 他們可以通過索引來訪問，
2. 每個數據僅僅是yes和no（所以大概一個位對於每個都是足夠的）

我在尋找性能最高，佔用空間最小的數據結構。

可能將數據存儲在平面存儲器中，另一方面，每個數據一位不是一個好選擇，另一方面，使用不同類型的樹結構仍然使用大量內存（例如，即使使用每個節點中的指針每個節點只有一個數據位）。

有沒有人有任何想法？

Answer 1

在Java中的BitSet中可能是一個不錯的選擇http://download.oracle.com/javase/6/docs/api/java/util/BitSet.html

Answer 2

這有什麼錯用一個單獨的內存塊，要麼存儲每字節1位（容易索引，但每個字節廢物7位）或包裝數據（略微更復雜的索引，但更高的內存效率）？

Answer 3

如果我正確理解你的問題，你應該將它們存儲在一個無符號整數中，在那裏你將每個值賦給整數（標誌）的位。

說你代表3個值，他們可以打開或關閉。然後你將第一個分配給1，第二個分配給2，第三個分配給4.你的unsigned int可以是0,1,2,3,4,5,6或7，這取決於哪些值是打開或關閉的，你檢查該值使用按位比較。

Answer 4

取決於語言以及如何定義「索引」。如果你的意思是索引操作符必須工作，那麼你的語言將需要能夠超載索引操作符。如果您不介意使用索引宏或函數，則可以通過將給定索引除以類型中的位數來訪問第n個元素（例如，8表示char，32表示uint32_t和variant），然後返回arr[n/n_bits] & (1 << (n % n_bits))

Answer 5

看一看布隆過濾器：http://en.wikipedia.org/wiki/Bloom_filter

它執行得很好，是節省空間的。但請確保您閱讀下面的細則;-)：從上面的維基頁面引用。

空布隆過濾器是m位的位陣列 ，全部設置爲0。必須有 也有k個不同的散列函數 所定義，其中的每一個映射或散列 一些組元件中的所述一個m陣列 位置均勻隨機 分佈。要添加元素，請將 送到k個散列函數中的每一個函數中，以獲得k個陣列位置，即 。將所有這些位置的位設置爲 。爲了查詢 元素（測試它是否在 集合中），將其饋送到k個散列函數 中的每一個函數以獲得k個陣列位置。如果 這些位置上的任何位都是 0，則該元素不在該集合中 - 如果是 那麼它將在插入時將所有位設爲 。如果 全部爲1，則該組中的元素是 ，或者在插入其他 元素的過程中，該位已被設置爲 。設計不同的獨立散列函數 的要求可能對於大k是禁止的。對於具有寬輸出一個 良好散列函數， 應該有一點，如果這 散列類型這樣的散列的不同 位字段之間的任何 相關性，因此可用於通過產生 多個「不同」的散列函數 將其輸出切分爲多個位 字段。或者，可以將k 不同的初始值（例如0, 1，...，k-1）傳遞給 採用初始值的散列函數;或將這些值添加（或 附加）到密鑰。對於 散列函數中 更大m和/或K，獨立可與假陽性率 可忽略的增加（迪林格& Manolios（2004年）， 基爾希& Mitzenmacher（2006））被放寬。 具體地說，迪林傑& Manolios （2004年b），使用增強型雙散列或 三重散列，雙 散列的變體，以得到上兩個或三個 指數與獨立散列 計算使用 簡單的算術第k指數顯示的 有效性功能。從 刪除元素這個簡單的布隆過濾器是不可能的 。該元素映射到k 位，並且雖然將 中的任何一個設置爲零，但這些k位爲0就足夠了，可以將其刪除，但這會帶來 的副作用，即將 映射到該位上，我們沒有辦法 確定是否添加了任何這樣的元素 。這種刪除將導致可能的錯誤 否定，這是不允許的。 一次性從 布隆過濾器中刪除元素可以通過 模擬具有第二個布隆過濾器， 包含已被刪除的項目。 但是，第二個 過濾器中的誤報成爲 複合過濾器中的假陰性，但不允許 。在這種方法中，重新添加 之前刪除的項目不是 可能，因爲必須從「已刪除」過濾器中刪除 。但是， 通常情況下，所有密鑰 都可用，但對枚舉 （例如，需要很多 磁盤讀取）而言非常昂貴。當假陽性率太高時，過濾器可以重新生成 ;這應該是一個比較少見的事件。