代碼精讀 LevelDB 布隆濾波器
簡介–布隆濾波器 BloomFilter 是一種常用的「使用少量字節數判斷鍵值存在性」的手段。其大致原理爲：使用多個哈希函數，對同一個鍵值做哈希運行，並將其哈希值取模設置比特數值。當給定一個鍵值時，如果計算上述多個哈希函數，存在一個哈希值對應的比特位爲零，則說明該鍵值不存在。從上可以發現，BloomFilter 常用於判斷鍵的不存在性。由於哈希碰撞的原因，可能存在假陽性 (False Posit ⌘ Read more