求模运算(%)和按位与运算(&)

2019-04-13 13:45发布

最近看了看HashMap源码,觉得里面的一个按位与运算用的很优雅,记录一下。jdk7中,HashMap是“数组+链表”的结构,为了让HashMap里的元素分布的更加均匀,就要在数组中给每个元素一个合适的位置,求模运算是一个不错的方法,但是,jdk7中使用了一种更加优雅的方法,源码中的方法如下:static int indexFor(int h, int length) { return h & (length-1); }是的,就是效率更高的按位与运算。这里有一个前提,length是一个2的幂次方整数,这样,length-1 的二进制就是一个形如“0000111...”的数,比如,如果length=4length-1=3,其二进制表示为“0011”,如果length=8length-1=7,其二进制表示为“0111”,以此类推。将hlength-1进行按位与运算的时候,由于高位都是0,只有低位的1才能决定最终的结果,就相当于对h进行相应数值(即length)的求模运算。