Bloom Filter 和 Cuckoo Filter有类似的用途，很多人将它们称为概率数据结构或者近似成员数据结构(approximate membership data structure)。最近看了一个Bloom Filter和一个Cuckoo Filter的比较好的实现，代码都是用C++实现，代码量也不大，读起来没有什么难度。 本文贴出来的是两个项目的大体构成，不涉及到空间、错误率等的理论分析，希望能给需要的新手一些帮助。 两个项目的网址如下： C++ Bloom filter library: https://code.google.com/p/bloom/ Cuckoo Filter: https://github.com/efficient/cuckoofilter 1. Bloom Filter (https://code.google.com/p/bloom/) 源码目录： $ tree . ├── Makefile ├── bloom_filter.hpp ├── bloom_filter_example01.cpp ├── bloom_filter_example02.cpp ├── bloom_filter_example03.cpp ├── random-list.txt ├── word-list-extra-large.txt ├── word-list-large.txt └── word-list.txt 文件包括三个用于测试example、三个用于测试insert的txt词典，bloom filter的实现在bloom_filter.hpp中。 bloom_filter.hpp中包括3个class：bloom_parameters、bloom_filter和compressible_bloom_filter。其中bloom_parameters是构建一个BF需要的参数，compressible_bloom_filter 类继承自bloom_filter类。 1.1 bloom_filter.hpp bloom_parameters 包含的成员： // […]