HashMap源码剖析及实现原理分析（学习笔记）

　　一、需求

　　最近开发中，总是需要使用HashMap，而为了更好的开发以及理解HashMap；因此特定重新去看HashMap的源码并写下学习笔记，以便以后查阅。

二、HashMap的学习理解　　

　　1、我们首先需要知道HashMap为什么会存在？

　　　　HashMap是从Java1.2引进的基于哈希表的Map接口的一个实现，以key-value的形式存在，从而可以通过key快速存取value值。

　　　　解释下哈希表(HashTable)——在说HahMap之前先说说Java中的数据结构，数组与链表的区别。

　　　　数组：数组的存储区间是连续的，占用内存比较大，从而导致空间复杂度比较大，时间复杂度比较小；特点是：寻址容易，但插入删除困难。

　　　　链表：链表的存储区间不连续，占的内存相对较小，空间复杂度也比较小，时间复杂度比较大；特点是：寻址困难，插入删除容易。

　　　　而哈希表(HashTable)是数组与链表二者特点的综合，既满足了数据的查找方便，同时不占用太多的内容空间，使用也十分方便。

　　　　HashMap其实也是一个线性的数组实现的,所以可以理解为其存储数据的容器就是一个线性数组。

　　2、HashMap的定义

　　　　HashMap实现了Map接口，继承AbstractMap。其中Map接口定义了键映射到值的规则，而AbstractMap类提供 Map 接口的具体实现，以最大限度地减少实现此接口所需的工作。　　　

　　　　public class HashMap<K,V>

　　　　　　　　　　extends AbstractMap<K,V>

　　　　　　　　　　implements Map<K,V>, Cloneable, Serializable

基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了非同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

　　3、HashMap的构造方法摘要

　　　　HashMap的四个构造函数：

　　　　 HashMap():构造一个具有默认初始容量(16)和加载因子(0.75)的空HashMap。

　　　　 HashMap(int initialCapacity) :构造一个带指定初始容量和默认加载因子(0.75)的空HashMap。

　　　　 HashMap(int initialCapacity, float loadFactor)：构造一个带指定初始容量和加载因子的空HashMap。

　　　　 HashMap(Map<? extends K,? extends V> m) ：构造一个映射关系与指定Map相同的新HashMap。

　　HashMap 的实例有两个参数影响其性能：初始容量 和加载因子。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子 是哈希表在其容量自动增加之前可以达到多满的一种尺度。当哈希表中的条目数超出了加载因子与当前容量的乘积时，则要对该哈希表进行 rehash 操作（即重建内部数据结构），从而哈希表将具有大约两倍的桶数。

　　通常，默认加载因子 (0.75) 在时间和空间成本上寻求一种折衷。加载因子过高虽然减少了空间开销，但同时也增加了查询成本（在大多数 HashMap 类的操作中，包括 get 和 put 操作，都反映了这一点）。在设置初始容量时应该考虑到映射中所需的条目数及其加载因子，以便最大限度地减少 rehash 操作次数。如果初始容量大于最大条目数除以加载因子，则不会发生 rehash 操作。因此一般情况下无需修改。

　　如果很多映射关系要存储在 HashMap 实例中，则相对于按需执行自动的 rehash 操作以增大表的容量来说，使用足够大的初始容量创建它将使得映射关系能更有效地存储。

HashMap构造方法的源码如下图：

　　从源码中可以看出，每次新建一个HashMap时，都会初始化一个table数组。table数组的元素为Entry节点。

　　　4、HashMap的数据结构

　　从上图看出，HashMap的底层实现还是数组，只是数组的每一项都是一条链。其中参数initialCapacity就代表了该数组的长度。

HashMap为什么能随机存取？这里用了一个小算法：

1 // 存储时:       
2     int hash = key.hashCode(); // 每个key的hash是一个固定的int值
3         int index = hash % Entry[].length;
4     Entry[index] = value;
5 
6 // 取值时:
7         int hash = key.hashCode();
8         int index = hash % Entry[].length;
9         return Entry[index];

　　5、HashMap存取实现put（key,values）

　　通过源码我们可以清晰看到HashMap保存数据的过程为：首先判断key是否为null，若为null，则直接调用putForNullKey方法。若不为空则先计算key的hash值，然后根据hash值搜索在table数组中的索引位置，如果table数组在该位置处有元素，则通过比较是否存在相同的key，若存在则覆盖原来key的value（这样就保证了HashMap中没有两个相同的key），否则将该元素保存在链头（最先保存的元素放在链尾）。若table在该处没有元素，则直接保存。

　　首先，我们先看看当key为null时的putForNullKey方法源码：

　　null key总是存放在Entry[]数组的第一个元素。

　　其次，我们再看到HashMap的核心之一：hash方法，该方法为一个纯粹的数学计算，就是计算h的hash值。

　　我们知道对于HashMap的table而言，数据分布需要均匀（最好每项都只有一个元素，这样就可以直接找到），不能太紧也不能太松，太紧会导致查询速度慢，太松则浪费空间。计算hash值后，怎么才能保证table元素分布均与呢？我们会想到取模，但是由于取模的消耗较大，HashMap是这样处理的：调用indexFor方法。

　　再来看看HashMap的核心之二：indexFor方法

HashMap存取时，都需要计算当前key应该对应Entry[]数组哪个元素，即计算数组下标；算法如下：

　　HashMap的底层数组长度总是2的n次方。当length为2的n次方时，h&(length - 1)就相当于对length取模，这意味着数组下标相同，并不表示hashCode相同。而且速度比直接取模快得多。

　　最后，再看看addEntry方法，addEntry(hash, key, value, i);

这个方法中有两点需要注意：

链的产生。系统总是将新的Entry对象添加到bucketIndex处。如果bucketIndex处已经有了对象，那么新添加的Entry对象将指向原有的Entry对象，形成一条Entry链，但是若bucketIndex处没有Entry对象，也就是e==null,那么新添加的Entry对象指向null，也就不会产生Entry链了。
扩容问题。

随着HashMap中元素的数量越来越多，发生碰撞的概率就越来越大，所产生的链表长度就会越来越长，这样势必会影响HashMap的速度，为了保证HashMap的效率，系统必须要在某个临界点进行扩容处理。该临界点在当HashMap中元素的数量等于table数组长度*加载因子。但是扩容是一个非常耗时的过程，因为它需要重新计算这些数据在新table数组中的位置并进行复制处理。所以如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

　　6、HashMap存取实现get（key,values）

　　HashMap在存储过程中并没有将key，value分开来存储，而是作为一个Entry对象。在存储的过程中，系统根据key的hashcode来决定Entry在table数组中的存储位置，在取的过程中同样根据key的hashcode取出相对应的Entry对象。

　　7、再散列rehash过程

　　当哈希表的容量超过默认容量时，则会调整table的大小。当容量已经达到最大可能值时，那么该方法就将容量调整到Integer.MAX_VALUE返回，这时，需要创建一张新表，将原表的映射到新表中。

PS:如果觉得文章有地方写得不对，请指正我们共同学习；如果你觉得文章对你有所帮助，别忘了推荐或者分享！

本文版权归作者和博客园共有，欢迎转载，但未经作者同意必须保留此段声明，且在文章页面明显位置给出原文连接，否则保留追究法律责任的权利。

本文在撰写中参考过以下两位博主的文章：

http://blog.csdn.net/vking_wang/article/details/14166593

http://www.cnblogs.com/chenssy/p/3521565.html