HashMap的默认容量为何为16？为何是2的整数倍？面试必备

Coder小哥 05-15 4600

前言：

现在朋友们对“java判断是否整数倍”都比较珍视，咱们都需要了解一些“java判断是否整数倍”的相关知识。那么小编同时在网络上搜集了一些对于“java判断是否整数倍””的相关内容，希望兄弟们能喜欢，小伙伴们一起来学习一下吧！

理解 HashMap 的源码实现时，有如下几点：

①、初始容量为 1<<4，也就是24 = 16

②、负载因子是0.75，当存入HashMap的元素占比超过整个容量的75%时，进行扩容，而且在不超过int类型的范围时，进行2次幂的扩展(指长度扩为原来2倍)

扩大一倍

③、新添加一个元素时，计算这个元素在HashMap中的位置，也就是本篇文章的主角哈希运算。分为三步：

第一步：取 hashCode 值： key.hashCode()

第二步：高位参与运算：h>>>16

第三步：取模运算：(n-1) & hash

ps：第 6 行代码是我自己加的。

首先第一步取得 hashCode，该方法是一个用native修饰的本地方法，返回的是一个 int 类型的值（根据内存地址换算出来的一个值），通常我们都会重写该方法。

第二步将取得的哈希值无符号右移16位，高位补0。并与前面第一步获得的hash码进行按位异或^ 运算。这是为了当length比较小的时候，也能保证考虑到高低Bit位都参与到Hash的计算中，同时不会有太大的开销。

看这段代码：

我们知道对于HashMap的table而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间。计算hash值后，怎么才能保证table元素分布均与呢？我们会想到取模，但是由于取模的消耗较大，HashMap是这样处理的：调用indexFor方法。

HashMap源码中有一个indexFor方法，返回的是key的hashcode跟初始容量-1做与运算。

首先length为2的整数次幂的话，h&(length-1)就相当于对length取模，这样便保证了散列的均匀，同时也提升了效率；

其次，length为2的整数次幂的话，为偶数。这样length-1为奇数，奇数的最后一位为1，这样便保证了h&(length-1)的最后一位为0，也可能为1（这取决于h的值），即与后的结果可能为偶数也可能是奇数。这样便可以保证散列的均匀性，

而如果length为奇数的话，很明显length-1为偶数，它的最后一位是0，这样h&(length-1)的最后一位肯定为0，即只能为偶数，这样任何hash值都只会被散列到数组的偶数下标位置上，这便浪费了近一半的空间。所以，length取2的整数次幂，是为了使不同hash值发生碰撞的概率较小，这样就能使元素在哈希表中均匀地散列。

为方便大家更好理解，说一下java运算符与（&）、非（~）、或（|）、异或（^）

1）十进制转二进制

原理：给定的数循环除以2，直到商为0或者1为止。将每一步除的结果的余数记录下来，然后反过来就得到相应的二进制了。

比如8转二进制，第一次除以2等于4（余数0），第二次除以2等于2（余数0），第三次除以2等于1（余数0），最后余数1，得到的余数依次是0 0 0 1 ，

2）二进制转十进制

计算也很简单，比如8的二进制表示位00001000，去掉补齐的高位就是1000.此时从个位开始计算2的幂（个位是0，依次往后推）乘以对应位数上的数，然后得到的值想加

于是有了，（2的0次幂）*0+（2的1次幂）*0+（2的2次幂）*0+（2的3次幂）*1 = 8

3）位异或运算（^）

运算规则是：两个数转为二进制，然后从高位开始比较，如果相同则为0，不相同则为1。

比如：8^11.

8转为二进制是1000，11转为二进制是1011.从高位开始比较得到的是：0011

4）位与运算符（&）