布隆过滤器的核心逻辑是通过多个哈希函数将元素映射到固定长度的位数组中，标记对应状态位为1，查询时检查所有对应位是否都为1来判断元素可能存在。位运算可以直接操作二进制位，是实现状态位快速映射的最优选择，能避免额外的内存开销和计算耗时。
布隆过滤器底层状态位存储基础
布隆过滤器的状态位通常存储在位数组（BitSet）中，由于大多数编程语言没有原生的位数组类型，一般使用整数数组模拟，每个整数的每一位对应一个状态位。例如一个int类型占32位，长度为10的int数组可以存储320个状态位。
要实现状态位映射，首先需要明确两个核心问题：给定元素哈希后的位置，如何找到对应的数组索引，以及如何定位该索引整数中的具体位。
状态位到数组索引的计算
假设位数组总长度为bitSize，哈希函数计算出的位置为hashValue，那么对应的数组索引可以通过位运算快速计算：
// 假设使用int数组存储，每个int占32位 int index = hashValue >>> 5; // 等价于 hashValue / 32，无符号右移避免负数问题
这里使用无符号右移运算>>>代替除法，效率更高，因为位运算的执行速度远快于算术运算。
状态位在整数中的定位
找到数组索引后，需要确定该位置对应整数中的第几位，计算方式为：
int bitOffset = hashValue & 31; // 等价于 hashValue % 32，因为32是2的5次方，&31取低5位
与运算&可以快速取余，同样比取模运算效率更高。
位运算实现状态位的设置与查询
状态位的操作分为设置（标记为1）和查询（检查是否为1）两种，都可以通过位运算快速完成。
设置状态位为1
要将对应位设置为1，需要将对应整数的对应位通过位或运算置为1，其他位保持不变：
// bitSet是存储状态位的int数组 bitSet[index] = bitSet[index] | (1 << bitOffset);
其中1 << bitOffset会生成一个只有第bitOffset位为1的整数，位或运算会将该位设置为1，其他位不变。
查询状态位是否为1
要检查对应位是否为1，需要将对应整数的对应位通过位与运算提取出来，判断结果是否不为0：
// 检查对应位是否为1 boolean isSet = (bitSet[index] & (1 << bitOffset)) != 0;
如果对应位为1，位与运算的结果不为0，否则结果为0。
完整布隆过滤器状态位映射实现示例
下面是一个简单的布隆过滤器实现，包含状态位的映射、设置和查询逻辑：
public class SimpleBloomFilter {
// 位数组总大小，这里设置为1024位
private static final int BIT_SIZE = 1024;
// 存储状态位的int数组，每个int32位，需要1024/32=32个int
private static final int INT_SIZE = BIT_SIZE / 32;
private int[] bitSet;
// 哈希函数数量
private int hashCount;
public SimpleBloomFilter(int hashCount) {
this.hashCount = hashCount;
this.bitSet = new int[INT_SIZE];
}
// 模拟哈希函数，实际使用中可替换为更优的哈希算法
private int hash(String value, int seed) {
int hash = value.hashCode() ^ seed;
// 保证哈希值为正数，避免索引计算异常
return hash & 0x7fffffff;
}
// 添加元素，设置对应状态位
public void add(String element) {
for (int i = 0; i < hashCount; i++) {
int hashValue = hash(element, i) % BIT_SIZE;
// 计算数组索引
int index = hashValue >>> 5;
// 计算位偏移
int bitOffset = hashValue & 31;
// 设置对应位为1
bitSet[index] = bitSet[index] | (1 << bitOffset);
}
}
// 检查元素是否可能存在
public boolean contains(String element) {
for (int i = 0; i < hashCount; i++) {
int hashValue = hash(element, i) % BIT_SIZE;
int index = hashValue >>> 5;
int bitOffset = hashValue & 31;
// 检查对应位是否为1
if ((bitSet[index] & (1 << bitOffset)) == 0) {
return false;
}
}
return true;
}
public static void main(String[] args) {
SimpleBloomFilter filter = new SimpleBloomFilter(3);
filter.add("test");
System.out.println(filter.contains("test")); // 输出true
System.out.println(filter.contains("other")); // 输出false
}
}
位运算的优势与注意事项
使用位运算实现布隆过滤器的状态位映射，相比其他实现方式有以下优势：
- 执行效率高，位运算是CPU原生支持的操作，速度远快于算术运算和逻辑判断
- 内存占用低，直接操作二进制位，没有额外的对象开销
- 实现逻辑简洁，不需要复杂的条件判断和循环处理
需要注意的问题：
- 哈希函数的选择会影响布隆过滤器的误判率，尽量选择分布均匀的哈希函数
- 位数组的大小需要根据预期元素数量和可接受误判率提前规划，过小会导致误判率升高
- 位运算时要注意符号问题，比如右移运算优先使用无符号右移
>>>避免负数索引
布隆过滤器是存在误判概率的，当查询返回true时，元素可能不存在，返回false时元素一定不存在，实际应用中需要结合业务场景评估误判率的影响。