问一个bloom filter 和 bitmap的使用区别# JobHunting - 待字闺中
l*y
1 楼
我是在看
http://www.mitbbs.com/article/JobHunting/31491461_3.html
bloom filter可以看做是对bit-map的扩展。
我原来的想法是bloom filter要比bit map省空间，因为bloom filter设计的思想就是
用错误率换空间。但是看了那个帖子里的两道题，又迷茫了不少。
问题1：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让
你找出A,B文件共同的URL。
建议答案：根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿
，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差
并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换
成ip，则大大简单了。
问题2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出
现2次及以上。或者我们不用2bit来进行表示，我们用
http://www.mitbbs.com/article/JobHunting/31491461_3.html
bloom filter可以看做是对bit-map的扩展。
我原来的想法是bloom filter要比bit map省空间，因为bloom filter设计的思想就是
用错误率换空间。但是看了那个帖子里的两道题，又迷茫了不少。
问题1：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让
你找出A,B文件共同的URL。
建议答案：根据这个问题我们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿
，n=50亿，如果按出错率0.01算需要的大概是650亿个bit。现在可用的是340亿，相差
并不多，这样可能会使出错率上升些。另外如果这些urlip是一一对应的，就可以转换
成ip，则大大简单了。
问题2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出
现2次及以上。或者我们不用2bit来进行表示，我们用