此問題已被多次詢問，但建議的答案並不完全是我正在尋找的。按位操作查找數組中是否存在數字
問：有沒有辦法找出一個數組是否包含給定的 數字？
假設：數組中的元素保證爲唯一的 。該數組沒有超出範圍的所有元素。陣列 是無序的。編寫數組的程序是 執行檢查的程序。所以在寫入數組之前，它可以執行一些預處理以保存在內存中。
我試圖想出一種方法，不需要在內存中保存元素，也不需要從小塊中加載磁盤中的元素。是否有類似於「按位異或方法在數組中尋找1個重複元素的方法」。原因是：我有組中的數字並存儲在磁盤上，我只想加載具有該數字的組。我正在尋找類似於組中所有元素的異或的內容，然後根據手頭的數字和異或值確定組中是否有數字。
你可以用基於哈希表的bloom filter來概率地做到這一點。
散列表的工作方式是將元素存儲在數組中，並由元素的散列索引。在存儲數字時，例如，您可以採用數字x％10。然後，你的哈希表可能有10個插槽可以放10個數字。
在這種情況下，您只想知道數字是否存在，因此每個插槽可能只需要一個插槽。使用這個簡單的例子，如果一個組包含數字{5,17,18,76}，則具有10比特的散列表將具有設置在索引5,6,7,8處的比特，並且其他比特將是然後，當你想知道這個組是否有91，你就會知道這個組沒有這個數字。但是，如果您想知道該組是否具有數字35，則會發現該位已設置。在這種情況下，您只知道該組可能有有此號碼。這種不確定性是由於兩個不同的元素恰好具有相同的散列而導致的，這是由於散列衝突造成的。您可以通過增大散列表來減少這種不確定性，以便有更多的潛在哈希值，並減少碰撞的機會。然而，即使你的散列表非常大，這仍然有一個不平凡的錯誤潛力，例如。 1000-10,000個插槽。
bloom濾波器有助於進一步降低這種不確定性，同時最大限度地減少所需的內存（插槽）。在簡單哈希表中，對於插入的每個元素，只需在散列表中設置1位，使用布隆過濾器即可在散列表中設置多個位。要做到這一點，你有多個散列函數，例如。 f(x), g(x), h(x), ...，它告訴你要設置哪些位。
在具有三個散列函數和20個插槽的示例中，您可能有f(x)=x%20，g(x)=floor(x/20)%20，h(x)=((x%7)+f(x))%20。假設你要插入3號 - 35，171，82到哈希表，那麼你將設置以下位：
現在，假設要檢查，如果數字80是存在的。相關位爲：0,4,3。您注意到雖然位0和位4已設置，但位3不是，因此您知道80不在組中。
如果您選擇最佳散列函數的數量，則在布隆過濾器中需要每個元素少於10位，誤報率爲1％。使用每個元素3-5位，您仍然可以獲得<〜50％的誤報率。由於我們正在計數位，因此可以很容易地使用1024位布隆過濾器（使用相當於32個4字節整數的內存），並存儲100-200個元素，同時仍然具有非常低的誤報率。
嗯有趣.. – broun
因此，您有一個未定義的編程語言的數組，並且您希望對整個數組執行按位操作，而無需從磁盤加載文件或將任何內容放入內存中？我不確定你想要做什麼。 – GolezTrol
我使用cpp，但不知道爲什麼它在這種情況下很重要。我想加載只有手頭有數字的數組，我需要在加載之前找到哪個數組。我想盡可能地減少內存使用量，而不是將任何內容都放在內存中。 – broun
你必須加載一些東西來檢查它的值。你不能問硬盤在位置x是否有值（更不用說在文件中）。你必須把它加載到內存中並檢查那裏的值。你可以用塊來做到這一點，以節省內存，但你必須處理文件。另外，如果您找到了不適合您的解決方案，請提及它們。也許我們可以幫助讓他們爲你跑步。 – GolezTrol