转载: https://www.cnblogs.com/hollischuang/p/12009172.html
集合是 Java 开发日常开发中经常会使用到的，而作为一种典型的 K-V 结构的数据结构，HashMap 对于 Java 开发者一定不陌生。
在日常开发中，我们经常会像如下方式以下创建一个 HashMap：
Map<String, String> map = new HashMap<String, String>();
但是，大家有没有想过，上面的代码中，我们并没有给 HashMap 指定容量，那么，这时候一个新创建的 HashMap 的默认容量是多少呢？为什么呢？
本文就来分析下这个问题。
什么是容量
在 Java 中，保存数据有两种比较简单的数据结构：数组和链表。数组的特点是：寻址容易，插入和删除困难；而链表的特点是：寻址困难，插入和删除容易。HashMap 就是将数组和链表组合在一起，发挥了两者的优势，我们可以将其理解为链表的数组。
在 HashMap 中，有两个比较容易混淆的关键字段：size 和 capacity ，这其中 capacity 就是 Map 的容量，而 size 我们称之为 Map 中的元素个数。
简单打个比方你就更容易理解了：HashMap 就是一个“桶”，那么容量（capacity）就是这个桶当前最多可以装多少元素，而元素个数（size）表示这个桶已经装了多少元素。
如以下代码：
Map<String, String> map = new HashMap<String, String>();
map.put("hollis", "hollischuang");
Class<?> mapType = map.getClass();
Method capacity = mapType.getDeclaredMethod("capacity");
capacity.setAccessible(true);
System.out.println("capacity :" + capacity.invoke(map));
Field size = mapType.getDeclaredField("size");
size.setAccessible(true);
System.out.println("size :" + size.get(map));
输出结果：
capacity : 16、size : 1
上面我们定义了一个新的 HashMap，并向其中 put 了一个元素，然后通过反射的方式打印 capacity 和 size，其容量是 16，已经存放的元素个数是 1。
通过前面的例子，我们发现了，当我们创建一个 HashMap 的时候，如果没有指定其容量，那么会得到一个默认容量为 16 的 Map，那么，这个容量是怎么来的呢？又为什么是这个数字呢？
容量与哈希
要想讲清楚这个默认容量的缘由，我们要首先要知道这个容量有什么用？
我们知道，容量就是一个 HashMap 中 "桶" 的个数，那么，当我们想要往一个 HashMap 中 put 一个元素的时候，需要通过一定的算法计算出应该把他放到哪个桶中，这个过程就叫做哈希（hash），对应的就是 HashMap 中的 hash 方法。
我们知道，hash 方法的功能是根据 Key 来定位这个 K-V 在链表数组中的位置的。也就是 hash 方法的输入应该是个 Object 类型的 Key，输出应该是个 int 类型的数组下标。如果让你设计这个方法，你会怎么做？
其实简单，我们只要调用 Object 对象的 hashCode()方法，该方法会返回一个整数，然后用这个数对 HashMap 的容量进行取模就行了。
如果真的是这么简单的话，那 HashMap 的容量设置就会简单很多了，但是考虑到效率等问题，HashMap 的 hash 方法实现还是有一定的复杂的。
hash 的实现
接下来就介绍下 HashMap 中 hash 方法的实现原理。(下面部分内容参考自我的文章：全网把 Map 中的 hash()分析的最透彻的文章，别无二家 。PS：网上的关于 HashMap 的 hash 方法的分析的文章，很多都是在我这篇文章的基础上 "衍生" 过来的。）
具体实现上，由两个方法 int hash(Object k)和 int indexFor(int h, int length)来实现。
hash ：该方法主要是将 Object 转换成一个整型。
indexFor ：该方法主要是将 hash 生成的整型转换成链表数组中的下标。
为了聚焦本文的重点，我们只来看一下 indexFor 方法。我们先来看下 Java 7（Java8 中虽然没有这样一个单独的方法，但是查询下标的算法也是和 Java 7 一样的）中该实现细节：
static int indexFor(int h, int length) {
return h & (length-1);
}
indexFor 方法其实主要是将 hashcode 换成链表数组中的下标。其中的两个参数 h 表示元素的 hashcode 值，length 表示 HashMap 的容量。那么 return h & (length-1) 是什么意思呢？
其实，他就是取模。Java 之所有使用位运算 (&) 来代替取模运算(%)，最主要的考虑就是效率。
位运算 (&) 效率要比代替取模运算 (%) 高很多，主要原因是位运算直接对内存数据进行操作，不需要转成十进制，因此处理速度非常快。
那么，为什么可以使用位运算 (&) 来实现取模运算 (%) 呢？这实现的原理如下：
X % 2^n = X & (2^n – 1)
假设 n 为 3，则 2^3 = 8，表示成 2 进制就是 1000。2^3 -1 = 7 ，即 0111。
此时 X & (2^3 – 1) 就相当于取 X 的 2 进制的最后三位数。
从 2 进制角度来看，X / 8 相当于 X >> 3，即把 X 右移 3 位，此时得到了 X / 8 的商，而被移掉的部分(后三位)，则是 X % 8，也就是余数。
上面的解释不知道你有没有看懂，没看懂的话其实也没关系，你只需要记住这个技巧就可以了。或者你可以找几个例子试一下。
6 % 8 = 6 ，6 & 7 = 6
10 & 8 = 2 ，10 & 7 = 2
所以，return h & (length-1); 只要保证 length 的长度是 2^n 的话，就可以实现取模运算了。
所以， 因为位运算直接对内存数据进行操作，不需要转成十进制，所以位运算要比取模运算的效率更高，所以 HashMap 在计算元素要存放在数组中的 index 的时候，使用位运算代替了取模运算。之所以可以做等价代替，前提是要求 HashMap 的容量一定要是 2^n 。
那么，既然是 2^n ，为啥一定要是 16 呢？为什么不能是 4、8 或者 32 呢？
关于这个默认容量的选择，JDK 并没有给出官方解释，笔者也没有在网上找到关于这个任何有价值的资料。（如果哪位有相关的权威资料或者想法，可以留言交流）
根据作者的推断，这应该就是个经验值（Experience Value），既然一定要设置一个默认的 2^n 作为初始值，那么就需要在效率和内存使用上做一个权衡。这个值既不能太小，也不能太大。
太小了就有可能频繁发生扩容，影响效率。太大了又浪费空间，不划算。
所以，16 就作为一个经验值被采用了。
在 JDK 8 中，关于默认容量的定义为：static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 ，其故意把 16 写成 1<<4，就是提醒开发者，这个地方要是 2 的幂。值得玩味的是：注释中的 aka 16 也是 1.8 中新增的，
那么，接下来我们再来谈谈，HashMap 是如何保证其容量一定可以是 2^n 的呢？如果用户自己设置了的话又会怎么样呢？
关于这部分，HashMap 在两个可能改变其容量的地方都做了兼容处理，分别是指定容量初始化时以及扩容时。
指定容量初始化
当我们通过 HashMap(int initialCapacity)设置初始容量的时候，HashMap 并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高 hash 的效率。(1->1、3->4、7->8、9->16)
在 JDK 1.7 和 JDK 1.8 中，HashMap 初始化这个容量的时机不同。JDK 1.8 中，在调用 HashMap 的构造函数定义 HashMap 的时候，就会进行容量的设定。而在 JDK 1.7 中，要等到第一次 put 操作时才进行这一操作。
看一下 JDK 是如何找到比传入的指定值大的第一个 2 的幂的：
int n = cap - 1;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : (n>= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
上面的算法目的挺简单，就是：根据用户传入的容量值（代码中的 cap），通过计算，得到第一个比他大的 2 的幂并返回。
请关注上面的几个例子中，蓝色字体部分的变化情况，或许你会发现些规律。5->8、9->16、19->32、37->64 都是主要经过了两个阶段。
Step 1，5->7
Step 2，7->8
Step 1，9->15
Step 2，15->16
Step 1，19->31
Step 2，31->32
对应到以上代码中，Step1：
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
对应到以上代码中，Step2：
return (n < 0) ? 1 : (n>= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
Step 2 比较简单，就是做一下极限值的判断，然后把 Step 1 得到的数值 + 1。
Step 1 怎么理解呢？其实是对一个二进制数依次向右移位，然后与原值取或。其目的对于一个数字的二进制，从第一个不为 0 的位开始，把后面的所有位都设置成 1。
随便拿一个二进制数，套一遍上面的公式就发现其目的了：
1100 1100 1100 >>>1 = 0110 0110 0110
1100 1100 1100 | 0110 0110 0110 = 1110 1110 1110
1110 1110 1110 >>>2 = 0011 1011 1011
1110 1110 1110 | 0011 1011 1011 = 1111 1111 1111
1111 1111 1111 >>>4 = 1111 1111 1111
1111 1111 1111 | 1111 1111 1111 = 1111 1111 1111
通过几次无符号右移和按位或运算，我们把 1100 1100 1100 转换成了 1111 1111 1111 ，再把 1111 1111 1111 加 1，就得到了 1 0000 0000 0000，这就是大于 1100 1100 1100 的第一个 2 的幂。
好了，我们现在解释清楚了 Step 1 和 Step 2 的代码。就是可以把一个数转化成第一个比他自身大的 2 的幂。
但是还有一种特殊情况套用以上公式不行，这些数字就是 2 的幂自身。如果数字 4 套用公式的话。得到的会是 8，不过其实这个问题也被解决了，具体验证办法及 JDK 的解决方案见 全网把 Map 中的 hash() 分析的最透彻的文章，别无二家，这里就不再展开了。
总之，HashMap 根据用户传入的初始化容量，利用无符号右移和按位或运算等方式计算出第一个大于该数的 2 的幂。
扩容
除了初始化的时候回指定 HashMap 的容量，在进行扩容的时候，其容量也可能会改变。
HashMap 有扩容机制，就是当达到扩容条件时会进行扩容。HashMap 的扩容条件就是当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容。
在 HashMap 中，threshold = loadFactor * capacity。
loadFactor 是装载因子，表示 HashMap 满的程度，默认值为 0.75f，设置成 0.75 有一个好处，那就是 0.75 正好是 3/4，而 capacity 又是 2 的幂。所以，两个数的乘积都是整数。
对于一个默认的 HashMap 来说，默认情况下，当其 size 大于 12(16*0.75) 时就会触发扩容。
下面是 HashMap 中的扩容方法 (resize) 中的一段：
if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
从上面代码可以看出，扩容后的 table 大小变为原来的两倍，这一步执行之后，就会进行扩容后 table 的调整，这部分非本文重点，省略。
可见，当 HashMap 中的元素个数（size）超过临界值（threshold）时就会自动扩容，扩容成原容量的 2 倍，即从 16 扩容到 32、64、128 ...
所以，通过保证初始化容量均为 2 的幂，并且扩容时也是扩容到之前容量的 2 倍，所以，保证了 HashMap 的容量永远都是 2 的幂。
总结
HashMap 作为一种数据结构，元素在 put 的过程中需要进行 hash 运算，目的是计算出该元素存放在 hashMap 中的具体位置。
hash 运算的过程其实就是对目标元素的 Key 进行 hashcode，再对 Map 的容量进行取模，而 JDK 的工程师为了提升取模的效率，使用位运算代替了取模运算，这就要求 Map 的容量一定得是 2 的幂。
而作为默认容量，太大和太小都不合适，所以 16 就作为一个比较合适的经验值被采用了。
为了保证任何情况下 Map 的容量都是 2 的幂，HashMap 在两个地方都做了限制。
首先是，如果用户制定了初始容量，那么 HashMap 会计算出比该数大的第一个 2 的幂作为初始容量。
另外，在扩容的时候，也是进行成倍的扩容，即 4 变成 8，8 变成 16。
本文，通过分析为什么 HashMap 的默认容量是 16，我们深入 HashMap 的原理，分析了下背后的原理，从代码中我们可以发现，JDK 的工程师把各种位运算运用到了极致，想尽各种办法优化效率。值得我们学习！
关于作者：Hollis，一个对 Coding 有着独特追求的人，现任阿里巴巴技术专家，个人技术博主，技术文章全网阅读量数千万，《程序员的三门课》联合作者。
本文由 Suremotoo 创作，采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外，均为本站原创或翻译，转载前请务必署名
最后编辑时间为: May 15,2020