java取模场景下设置数组等长度尽量用2的n次方数字

记录一下除数为2的N次方取模可以用与运算替代，效率更高

转载：除数为2的N次方取模可以用与运算替代，效率更高_taoshengyang的专栏-CSDN博客

取模运算在包括JAVA在内的大多数语言中的效率都十分低下，而当除数为2的N次方时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce Eckel给出的数据，大约可以提升5～8倍） 。看看JDK中是如何实现的：

Java代码：
 

static int indexFor(int h, int length) {   
    return h & (length-1);   
}  

当key空间长度为2的N次方时，计算hashCode为h的元素的索引可以用简单的与操作来代替笨拙的取模操作！假设某个对象的hashCode为35（二进制为100011），而hashMap采用默认的initialCapacity（16），那么indexFor计算所得结果将会是100011 & 1111 = 11，即十进制的3，是不是恰好是35 Mod 16。

上面的方法有一个问题，就是它的计算结果仅有对象hashCode的低位决定，而高位被统统屏蔽了；以上面为例，19（10011）、35（100011）、67（1000011）等就具有相同的结果。针对这个问题， Joshua Bloch采用了“防御性编程”的解决方法，在使用各对象的hashCode之前对其进行二次Hash，参看JDK中的源码：

Java代码：
 

static int hash(Object x) {   
        int h = x.hashCode();   
        h += ~(h << 9);   
        h ^=  (h >>> 14);   
        h +=  (h << 4);   
        h ^=  (h >>> 10);   
        return h;   
    }

采用这种旋转Hash函数的主要目的是让原有hashCode的高位信息也能被充分利用，且兼顾计算效率以及数据统计的特性，其具体的原理已超出了本文的领域。

加快Hash效率的另一个有效途径是编写良好的自定义对象的HashCode，String的实现采用了如下的计算方法：

Java代码：
 

for (int i = 0; i < len; i++) {   
h = 31*h + val[off++];   
}   
hash = h;  

这种方法HashCode的计算方法可能最早出现在Brian W. Kernighan和Dennis M. Ritchie的《The C Programming Language》中，被认为是性价比最高的算法（又被称为times33算法，因为C中乘数常量为33，JAVA中改为31），实际上，包括List在内的大多数的对象都是用这种方法计算Hash值。