2的n次方

除数为2的N次⽅取模可以⽤与运算替代，效率更⾼

取模运算在包括JAVA在内的⼤多数语⾔中的效率都⼗分低下，⽽当除数为2的N次⽅时，取模运算将退化为最简单的位运算，其效率明显提升（按照Bruce

Eckel给出的数据，⼤约可以提升5～8倍）。看看JDK中是如何实现的：

当key空间长度为2的N次⽅时，计算hashCode为h的元素的索引可以⽤简单的与操作来代替笨拙的取模操作！假设某个对象的hashCode为35（⼆进制为

100011），⽽hashMap采⽤默认的initialCapacity（16），那么indexFor计算所得结果将会是100011&1111=11，即⼗进制的3，是不是恰好是35Mod16。

上⾯的⽅法有⼀个问题，就是它的计算结果仅有对象hashCode的低位决定，⽽⾼位被统统屏蔽了；以上⾯为例，19（10011）、35（100011）、

67（1000011）等就具有相同的结果。针对这个问题，JoshuaBloch采⽤了“防御性编程”的解决⽅法，在使⽤各对象的hashCode之前对其进⾏⼆次Hash，参

看JDK中的源码：

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

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

这种⽅法HashCode的计算⽅法可能最早出现在han和e的《TheCProgrammingLanguage》中，被认为是性价⽐最⾼的算法

Java代码：

intindexFor(inth,intlength){

h&(length-1);

03.}

[java]

intindexFor(inth,intlength){

h&(length-1);

03.}

inthash(Objectx){

=de();

03.h+=~(h<<9);

04.h^=(h>>>14);

05.h+=(h<<4);

06.h^=(h>>>10);

h;

08.}

[java]

inthash(Objectx){

=de();

03.h+=~(h<<9);

04.h^=(h>>>14);

05.h+=(h<<4);

06.h^=(h>>>10);

h;

08.}

(inti=0;i

02.h=31*h+val[off++];

03.}

=h;

[java]

(inti=0;i

02.h=31*h+val[off++];

03.}

=h;

（⼜被称为times33算法，因为C中乘数常量为33，JAVA中改为31），实际上，包括List在内的⼤多数的对象都是⽤这种⽅法计算Hash值。