元素算法Bloom Filter

最近研究元素算法，稍微总结一下，以后继续补充：

快速判断item是否存在于一个集合中。hbase使用bloomfilter算法，用blockID去regionMeta中判断是否分布在某个region中。

http://www.eecs.harvard.edu/~michaelm/NEWWORK/postscripts/BloomFilterSurvey.pdf

核心要点：

使用hash，增加状态位的存储容量
使用多次hash，增加hash冲突，增加误判律
掷中bloomfilter，不代表元素必定存在。但不掷中bloomfilter，代表元素必定不存在。
适用于90％情况下不掷中的场景

算法：

int maxKeys = 100000;// 最多元素个数
float errorRate = 0.001f; // 错误率
int foldFactor = 8; // 规整因子

int bitSize = (int) Math.ceil(maxKeys
        * (Math.log(errorRate) / Math.log(0.6185)));
int functionCount = (int) Math.ceil(Math.log(2) * (bitSize / maxKeys));

int byteSize = (bitSize + 7) / 8; // 转换为字节单位
int mask = (1 << foldFactor) - 1;
if ((mask & byteSize) != 0) {
    byteSize >>= foldFactor;
    ++byteSize;
    byteSize <<= foldFactor;
}

bloomFilter的字节巨细，和maxKeys相关。而hash次数和错误率相关

每日一道理
生命不是一篇"文摘"，不接受平淡，只收藏精彩。她是一个完整的过程，是一个"连载"，无论成功还是失败，她都不会在你背后留有空白；生命也不是一次彩排，走得不好还可以从头再来，她绝不给你第二次机会，走过去就无法回头。

maxKeys, errorRate	0.1	0.01	0.001
1000	768byte, func = 3	1280byte, func=7	2048byte,func=10
10000	6144byte, func=3	12032byte, func=7	18176byte, func=10
100000	60160byte, func= 3	120064byte, func=7	179968byte, func = 10

添加元素：

http://www.eecs.harvard.edu/~kirsch/pubs/bbbf/esa06.pdf

int hash1 = this.hash.hash(buf, offset, len, 0);
int hash2 = this.hash.hash(buf, offset, len, hash1);

for (int i = 0; i < this.hashCount; i++) {
    int hashLoc = Math.abs((hash1 + i * hash2) % (this.byteSize * 8));
    set(hashLoc);
}

this.keyCount.incrementAndGet();

简略描述为：两次hash值，以第一次为基准，第二次为步长停止打点。

文章结束给大家分享下程序员的一些笑话语录：问答
Q：你是怎么区分一个内向的程序员和一个外向的程序员的？ A：外向的程序员会看着你的鞋和你说话时。
Q：为什么程序员不能区分万圣节和圣诞节？ A：这是因为 Oct 31 == Dec 25！（八进制的 31==十进制的 25）