使用位图做整型ID去重的一种方法

什么是位图算法

英文叫做bitmap，也有叫做bitset，Java SDK的util包中就包含一个BitSet的实现。

《编程珠玑》中提到一个位图算法的例子：

输入：一个文件，里面大约有1千万行数据，每个数据是7位整数，同时每个数是唯一的，即不允许有2个数相同，这些整数不与其他任何数产生关联。

输出：将这个整数按升序排列，并生成到一文件中

限制：能够使用内存为1M，但是附存足够大，运行时间最多为几分钟，10s为最合适的时间。

用位图算法解决可以这么做：用含有1千万个位的整型数组来表示这个文件，文件中有的数据则标识为1，没有则标识为0，最后从第一位读至最后一位，即为有序的集合。

利用位图算法过滤重复ID

首先阐述一下算法思路：

使用一个足够大的位图，每一位表示一个整数的ID，有ID需要处理前，去位图里面查找对应的位是否为0，0表示未处理过，等处理过后就置成1.比如现在有个位图，二进制是00000000，来个id值是3，那么我们需要把位图置成00001000，如果重复的id值3再过来，通过判断这个位图的第三位是1就知道已经处理过了。

。。。。

 

详情请到我的新博客：

http://xiaofengmetis.com/?p=60