2017-07-31 19:36:00

一、简介

1、HashMap作用及使用场景

HashMap利用数组+单向链表的方式，实现了key-value型数据的存储功能。HashMap的size永远是2^x的值，主要是为了更加均衡的使用数组位置。

2、存储key-value型数据的数据结构

如下代码，HashMap中定义了Node类，实现了Map.Entry接口，Entry接口只有set和get方法定义，极其简单。Node中定义了key、value、hash及指向下一个Node的指针next，Node类其实也可以作为单向链表。

3、HashMap的存储方式

HashMap采用数组+链表的方式存储数据，链表就是前面提到的Node类，数组如下：

4、HashMap几个重要参数

要想了解HashMap的扩容策略，先看看这几个默认值：

默认容量为16，最大容量为2^30，默认加载因子0.75f。后面3个TREEIFY相关的参数，都是使用tree存存数据时所用，暂时不用理会。

再看几个成员变量：

如上图：

table：存数据的数组；

entrySet：是entrySet()的返回值，被当做缓存，这样调用entrySet()方法时不用每次都重新创建一个Set对象；

size：key-value数据的数量；

modCount：防止并发修改的标志位；

threshold：临界值，超过这个临界值要需要扩容；

loadFactor：加载因子，用于计算临界值；

5、HashMap初始容量

HashMap的处理容量要么是默认值，要么使用用户设置的capacity，先看默认值。使用new HashMap()构造器，会使用默认capacity，代码如下：

奇怪了，这里怎么没有new数组呢？构造器中没有创建数组，说明数组的创建采用的是lazy策略，肯定要在put元素之前创建，要么数据存哪里？看看put方法，put方法调用了包级访问权限的putVal()，putVal()又调用了resize()，有如下代码：

看到了吧，如果table数组为null，在这里创建了数组。

那么用户设置了capacity的HashMap是如何初始化的？使用new HashMap(int capacity)构造器：

最终调用了这个构造器，加载因子是默认值。这里也并没有new数组，而是计算了临界值。在前一张图片resize()方法中，如果table的size为0，且newThr大于0，则会按照newThr的大小创建数组。前面提到HashMap的size永远是2的幂次值，那现在看看newThr是怎么计算出来的？看看tableSizeFor()方法：

这个方法的作用找到最小的大于cap的2^n的值，so即便我们设置不是一个2^n的值，HashMap也会帮我们处理的。至于为什么一定要是2^n，后面再详细解释。 

====================================================================================================================

注：以上分析基于jdk中HashMap源码，从现在开始使用Android的HashMap源码分析，主要原因是Android的HashMap源码中剔除了一些无用的代码，结构更加清晰，便于了解其原理。

====================================================================================================================

二、HashMap中一些重要的方法

1、put(K key， V value)及扩容原理

如上代码，如果加入的数据key=null，则执行如下逻辑：

【Java集合系列五】HashMap解析