摘要：

判断目标值是否在一个大的集合中是比较常见的业务场景，相应的解决方案有很多，比如大的Hash表、Byte数组、BitSet等方案。当集合非常大的时候，这些方案在内存占用方面都比较大。BitSet方案相对比较可行。

BloomFilter是解决这种问题最好的方案，它在内存占用、查询性能等方面都是最优秀的，但是它有一定的误判概率，这种误判概率是可以接受的。

假设我们有这样的一个业务逻辑：

我们有一个网站，并且网站的流量和独立用户数非常大。当有用户访问我们网站的时候，我们需要判断该用户是否是第一次访问我们的网站。这是一个很场景的业务场景，我们可以想到以下两种方案来解决该问题。

一、Hash表来存储每个用户的IP

当有用户访问网站发送请求的时候，我们把用户的IP存到一张Hash表中。当有用户发送访问请求的时候，我们先去Hash表中找该IP，如果可以找到，则证明用户访问过。Hash表的存取时间复杂度都是O(1)，效率很高。

这种方案看似没什么问题，但是前提是网站的独立用户数不大。如果网站的独立用户数非常大，我们假设达到了1个亿。那这1个亿的IP Hash值需要多大的内存空间呢？每个ip的长度是15，一共需要15 * 100000000 = 1500000000Bytes = 1.4G，这还没考虑hash冲突的问题（hash表中的槽位越多，越浪费空间，槽位越少，效率越低）。

二、IP转换成无符号的int型值来存储

Hash表占用太大的内存空间，为了节省内存空间。我们可以把ip转换成无符号的int型值来存储，这样一个ip只需要占用4个字节就行了，这时1亿个ip占用的空间是4 * 100000000 = 400000000Bytes = 380M，空间消耗降低了很多。

除了以上两种方法，我们还有没有其其它更好的方法呢？有，BitSet。

三、BitSet

32位无符号int型能表示的最大值是4294967295，所有的ip都在这个范围内，我们可以用一个bit位来表示某个ip是否出现过，如果出现过，就把代表该ip的bit位置为1，那么我们最多需要429496729个bit就可以表示所有的ip了。

举个例子比如127.0.0.1转换成int是167772161，那么把长度为4294967295的bit数组的第167772161个位置置为1即可，当有ip访问时，只需要检查该标志位是否为1就行了。

<code>4294967295bit = 536870912Byte = 512M/<code>

如果用hash表示所有4294967295范围内的数组的话，需要十几G的空间。

我们来看看BitSet具体怎样实现。

首先，比如我们有一个长度=2的byte数组，2个字节一共有16位，可以表示0-15的数字是否存在。比如我们要验证11是否出现过，那么我们先检查第11个位置是否为1，如果为0，说明11没出现过，然后我们把第11位置为1，表示11已经出现过了

所以，BitSet基本只有两个操作，set(int value) 和 isHas(int value)

set(int value)

我们先来看set怎么实现，因为一个byte占8位，所以对于一个给定的value，我们先求出该value应该位于哪个Byte上，这很简单，

<code> int byteIndex = value / 8/<code>

找到value在byte数组中的位置后，再就是在该字节中寻找表示value的bit位，我们知道，一个byte其实就是一个长为8的bit数组，那么value在该bit数组中的位置也就很好算了

<code>int bitIndex = value % 8;/<code>

最后我们把该bit位设置为1就可以了

<code>byte[byteIndex] = byte[byteIndex] | 1 << ( 7 - bitIndex)

/<code>

<code>public void set(int value){

int byteIndex = value / 8;

int bitIndex = value % 8;

byte[byteIndex] = byte[byteIndex] | 1 << (7 - bitIndex)

}/<code>

isHas(int value)

<code>public boolean isHash(int value){

int byteIndex = value / 8;

int bitIndex = value % 8;

return byte[byteIndex] & 1 << (7 - bitIndex) > 0 


}/<code>

BitSet的局限性

BitSet有两个比较局限的地方：