HashMap中的为什么hash的长度为2的幂而&位必须为奇数

电玩女神 2022-06-06 13:25 67阅读 0赞

### 背景 ###

哈希算法在Java中是经常用的的一个算法，也是一些常用数据结构中必用的一个算法，它为上层的复杂数据结构提供了基础支撑。

哈希算法的实现有很多种，除了这里讲的map中的hashcode算法，还有其他哈希算法：

1.直接定址法  
2.数字分析法  
3.折叠法  
4.平方取中法  
5.减去法  
6.字符串数值哈希法  
7.旋转法

更多算法请参考另一篇作者的文章：  
[hash算法原理详解][hash]

### HashMap中的HashCode算法详解 ###

1，哈希算法在HashMap类中的应用  
java中的集合，比如HashMap/Hashtable/HashSet等，在实现时，都用到了哈希算法。当我们向容器中添加元素时，我们有必要知道  
这个元素是否已经存在。  
从实现上来说，java是借助hashcode()方法和equals()方法来实现判断元素是否已经存在的。当我们向HashMap中插入元素A时，首先，  
调用hashcode()方法，判断元素A在容器中是否已经存在。如果A元素的hashcode值在HashMap中不存在，则直接插入。否则，接着调用  
equals()方法，判断A元素在容器中是否已经存在。hashcode()的时间复杂度为O(1)，equals()方法的时间复杂度为O(m)，整体的时间复杂度  
就是：O(1) + O(m)。其中，m是桶的深度。桶的深度是一个什么概念呢，桶的深度是指具有相同hashcode值得元素的个数，也就是发生哈希  
碰撞的元素的个数。  
一个好的哈希算法应该尽量减少哈希碰撞的次数。

HashCode是Object中本身就有的方法，但是没有具体实现。而各个不同的数据类型又继承实现了各自的具体HashCode算法，这里只以String类型的HashCode为例。

public int hashCode() {  
    int h = hash;  
    if (h == 0) {  
        int off = offset;  
        char val[] = value;  
        int len = count;  
    
            for (int i = 0; i < len; i++) {  
                h = 31*h + val[off++];  
            }  
            hash = h;  
        }  
        return h;  
    }

源代码写的比较简洁，阅读起来也不是太方便，下面我详细解读一下：  
// String类的hashcode值（哈希值）是如何计算得到的？具体实现？为了方便阅读，我们来进行分步说明

static void hashcodeTest(){  
    
        String str = "yangcq";  
    
        // 第一步 = (int)'y'  
        // 第二步 = (31 * (int)'y') + (int)'a'  
        // 第三步 = 31 * ((31 * (int)'y') + (int)'a') + (int)'n'  
        // 第四步 = 31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g'  
        // 第五步 = 31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c'  
        // 第六步 = 31 * (31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c') + (int)'q'  
    
        // 上面的过程，也可以用下面的方式表示  
    
        // 第一步 = (int)'y'  
        // 第二步 = 31 * (第一步的计算结果) + (int)'a'  
        // 第三步 = 31 * (第二步的计算结果) + (int)'n'  
        // 第四步 = 31 * (第三步的计算结果) + (int)'g'  
        // 第五步 = 31 * (第四步的计算结果) + (int)'c'  
        // 第六步 = 31 * (第五步的计算结果) + (int)'q'  
    
        int hashcode = 31 * (31 * (31 * (31 * ((31 * (int)'y') + (int)'a') + (int)'n') + (int)'g') + (int)'c') + (int)'q';  
        System.out.println("yangcq的hashcode = " + hashcode);        // yangcq的hashcode = -737879313  
        System.out.println("yangcq的hashcode = " + str.hashCode());  // yangcq的hashcode = -737879313  
    
    }

### 为什么HashMap中的&位必须为奇数（Length - 1） ###

从Key映射到HashMap数组的对应位置，会用到一个Hash函数：

index = Hash（“apple”）

如何实现一个尽量均匀分布的Hash函数呢？我们通过利用Key的HashCode值来做某种运算。  
如何进行位运算呢？有如下的公式（Length是HashMap的长度）：

index = HashCode（Key） & （Length - 1）

下面我们以“book”的Key来演示整个过程：

1.计算book的hashcode，结果为十进制的3029737，二进制的101110001110101110 1001。

2.假定HashMap长度是默认的16，计算Length-1的结果为十进制的15，二进制的1111。

3.把以上两个结果做与运算，101110001110101110 1001 & 1111 = 1001，十进制是9，所以 index=9。

可以说，Hash算法最终得到的index结果，完全取决于Key的Hashcode值的最后几位。

假设HashMap的长度是10，重复刚才的运算步骤：  
![这里写图片描述][SouthEast]

单独看这个结果，表面上并没有问题。我们再来尝试一个新的HashCode 101110001110101110 1011 ：  
![这里写图片描述][SouthEast 1]  
让我们再换一个HashCode 101110001110101110 1111 试试 ：  
![这里写图片描述][SouthEast 2]

是的，虽然HashCode的倒数第二第三位从0变成了1，但是运算的结果都是1001。也就是说，当HashMap长度为10的时候，有些index结果的出现几率会更大，而有些index结果永远不会出现（比如0111）！

这样，显然不符合Hash算法均匀分布的原则。

反观长度16或者其他2的幂，Length-1的值是所有二进制位全为1，这种情况下，index的结果等同于HashCode后几位的值。只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

[hash]: http://blog.csdn.net/tanggao1314/article/details/51457585
[SouthEast]: /images/20220606/1a886464ceb64f0b915dce6e0e130a8d.png
[SouthEast 1]: /images/20220606/7377be20498b4442ae788df142fa7ffe.png
[SouthEast 2]: /images/20220606/cba3d50cc20248eaa5e343f31c3b283c.png