1
2
3
4
5
6

<!--  引入 guava 依赖  -->      
<dependency>        
    <groupId>com.google.guava</groupId>        
    <artifactId>guava</artifactId>        
	<version>30.1-jre</version>      
</dependency>      

1
2
3
4

public static <T> BloomFilter<T> create(        
    Funnel<? super T> funnel, int expectedInsertions, double fpp) {        
  return create(funnel, (long) expectedInsertions, fpp);        
}      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

	/**        
	 * 预计要插入多少数据 958,5058 100,0000        
	 */      
	 private static final int size = 1000000;        
	        
	/**        
	 * 期望的误判率        
	 */        
	private static final double fpp = 0.01;        
	        
	/**        
	 * 布隆过滤器        
	 */        
	private static final BloomFilter<Integer> bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

public static void main(String[] args) throws Exception {        
    Class<BloomFilter> bloomFilterClass = BloomFilter.class;        
            
    // 获取哈希函数个数        
    Field numHashFunctions = bloomFilterClass.getDeclaredField("numHashFunctions");        
    numHashFunctions.setAccessible(true);        
    System.out.println("哈希函数个数 = " + numHashFunctions.get(bloomFilter));        
        
    // 获取数组长度        
    Method optimalNumOfBits = bloomFilterClass.getDeclaredMethod("optimalNumOfBits", long.class, double.class);        
    optimalNumOfBits.setAccessible(true);        
    System.out.println("布隆过滤器大小 = " + optimalNumOfBits.invoke(bloomFilter, size, fpp));        
            
    // 插入10万样本数据        
    for (int i = 0; i < size; i++) {        
        bloomFilter.put(i);        
    }        
        
    // 用另外十万没被插入的数据测试数据，测试误判率        
    int count = 0;        
    for (int i = size; i < size + 100000; i++) {        
        if (bloomFilter.mightContain(i)) {        
            count++;        
        }        
    }        
    System.out.println("误判率:" + (double)count / 100000);        
}      

1
2
3

哈希函数个数 = 7      
布隆过滤器大小 = 9585058      
误判率:0.00947      

1
2
3
4
5

Add(item): 将元素插入过滤器。      
Contain(item): 如果元素已在过滤器中，则返回。请注意，和布隆过滤器一样，此方法可能会误报。      
Delete(item): 从过滤器中删除给定的项目。请注意，要使用此方法，必须确保此项目在过滤器中;否则，可能会误删。      
Size(): 返回过滤器中当前项目的总数。      
SizeInBytes(): 返回过滤器大小，单位为字节。      

1
2
3
4
5
6
7
8
9

fp = getFingerprint(x);      
p1 = hash1(x);      
insert(p1);      
if (失败) {      
	// hash2 保证，hash2(p2, fp) == p1      
	p2 = hash2(p1, fp);      
	insert(p2);      
	if (再次失败) 执行驱逐代码      
}      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

template <typename ItemType, size_t bits_per_item,        
          template <size_t> class TableType, typename HashFamily>        
Status CuckooFilter<ItemType, bits_per_item, TableType, HashFamily>::Add(        
    const ItemType &item) {        
  size_t i;  // p1      
  uint32_t tag; // 指纹       
        
  if (victim_.used) {        
  // 检测是否还有空间      
    return NotEnoughSpace;        
  }        
        
  GenerateIndexTagHash(item, &i, &tag);        
  return AddImpl(i, tag);        
}      
      
// 计算索引 1 和 指纹 tag      
inline void GenerateIndexTagHash(const ItemType& item, size_t* index,        
                                 uint32_t* tag) const {        
  const uint64_t hash = hasher_(item);        
  *index = IndexHash(hash >> 32);        
  *tag = TagHash(hash);        
}      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

template <typename ItemType, size_t bits_per_item,        
          template <size_t> class TableType, typename HashFamily>        
