本文主要是介绍除数为2的N次方取模可以用与运算替代，效率更高，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
取模运算在包括JAVA在内的大多数语言中的效率都十分低下，而当除数为2的N次方时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce Eckel给出的数据，大约可以提升5～8倍） 。看看JDK中是如何实现的：Java代码：
- static int indexFor(int h, int length) {
- return h & (length-1);
- }
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;
- }
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;
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值。
这篇关于除数为2的N次方取模可以用与运算替代，效率更高的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
