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

2019-04-13 15:10发布

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

Java代码：
  1. static int indexFor(int h, int length) {   
  2.     return h & (length-1);   
  3. }  
[java] view plain copy
  1. static int indexFor(int h, int length) {  
  2. return h & (length-1);  
  3. }  


当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代码：
  1. static int hash(Object x) {   
  2.         int h = x.hashCode();   
  3.         h += ~(h << 9);   
  4.         h ^=  (h >>> 14);   
  5.         h +=  (h << 4);   
  6.         h ^=  (h >>> 10);   
  7.         return h;   
  8.     }  
[java] view plain copy
  1. static int hash(Object x) {  
  2. int h = x.hashCode();  
  3. h += ~(h << 9);  
  4. h ^=  (h >>> 14);  
  5. h +=  (h << 4);  
  6. h ^=  (h >>> 10);  
  7. return h;  
  8. }  


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

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

Java代码：
  1. for (int i = 0; i < len; i++) {   
  2. h = 31*h + val[off++];   
  3. }   
  4. hash = h;  
[java] view plain copy
  1. for (int i = 0; i < len; i++) {  
  2. h = 31*h + val[off++];  
  3. }  
  4. hash = h;  


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

热门文章