位运算
布隆过滤器
- 场景
网页黑名单系统
垃圾邮件过滤系统
爬虫的网址判断重复系统
容忍一定程度的失误率
对空间要求较严格 - 优势：使用很少的空间做到正确率很高
- 原理：
引入了k(k>1)个相互独立的哈希函数，对输入进行取哈希值，然后将结果对m取余（m为bitarray的长度），bitarray对应位置上的结果涂黑。
x,y,z经由哈希函数映射将各自在Bitmap中的3个位置置为1，当w出现时，仅当3个标志位都为1时，才表示w在集合中。 - 关键：
m如何确定大小？
由样本数量n和失误率p决定。
交换两个数的值
a = a^b;
b = a^b;
a = a^b;