写在前面

HashMap源码分析，可以说是面试中必问的题目。作为以key/value存储方式的集合，HashMap的集成了链表的思想；此外1.8引入了红黑树的思想。今天这篇文章着重聊一聊1.8之前的HashMap~

接下来会用到的几个常量

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

static final int MAXIMUM_CAPACITY = 1 << 30;

static final int MAXIMUM_CAPACITY = 1 << 30;

正文

HashMap的思路

我们put的key/value会被封装成一个叫做Entry的内部类。这个Entry由一个变量名为table数组管理。我们每次put会通过一系列的计算，计算一个table数组的index下标用于放Entry，如果出现hash冲突使用链表法解决。get时，可以理解是一个反向的put过程。

put(K key, V value)

1、初始化

走到这一步，相当于我们的第一次put的初始化过程完成。那么接着让我们看下一步操作。

2、key为null

当然这一步的前面还有一个key为null的情况。因为实在是太直白，就不单独展开，代码如下：

这里我们可以得到一个信息，key为null的Entry会放在table[0]的位置上。

3、index下标计算

走到这一步，我们所要做的就是先计算我们这个key/value应该放在table的那个位置。也就是说，在真正包装成Entry之前，我们需要确定这个Entry的应该再哪个坑里。

计算hash值的hash方法如下：

计算完hash之后，就是通过hash计算我们Entry应该在那个下标中：

走到这一步我们Entry该放在哪个位置已经明确了，这里有很多位运算…根据效果来看，这样的计算方式保证了，Entry更少的冲突。

4、插入Entry

既然上诉2的过程已经确定了插入位置，那么毫无疑问，我们该插入这个Entry了。

4.1、重复key处理

既然插入，那么势必有可能遇到重复问题，比如说，我们插入同一个key。这里就是一个比较常见的问题，Map可不可以使用重复key，或者Map怎样处理重复key的问题。

因此关于key重复的问题，我们就可以得到答案。Map的操作是替换旧的value并返回老的value。

4.2、扩容

上诉步骤我们处理的key重复的问题。那么接下来，就是Map的扩容过程。这里会用到一个变量threshold，我们知道初始化table之后，这个变量 = 数组长度*0.75。记住这个值，它就是扩容的阈值。

4.3、创建并添加

首先获取index下标下的Entry，我们明白这里的e有可能为空。（而这里没有对null这种情况进行判断，也就是说这里为不为空都无所谓）

拿到e之后，进行new Entry()把e，以及hash，key，value传了进来。

这里我们看一个e，放在了哪里？

这里说明一个什么问题？那就是当hash冲突之后，我们的Entry是在链表的头还是尾。根据代码来看，很明显是在链表的头，这也说明了，为什么e为null这种情况没有做特别处理。

我们对put的分析就到此为止，既然分析了put，那么接下来就是get。

get(Object key)

1、处理key为null的情况

关于key为null的情况，其实我们也能看出，比较简单明了。接下来就是key不为null的情况。

2、key不为null

代码思路比较的明确，其实就是一个反向的put过程。我们先通过key计算hash，然后计算对应Entry在数组中的index，然后遍历对应链，找出匹配的value即可。

get方法我们可以看出，是比较简单的。

尾声

分析完put/get其实基本上HashMap就梳理完毕。

这里我们进行一点总结：

1、put时，key可以为空。并且放在table[0]的这个位置2、扩容策略是，size>=当前容量*0.75并且当前table[index]不为null。扩容大小为2倍。3、JDK1.7的HashMap使用链表法解决冲突，并且新插入的Entry是在链表的表头。