HashMap实现原理分析

参考：http://blog.csdn.net/vking_wang/article/details/14166593

HashMap的数据结构

在数据结构中，有数组和链表来实现对数据的存储，但这两者是两个极端。

数组

数组的存储区间是连续的，空间复杂度大，时间复杂度小。特点是：查找容易，插入和删除困难。

链表

链表的存储区间是离散的，空间复杂度小，时间复杂度大。特点是：查找困难，插入和删除容易。

哈希表

哈希表是综合了数组和链表的优点，既满足了查找方便，同时也不占用太多空间，使用也很方便。

哈希表有很多实现方式，下面讲解最常用的拉链发，可以理解为链表的数组：

从上图中总可以看出，哈希表是由数组+链表组成的，HashMap里面实现了一个静态内部类Entity,其重要属性有key、value和next，从属性可以看出Entity是HashMap键值对实现的一个基础Bean，上面我们说到HashMap的基础就是一个线性数组，即Entity[],Map里面的内容都保存在数组Entity[]中, 下面是个demo：

这个链表是一个长度为16的数组，左边数字是数组的下标，右边的数字是key的hash值，数组中的每一个元素都是一个链表的头节点，那么这些元素是按照什么规则存储的呢？又是按照什么规则查找的呢？

存取规则hash(key)%len

比如上图中，key的hash值为31的元素，模上数组长度16，结果是15，那么它就存储在arr[15]所在的链表中。查找时就是先计算hash(key)%len，找出元素所在的链表位于数组的位置，然后遍历链表即可。

几个注意点

1. 不同的Hash可能有相同的index，相同的index不一定有相同的Hash。
2. 对于hash(key)%len计算得到相同index的元素，采用头插法，即后来的插到链表的头部，也就是说数组中存储的那个头元素是最后插进来的。
3. HashMap允许key为null的元素存入，key为null的元素永远存储在链表头部，即数组中。
4. Entity[]的长度固定后，随着元素的增加，链表会越来越长，这时候HashMap中的一个因子就会起到作用，随着map的size越来越大，Entity[]的length会以一定的规则增加。