檢查現有值時避免使用數據庫

Question

通過哈希或按位運算符或其他算法避免在僅檢查以前出現的字符串或值時使用數據庫，有沒有辦法？ 假設，沒有辦法存儲以前出現的字符串的整個歷史，只能存儲很少的信息。

Answer 1

您可能感興趣的布盧姆過濾器。他們不會讓你權威地說，「是的，這個價值是在利益集合中」，但他們確實讓你說「是的，這個價值是可能是在集合」vs.「不，這個價值肯定是不是中的集合「。對於很多情況，這足夠有用。

它的工作方式是：

• 創建布爾值的陣列（即比特）。你能夠承受的數量越多，效果越好。
• 您創建了一堆不同的散列函數，每個散列函數獲取一個輸入字符串並將其映射到數組的一個元素。你希望這些哈希函數是獨立的，這樣即使一個哈希函數將兩個字符串映射到同一個元素，一個不同的哈希函數也很可能將它們映射到不同的元素。
• 要記錄一個字符串是否在集合中，您將其中的每個散列函數應用於其中，然後—向您提供數組—中的一組元素，並將所有映射元素設置爲TRUE。
• 要檢查一個字符串是否（可能）在該集合中，除了現在只檢查映射元素以查看它們是否爲TRUE之外，您可以做同樣的事情。如果它們都是TRUE，那麼該字符串可能在集合中;否則，它絕對不是。

如果你有興趣在這種方法中，看到https://en.wikipedia.org/wiki/Bloom_filter進行詳細的分析，可以幫助你調整適當過濾（選擇正確的數組大小和散列函數的數量），以獲得有用的概率。