最近好奇的研究了下Spark的BloomFilter的实现，发现其org/apache/spark/util/sketch/BitArray.java对bit处理的实现很巧妙（源码可能是从其他开源项目借鉴的也不好说），从中学到不少东西，记录下。
BitArray巧妙的核心设计
BitArray内部采用long[] data来表示一个大的bitmap，long类型相比int在相同的数组个数下可以存放更多的bit信息。
比较有意思的是set方法的实现，核心代码如下：
// 将指定index位置的bit位设置为1，表示指定的index处有值
void set(long index) {
data[(int) (index >>> 6)] |= (1L << index);
}
估计不少读者看到这行代码比较懵逼，由于工作中使用bit操作的场景不多，至少我当时是比较懵逼的。
先来说下>>>, >>是按位右移操作(bitwise shift)相信大家都清楚，>>是保留符号位的，>>>则是无符号右移，也就说要移的数为正，则高位补0，而若该数为负数，则右移后高位同样补0，还是看个例子比较直观：
jshell> -2 >> 1
$1 ==> -1
jshell> -2 >>> 1
$2 ==> 2147483647
那么index >>> 6又是什么鬼？
Java中一个long类型占8个byte，也就是64个bit，如果让我们实现给定一个index，判断该index属于数组的第几个元素，我们可能会这么实现：
data[index / 64]
而2^6刚好是64，index >>> 6则相当于index / 64，而按位(bitwise)操作效率上是高于买游戏账号除法的，所以，会看到代码里采用了index >>> 6的实现。
现在定位到了index所处data数组中的位置了，怎么给指定的index设置bit位为1呢？
假如我们手头上有个int类型的变量a，以a |= (1 << 3)为例：采用按位或的操作就可以将a的第3个bit位设置为1，这个比较基础，相信大家都明白。
BitArray中让人懵逼的是直接对一个long类型的值进行了1L << index操作，如果让我实现的话，我会这么做：1 << (index % 64)，我们知道long只有64位，如果index大于64位呢？
如果不实际运行代码，1L << 65，由于移位数超出了long的表示范围，估计不少人会认为得到的值是0吧，我们先看下实际的结果：
jshell> 1L << 65
$1 ==> 2
为啥会是这样？各种找资料，最后在Oracle官方的Java SE Specifications中找到了答案：
If the promoted type of the left-hand operand is long, then only the six lowest-order bits of the right-hand operand are used as the shift distance. It is as if the right-hand operand were subjected to a bitwise logical AND operator & (§15.22.1) with the mask value 0x3f (0b111111). The shift distance actually used is therefore always in the range 0 to 63, inclusive.
原来Java内部在做移位(shift operation)操作时，会将右边的shift distance和0x3f按位与后，在做移位操作，这样就能保证移位的范围总是0~63。也就是说对于long类型的位移操作Java内部自动给我们做了% 64的处理。类似的，如果是int类型的操作，Java内部会将移位的距离& 0x1f确保移位范围在0~31。
我们把1L << index按Java内部的处理拆解下：
1L << index 相当于
1L << (index & 0x3f) 相当于
1L << (index & 0b111111) 相当于
1L << (index % 2^6) 相当于
1L << (index % 64)
在回头看下1L << 65其实就是1L << (65 % 64)等价于1L << 1得到的值是2。这个问题就比较清楚了。
回到BitArray的set方法的实现上：
void set(long index) {
data[(int) (index >>> 6)] |= (1L << index);
}
// 等价于
void set(long index) {
data[index / 64] |= (1L << (index % 64));
}
这下就不懵逼了。bitwise操作性能更好，data[index / 64] |= (1L << (index % 64))看起来更直观，顺便查了下这种操作JVM是否会自动优化为bitwise操作，文章提到会优化。
一些常用的bitwise运算实例
鉴于bitwise的操作比较有意思，我整理了些常用实例，至少以后遇到这种操作不让自己那么懵逼。
判断int型变量a是奇数还是偶数
a & 1 = 0 // 偶数
a & 1 = 1 // 奇数
取模运算转化成位运算 (在不产生溢出的情况下)
a % (2^n) 等价于 a & (2^n - 1)
如：a % 32 等价于 a & 0x1f
乘法运算转化成位运算 (在不产生溢出的情况下)
a * (2^n) 等价于 a << n
除法运算转化成位运算 (在不产生溢出的情况下)
a / (2^n) 等价于 a >> n
取相反数
x的相反数为~x + 1
// 原理上和计算机采用二进制补码（2's complement）的表示形式有关
其他
if (x == a):
x = b
else:
x = a
等价于：x = a ^ b ^ x
附：Spark的BloomFilter之Hash算法
最后看了下Spark内部的BloomFilter关于Hash算法选择的问题，发现其采用的是Murmur3Hash，第一次听说这个Hash算法，了解下是谷歌的东西，优势在于性能。Spark源码里直接将MurmurHash从Guava包中搬过来了。
Spark内部除了BloomFilter在用MurmurHash以外，UnsafeRow在计算Hash时，也有用到。
查了下MurmurHash应用的还是挺广泛的，Redis，Memcached，Cassandra，HBase，Lucene都有在用。对于MurmurHash自己真是孤陋寡闻了，看来平时还得多看看源码。
