- 哈希函數的個數 k：
【戀上資料結構(2)，40張圖文詳解，我就不信你還參透不了并發程式設計
布隆過濾器的實作
===========================================================================
Guava: Google Core Libraries For Java（谷歌核心庫中Java實作）
- https://mvnrepository.com/artifact/com.google.guava/guava
布隆過濾器的基礎操作有兩個：添加元素、查詢元素是否存在
/**
* 添加元素
* @return true代表bit發送了變化
*/
boolean put(T value);
/**
* 查詢元素是否存在
* @return false代表一定不存在, true代表可能存在
*/
boolean contains(T value);
布隆過濾器的構造
根據上面的公式可知，布隆過濾器必然有2個全局變量：
-
bitSize
-
hashSize
并且必然有個容器來存儲這些二進制位：
-
bits
long[]
long
bit
int[]
package com.mj;
public class BloomFilter<T> {
/**
* 二進制向量的長度(一共有多少個二進制位)
*/
private int bitSize;
/**
* 二進制向量
*/
private long[] bits;
/**
* 哈希函數的個數
*/
private int hashSize;
/**
* 布隆過濾器的構造
* @param n 資料規模
* @param p 誤判率, 取值範圍(0, 1)
*/
public BloomFilter(int n, double p){
if (n <= 0 || p <= 0 || p >= 1) { // 非法輸入檢測
throw new IllegalArgumentException("wrong n or p");
}
// 根據公式求出對應的資料
double ln2 = Math.log(2);
// 求出二進制向量的長度
bitSize = (int) (- (n * Math.log(p)) / (ln2 * ln2));
hashSize = (int) (bitSize * ln2 / n);
// bits數組的長度
bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE]; // 分頁公式
// (64 + 64 - 1) / 64 = 127 / 64 = 1
// (128 + 64 - 1) / 64 = 2
// (130 + 64 - 1) / 64 = 3
// 分頁問題:
// 每一頁顯示100條資料, pageSize = 100
// 一共有999999條資料, n = 999999
// 請問有多少頁 pageCount = (n + pageSize - 1) / pageSize
};
}
測試一下，假設有1億個資料，要求誤判率為1%：
可以得到哈希函數的個數為 6，二進制位的個數是 958505837。
public static void main(String[] args) {
BloomFilter<Integer> bf = new BloomFilter<>(1_0000_0000, 0.01);
// 哈希函數的個數: 6
// 二進制位的個數: 958505837
}
布隆過濾器 - 添加元素
設定指定位置元素的二進制值為1
比如要設定
100000
的 第2位bit 為 1，應當
100000 | 000100
，即
100000 | (1 << 2)
；
100000
| 000100 == (1 << 2)
------------------
100100
那麼設定
value
的 第index位bit為 1，則是
value| (1 << index)
；
/**
* 設定index位置的二進制為1
*/
private boolean set(int index){
// 對應的long值
long value = bits[index / Long.SIZE];
int bitValue = 1 << (index % Long.SIZE);
bits[index / Long.SIZE] = value | bitValue;
return (value & bitValue) == 0;
}
有了以上基礎，可以實作布隆過濾器的添加元素操作：
/**
* 添加元素
*/
public boolean put(T value) {
nullCheck(value);
// 利用value生成 2 個整數
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
boolean result = false;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 生成一個二進制的索引
int index = combinedHash % bitSize;
// 設定第index位置的二進制為1
if (set(index)) result = true;
// 101010101010010101
// | 000000000000000100 1 << index
// 101010111010010101
}
return result;
}
布隆過濾器 - 判斷元素是否存在
檢視指定位置的二進制的值
比如要檢視
10101111
的 第2位bit 為 1，應當
10101111 & 00000100
，即
10101111 & (1 << 2)
，隻有指定位置的二進制的值為 0，傳回值才會是 0，否則為 1；
10101111
& 00000100 == (1 << 2)
--------------
00000100 != 0, 說明index位的二進制為1
那麼擷取
value
的 第index位bit 的值，則是
value & (1 << index)
；
/**
* 檢視index位置的二進制的值
* @param index
* @return true代表1, false代表0
*/
private boolean get(int index) {
// 對應的long值
long value = bits[index / Long.SIZE];
return (value & (1 << (index % Long.SIZE))) != 0;
}
有了以上基礎，可以實作布隆過濾器的判斷一個元素是否存在操作：
/**
* 判斷一個元素是否存在
*/
public boolean contains(T value) {
nullCheck(value);
// 利用value生成2個整數
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 生成一個二進制的索引
int index = combinedHash % bitSize;
// 查詢第index位置的二進制是否為0
if (!get(index)) return false;
// 101010101010010101
// | 000000000000000100 1 << index
// 101010111010010101
}
return true;
}
布隆過濾器 - 完整代碼
===============================================================================
package com.mj;
public class BloomFilter<T> {
/**
* 二進制向量的長度(一共有多少個二進制位)
*/
private int bitSize;
/**
* 二進制向量
*/
private long[] bits;
/**
* 哈希函數的個數
*/
private int hashSize;
/**
* 布隆過濾器的構造
* @param n 資料規模
* @param p 誤判率, 取值範圍(0, 1)
*/
public BloomFilter(int n, double p){
if (n <= 0 || p <= 0 || p >= 1) { // 非法輸入檢測
throw new IllegalArgumentException("wrong n or p");
}
// 根據公式求出對應的資料
double ln2 = Math.log(2);
// 求出二進制向量的長度
bitSize = (int) (- (n * Math.log(p)) / (ln2 * ln2));
hashSize = (int) (bitSize * ln2 / n);
// bits數組的長度
bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE]; // 分頁公式
// (64 + 64 - 1) / 64 = 127 / 64 = 1
// (128 + 64 - 1) / 64 = 2
// (130 + 64 - 1) / 64 = 3
// 分頁問題:
// 每一頁顯示100條資料, pageSize = 100
// 一共有999999條資料, n = 999999
// 請問有多少頁 pageCount = (n + pageSize - 1) / pageSize
};
/**
* 添加元素
*/
public boolean put(T value) {
nullCheck(value);
// 利用value生成2個整數
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
boolean result = false;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
// 生成一個二進制的索引
int index = combinedHash % bitSize;
// 設定第index位置的二進制為1
if (set(index)) result = true;
// 101010101010010101
// | 000000000000000100 1 << index
// 101010111010010101
}
return result;
}
/**
* 判斷一個元素是否存在
*/
public boolean contains(T value) {
nullCheck(value);
// 利用value生成2個整數
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
### 筆者福利
##### 以下是小編自己針對馬上即将到來的金九銀十準備的一套“面試寶典”，不管是技術還是HR的問題都有針對性的回答。
**有了這個，面試踩雷？不存在的！**
##### 需要這套“面試寶典”的，[點選這裡即可免費擷取](https://gitee.com/vip204888/java-p7)！回饋粉絲，誠意滿滿！！！
public boolean contains(T value) {
nullCheck(value);
// 利用value生成2個整數
int hash1 = value.hashCode();
int hash2 = hash1 >>> 16;
for (int i = 1; i <= hashSize; i++) {
int combinedHash = hash1 + (i * hash2);
if (combinedHash < 0) {
combinedHash = ~combinedHash;
}
### 筆者福利
##### 以下是小編自己針對馬上即将到來的金九銀十準備的一套“面試寶典”，不管是技術還是HR的問題都有針對性的回答。
**有了這個，面試踩雷？不存在的！**
##### 需要這套“面試寶典”的，[點選這裡即可免費擷取](https://gitee.com/vip204888/java-p7)！回饋粉絲，誠意滿滿！！！
[外鍊圖檔轉存中...(img-GirafzGd-1628428344406)]
[外鍊圖檔轉存中...(img-ec81i51t-1628428344407)]
[外鍊圖檔轉存中...(img-GJE893Ve-1628428344408)]
![Java String.format方法的簡單使用[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)