昨天，在跟同学&同事谈人生谈理想的时候。他告诉我他学长面试头条，其中一道题是如何判断一个整数在不在40亿整数集中；他说他学长竟然不知道bitmap(原题链接)!!!然后我又给他科普了一下布隆过滤器和布谷鸟过滤器。
所以借此文章来记录一下这些知识，并巩固一下。

Bitmap

Bitmap，直译就叫位图。可以理解为通过一个bit数组存储特定数据的一种数据结构；由于bit是数据的最小单位，所以这种数据结构往往是非常节省存储空间的。在Java和Redis中都存在同名实现结构。
在一个记录只有两种状态，是或不是的场景下，如果使用其他数据结构存储则会存在大量空间空间的浪费。即使存在海量的数据，我们也只需要为每个数据分配1byte的空间就可以记录了。比如：用户画像
Bitmap可以节省大量的存储空间，所以可以很容易的倍一次性加载到内存中。Bitmap结构还有一个很重要的特点:可以很方便的进行位运算
比如我们需要统计用户满足以下条件的用户：程序员、带眼镜、长头发。。。。那么我们可以将对相应条件的用户画像的Bitmap结构做AND操作，就可以方便的过滤出满足条件的对象了。

Bitmap的优化

假如一个Bitmap中只有稀疏的那个几个1，那么其他空间是不是就被浪费了呢？

谷歌开发的EWAHComressedBitmap对Bitmap存储空间做了一定的优化操作。

EWAH把Bitmap存储在一个long数组中，long数组的每一个元素都可以当做64位的二进制数，也就是整个Bitmap的子集，称为Word。
当创建一个空的Bitmap时，只有4个Word，也就是只有4个long数组，随着数据的不断插入，Word数组会随着进行扩容。
Word节点分为两种，直接存储数据的叫做Literal Word，简称LW。存储跨度信息的叫Running Length Word，简称RLW。
每一个RLW分为两部分，低32位表示当前Word横跨了多少个空Word，高32位表示当前RLW后面又多少个连续的LW。这样即使存在很多个0的位置，也能进行合并，减少浪费。

Bloom Filter

Bitmap适合处理按顺序字段映射，如ID。但是当遇到其他情况时就无能为力了，比如判断一个单词是否存在于单词集中，这个时候如果需要映射的话，只能够对该单词进行相应的hash计算后映射到Bitmap上，But！绝大情况下会存在hash冲突，无法确认是不是。

于是便引入了布隆过滤器。布隆过滤器也不能完全的消除误差。只能说大大的减少了误差率。

布隆过滤器的原理就是将需要判断的对象进行多次不同的hash计算后，同时判断那几位是否都为1，由此可见，布隆过滤器的误差率取决于hash函数的选取。

Cuckoo Filter

布隆过滤器存在一个致命的缺点，那就是已经置为1的位不能再重置为0。这是因为你并不能判断该位具体被多少个对象映射了。只能在你认为误差率已经不能接受时进行重建。

我也是最近才了解到有布谷鸟过滤器的存在。

布谷鸟哈希

最简单的布谷鸟哈希结构时一维数组结构，会有两个hash算法将新来的元素映射到数组的两个位置。如果两个位置中有一个位置为空，那么就可以把元素放进去；但是如果这两个位置都满了，那么会随机踢走一个，然后自己霸占这个位置。
被踢走的那个元素会寻找其他位置，重复上面的行为。知道所有的元素都找到了对应的位置。

1 2	p1 = hash1(x) % l p2 = hash2(x) % l

布谷鸟算法为了避免重复踢的这个过程执行次数过多，会设置一个阈值，如果执行次数超过这个值，那么就会进行扩容操作，重新放置所有的元素。

布谷鸟过滤器

布谷鸟过滤器和布谷鸟哈希结构一样，也是一维数组，但是不同于布谷鸟哈希的是，布谷鸟哈希会存储整个元素，而布谷鸟过滤器只会储存元素的指纹信息（只有几个bit，类似于布隆过滤器）。

首先布谷鸟过滤器还是只会选用两个 hash 函数，但是每个位置可以放置多个座位。这两个 hash 函数选择的比较特殊，因为过滤器中只能存储指纹信息。当这个位置上的指纹被挤兑之后，它需要计算出另一个对偶位置。

1
2
3

fp = fingerprint(x)
p1 = hash(x)
p2 = p1 ^ hash(fp)  // 异或

我们可以看出p1和p2具有对偶性。所以我们根本不需要知道当前的位置是 p1 还是 p2，只需要将当前的位置和 hash(fp) 进行异或计算就可以得到对偶位置。而且只需要确保 hash(fp) != 0 就可以确保 p1 != p2，如此就不会出现自己踢自己导致死循环的问题。

由于布谷鸟过滤器保证了一个byte只被一个元素映射，所以允许删除操作，但是会存在误删的情况。

http://blog.talkingdata.net/?p=2493
https://juejin.im/post/5c4fd2af51882525da267385
https://cloud.tencent.com/developer/article/1447177