Status CuckooFilter<ItemType, bits_per_item, TableType, HashFamily>::AddImpl(        
    const size_t i, const uint32_t tag) {        
  size_t curindex = i;  // 当前插入元素的下标      
  uint32_t curtag = tag;  // 当前插入元素的指纹      
  uint32_t oldtag;  // 暂存被驱逐的元素指纹      
        
  for (uint32_t count = 0; count < kMaxCuckooCount; count++) {        
    bool kickout = count > 0;  // 驱逐开始的时机：计算替代索引之后      
    oldtag = 0;        
    if (table_->InsertTagToBucket(curindex, curtag, kickout, oldtag)) {        
	// 插入成功的话，计数      
      num_items_++;        
      return Ok;        
    }        
    // 如果没有插入，说明需要驱逐，将 curtag 设置为被驱逐的元素      
    if (kickout) {        
      curtag = oldtag;        
    }        
    // 计算替代索引      
    curindex = AltIndex(curindex, curtag);        
  }        
  // 如果最终还没有插入成功，视为满了，做些善后工作      
  victim_.index = curindex;        
  victim_.tag = curtag;        
  victim_.used = true;        
  return Ok;        
}      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

inline bool InsertTagToBucket(const size_t i, const uint32_t tag,        
                              const bool kickout, uint32_t &oldtag) {        
  for (size_t j = 0; j < kTagsPerBucket; j++) {        
    if (ReadTag(i, j) == 0) {        
      WriteTag(i, j, tag);        
      return true;        
    }        
  }        
  if (kickout) {        
    size_t r = rand() % kTagsPerBucket;        
    oldtag = ReadTag(i, r);        
    WriteTag(i, r, tag);        
  }        
  return false;        
}      

1
2
3
4
5

inline size_t AltIndex(const size_t index, const uint32_t tag) const {        
  // NOTE(binfan): originally we use:        
  // index ^ HashUtil::BobHash((const void*) (&tag), 4)) & table_->INDEXMASK;  // now doing a quick-n-dirty way:  // 0x5bd1e995 is the hash constant from MurmurHash2        
  return IndexHash((uint32_t)(index ^ (tag * 0x5bd1e995)));        
}      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22

template <typename ItemType, size_t bits_per_item,        
          template <size_t> class TableType, typename HashFamily>        
Status CuckooFilter<ItemType, bits_per_item, TableType, HashFamily>::Contain(        
    const ItemType &key) const {        
  bool found = false;        
  size_t i1, i2;        
  uint32_t tag;        
        
  GenerateIndexTagHash(key, &i1, &tag);        
  i2 = AltIndex(i1, tag);        
        
  assert(i1 == AltIndex(i2, tag));        
        
  found = victim_.used && (tag == victim_.tag) &&        
          (i1 == victim_.index || i2 == victim_.index);        
        
  if (found || table_->FindTagInBuckets(i1, i2, tag)) {        
    return Ok;        
  } else {        
    return NotFound;        
  }        
}      

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

template <typename ItemType, size_t bits_per_item,        
          template <size_t> class TableType, typename HashFamily>        
Status CuckooFilter<ItemType, bits_per_item, TableType, HashFamily>::Delete(        
    const ItemType &key) {        
  // 生成索引      
  size_t i1, i2;        
  uint32_t tag;        
  GenerateIndexTagHash(key, &i1, &tag);        
  i2 = AltIndex(i1, tag);        
      
 // 尝试删除元素，删除成功的话，跳到 TryEliminateVictim 去尝试清楚受害者元素      
  if (table_->DeleteTagFromBucket(i1, tag)) {        
    num_items_--;        
    goto TryEliminateVictim;        
  } else if (table_->DeleteTagFromBucket(i2, tag)) {        
    num_items_--;        
    goto TryEliminateVictim;        
  } else if (victim_.used && tag == victim_.tag &&        
             (i1 == victim_.index || i2 == victim_.index)) {        
    // num_items_--;        
    victim_.used = false;        
    return Ok;        
  } else {        
    return NotFound;        
  }        
TryEliminateVictim:        
// 清除受害者      
  if (victim_.used) {        
    victim_.used = false;        
    size_t i = victim_.index;        
    uint32_t tag = victim_.tag;        
    AddImpl(i, tag);        
  }        
  return Ok;        
}