集合在Java开发的日常开发中经常会用到，而HashMap作为典型的K-V结构数据结构，对于Java开发者来说一定不陌生。在日常开发中，我们经常会创建一个HashMap，如下所示：Mapma??p=newHashMap();但是，大家有没有想过，在上面的代码中，我们并没有给HashMap指定容量，那么此时新建一个HashMap的默认容量是多少呢？为什么？本文将分析这个问题。什么是容量在Java中，有两种比较简单的存储数据的数据结构：数组和链表。数组的特点是：寻址容易，插入删除困难；而链表的特点是：寻址困难，插入删除方便。HashMap是数组和链表的结合，利用两者的优势，我们可以理解为链表的数组。在HashMap中，有两个容易混淆的关键字段：size和capacity，其中capacity是Map的容量，size称为Map中元素的个数。一个简单的类比会让你更容易理解：HashMap是一个“桶”，那么容量（capacity）就是这个桶当前能容纳的最大元素个数，元素个数（size）表示有多少个元素桶已经装满了。比如下面的代码：Mapma??p=newHashMap();map.put("hollis","hollishuang");类mapType=map.getClass();Methodcapacity=mapType。getDeclaredMethod("capacity");capacity.setAccessible(true);System.out.println("capacity:"+capacity.invoke(map));Fieldsize=mapType.getDeclaredField("size");size.setAccessible(true);System.out.println("size:"+size.get(map));输出结果：capacity:16,size:1上面我们定义了一个新的HashMap，并往里面放了一个元素，然后通过反射同样的方式打印出capacity和size，capacity为16，存储的元素个数是1，通过前面的例子我们发现，我们在创建一个HashMap的时候，如果不指定它的容量，会得到一个默认容量为16的Map。那么，这个容量是怎么来的呢？为什么是这个数字？?CapacityandHash要弄清楚这个默认容量的原因，首先要知道这个容量有什么用？我们知道，容量是HashMap中“桶”的数量。那么，当我们要往一个HashMap中放一个元素的时候，就需要通过一定的算法计算出应该放到哪个桶中。这个过程称为散列（hash），对应HashMap中的hash方法。我们知道hash方法的作用是根据Key来定位K-V在链表数组中的位置。即hash方法的输入应该是Object类型的Key，输出应该是int类型的数组下标。如果让你设计这种方法，你会怎么做？其实很简单，我们只需要调用Object对象的hashCode()方法，它会返回一个整数，然后用这个数对HashMap的容量取模。如果真的那么简单，那么HashMap的容量设置就会简单很多，但是考虑到效率等问题，HashMap的hash方法的实现还是有些复杂。hash的实现接下来介绍一下HashMap中hash方法的实现原理。具体实现上，通过inthash(Objectk)和intindexFor(inth,intlength)两个方法实现。hash：这个方法主要是将Object转化为一个整数。indexFor：该方法主要是将hash生成的整数转化为链表数组中的下标。为了突出本文的重点，我们只看indexFor方法。我们先看看Java7中的实现细节（虽然Java8中没有单独的方法，但是查询下标的算法和Java7是一样的）：staticintindexFor(inth,intlength){returnh&(length-1);}indexFor方法主要是将链表数组中的hashcode替换为下标。两个参数h表示元素的hashcode值，length表示HashMap的容量。那么returnh&(length-1)是什么意思呢？事实上，它是模数。所有Java都使用位运算(&)而不是模运算(%)。主要考虑的是效率。位运算（&）的效率远高于代替模运算（%）的效率。主要原因是位运算直接对内存数据进行运算，不需要转成十进制，所以处理速度非常快。那么，为什么可以用位运算（&）来实现模运算（%）呢？其实现原理如下：X%2^n=X&(2^n–1)假设n为3，则2^3=8，用二进制表示为1000。2^3-1=7，也就是0111，此时X&(2^3-1)就相当于取了X的二进制后三位，从二进制的角度来看，X/8相当于X>>3，即把X右移3位，此时得到X/8的商，去掉的部分（后三位）就是X%8，也就是余数。不知道上面的解释你看懂了吗。看不懂也没关系。你只需要记住这个技巧。或者你可以找几个例子试试看。6%8=6,6&7=610&8=2,10&7=2运算过程如下：因此，returnh&(length-1);只要保证length的长度为2^n，就可以实现模运算。因此，由于位运算直接对内存数据进行运算，不需要转成十进制，所以位运算比取模运算效率更高，所以HashMap在计算要存储的元素在数组中的索引时，而是使用位操作。模运算。之所以可以进行等价替换，是因为HashMap的容量必须是2^n。那么，既然是2^n，为什么一定要是16呢？为什么不能是4、8或32？关于这个默认容量的选择，JDK官方并没有给出解释，笔者在网上也没有找到这方面的资料。值信息。（如果哪位有相关权威信息或者想法可以留言交流）根据笔者的推断，这应该是一个经验值（ExperienceValue）。既然需要设置一个默认的2^n作为初始值，那么就需要在效率和内存占用之间做一个权衡。这个值既不能太小也不能太大。如果太小，可能会频繁扩容，影响效率。太大了，浪费空间，不值得。因此，采用16作为经验值。在JDK8中，默认容量的定义是：staticfinalintDEFAULT_INITIAL_CAPACITY=1<<4;//aka16，故意把16写成1<<4，就是提醒开发者这个地方是2的幂。值得深思：评论中的aka16也是1.8新增的。那么，我们来说说如何保证HashMap的容量可以是2^n？如果用户自己设置会怎样？如何？关于这部分，HashMap在两个可能改变容量的地方做了兼容处理，分别是初始化指定容量时和扩容时。指定容量初始化当我们通过HashMap(intinitialCapacity)设置初始容量时，HashMap并不一定直接采用我们传入的值，而是计算得到一个新的值，这样做的目的是提高哈希效率。(1->1,3->4,7->8,9->16)在JDK1.7和JDK1.8中，HashMap初始化这个容量的时机是不一样的。在JDK1.8中，调用HashMap的构造函数定义HashMap时，会设置容量。在JDK1.7中，直到第一个put操作才会执行此操作。看一下JDK如何求大于传入的指定值的2的1次方：intn=cap-1;n|=n>>>1;n|=n>>>2;n|=n>>>4;n|=n>>>8;n|=n>>>16;返回(n<0)?1:(n>=MAXIMUM_CAPACITY)?MAXIMUM_CAPACITY:n+1;上述算法的目的很简单，就是：根据用户传入的容量值（代码中的cap），通过计算，得到比它大的2的1次方并返回。请注意上面例子中蓝色字体的变化，说不定你会发现一些规律。5->8、9->16、19->32、37->64主要经历了两个阶段。Step1,5->7Step2,7->8Step1,9->15Step2,15->16Step1,19->31Step2,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;第2步比较简单，就是判断极限值，然后将第1步得到的值加1。如何理解第1步？其实就是将一个二进制数依次右移，再与原值进行或运算。它的用途是用于数字二进制，从第一个非0的位开始，并将所有后续位设置为1。随便拿一个二进制数，套一遍上面的公式就发现其目的了：110011001100>>>1=011001100110110011001100|011001100110=111011101110111011101110>>>2=001110111011111011101110|001110111011=111111111111111111111111>>>4=111111111111111111111111|111111111111=111111111111通过几无符号右移和按位或操作，我们将110011001100转化为111111111111，然后111111111111加1得到1000000000000，也就是大于110011001100的第2次方。好了，现在我们已经把Step1和Step2的代码解释清楚了。意思是一个数可以转换成比它本身大的2的1次方。但是还有一种特殊情况，上面的公式就不能应用了。这些数字本身就是2的幂。如果数字4应用公式。结果会是8，其实这个问题也解决了。简而言之，HashMap根据用户传入的初始化容量，使用无符号右移和按位或运算，计算大于数的2的1次方。HashMap除了在初始化时指定容量外，其容量在扩容时也可能发生变化。HashMap有一个扩容机制，即当满足扩容条件时，它就会扩容。HashMap的扩容条件是当HashMap中的元素个数（size）超过阈值（threshold）时，会自动扩容。在HashMap中，threshold=loadFactor*capacity。loadFactor是加载因子，表示HashMap的填充度。默认值为0.75f。设置为0.75有个好处，就是0.75正好是3/4，capacity是2的幂，所以两个数的乘积是整数。对于一个默认的HashMap，默认情况下，当其大小大于12（16*0.75）时会触发扩容。下面是一段HashMap的扩容方法（resize）：if((newCap=oldCap<<1)=DEFAULT_INITIAL_CAPACITY)newThr=oldThr<<1;//doublethreshold}从上面的代码可以看出，扩展后表的大小增加了一倍。执行完这一步后，表会在扩容后进行调整。这部分不是本文的重点，省略。可以看出，当HashMap中的元素个数（size）超过阈值（threshold）时，会自动扩容到原来容量的2倍，即从16个扩容到32个、64个、128个……所以，通过保证初始容量统一是2的幂，在扩容的时候，也扩充到之前容量的两倍。所以保证了HashMap的容量永远是2的幂。总结一下，HashMap是一种数据结构。在put过程中需要对元素进行哈希处理，以便计算出元素存储在hashMap中的具体位置。hash运算的过程其实就是对目标元素的Key进行hashcode，然后对Map的容量取模。JDK工程师为了提高取模效率，采用位操作代替取模操作，这就要求Map的容量一定。必须是2的次方，因为默认的容量，太大也太小都不合适，所以采用16作为比较合适的经验值。为了保证Map的容量在任何情况下都是2的幂，HashMap在两个地方做了限制。首先，如果用户指定初始容量，那么HashMap会计算大于该数的2的1次方作为初始容量。另外，当扩容时，容量翻倍，即4变成8，8变成16。本文通过分析为什么HashMap默认容量为16，深入HashMap的原理和分析其背后的原理。从代码中我们可以发现，JDK工程师将各种位操作发挥到了极致，想方设法优化效率。值得学习！【本文为专栏作家霍利斯原创文章，作者微信公众号Hollis（ID：hollishuang）】点此阅读作者更多好文
