Java集合框架1——HashMap中“键值对”存放的源码理解

最近，学习JavaWeb的同时，也在回顾JavaSE中集合框架的知识。本文主要从源码的角度，分析和理解HashMap对元素的存储。

下图是HashMap的存储结构（纵向是数组，横向是链表）：

将键值对存入HashMap集合中，需要调用put(K key,V value)方法，所以先来看看HashMap源码中的Put(K key,V value)方法：（我自己加的简略注释，后面有详解）

通过上面的put()源码，我们已经可以先从整体上了解键值对在HashMap中的存储过程。下面将分析细节：

一、key对应的哈希值的计算

由上面的代码，我们可以知道key对应的哈希值是通过hash()方法计算出来的一个int型的数值，但这个数值并不是通常所说的hashCode,点进源码的hash()方法里看看：

从上面的代码片段可以看出，hash()方法内部先算出了key对应的hashCode值（hashCode底层是用C++实现的，略过），再通过一系列的异或、移位等运算，对hashCode值进一步计算和二进制位的调整，实现了存储位置的均匀分布。

二、存放在table[]数组中的索引值i的计算

索引值i是通过调用indexFor()方法计算出来的，我们点进源码的indexFor()方法看看：

indexFor()方法内部只有一行代码： return h & (length-1);但却是HashMap的核心知识点。

这里的h即为刚刚通过hash()方法得到的值，而length即为table[]数组的长度（在HashMap中，若创建时没有传入length，则默认length为16，阈值为12，装填因子默认为0.75，阈值=length*装填因子）。

将要存放的键值对在table[]数组中的索引值i就是由h & (length-1)得到的，&代表二进制的与运算在HashMap的扩容机制中，table[]数组长度总是2的n次方，原因就在于：当length为2的n次方时（这个是前提！），h& (length-1)运算等价于对length取模，也就是h%length，但是&比%具有更高的效率。

三、如何存放新插入的键值对

由上面的分析可知，我们先计算出键值对中的“键”key所对应的的哈希值hash，目的是利用该哈希值去计算存放位置的索引i,最后一步我们要做的就是存放该键值对了。是怎么做的呢？

首先，通过for循环遍历table[i]及对应的冲突链表，看看是否已经存在了该key对应的键值对，如果已经存在了，那么就用新键值对的value去覆盖旧键值对的value，完成！

如果table[i]及对应的冲突链表中，找不到与新键值对中的key完全相同的对象，那么就在table[i]增加新键值对，存放进来，而且新插入的键值对总是在table[i]对应的冲突链表的表头,它指向原有的键值对。

再看看源码的具体实现：