JDK源码分析(三)——HashMap 上（基于JDK7）

HashMap概述

  前面我们分析了基于数组实现的ArrayList和基于双向链表实现的LinkedList,它们各有优缺点：ArrayList查找元素快但是插入删除元素慢，LinkedList插入删除元素快但是查找元素慢。那么有没有一种数据对象能够做到高效的查询和插入删除呢？答案是有的，HashMap就能够很好的满足这个特性。
  由于JDK1.8对HashMap进行了优化，与JDK1.7版本的实现有很大的不同，相对来说也要负责一些，故本文以JDK1.7版本的HashMap为基础进行分析，主要分析HashMap的内部结构及插入扩容原理；将在下一篇文章分析JDK1.8版本的HashMap带来了那些改进和优化。
  JDK api是这样介绍HashMap的：

Hash table based implementation of the Map interface. This implementation provides all of the optional map operations, and permits null values and the null key. (The HashMap class is roughly equivalent to Hashtable, except that it is unsynchronized and permits nulls.) This class makes no guarantees as to the order of the map; in particular, it does not guarantee that the order will remain constant over time.

大意是HashMap是基于哈希表对Map接口的实现，此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了是线程不安全的和允许null键值对插入，HashMap大致等同于HashTable）,HashMap不保证映射的顺序，特别是它不保证该顺序恒久不变。

HashMap数据结构

  画了个示意图如下，由图可知，HashMap基于数组和单链表实现。使用过HashMap都知道，它储存的是键值对，当我们存储键值对时，先根据哈希算法计算出哈希值，根据计算出来的哈希值映射到数组上得到一个索引，可能会有多个对象映射到同一个索引上，就是图片上出现单链表的情况，这时候就产生了哈希冲突，一个好的算法能够尽量避免哈希冲突。根据哈希值，HashMap能够以几乎O(1)的复杂度存储或查询元素，效率相当高。

HashMap继承结构

  HashMap 继承了 AbstractMap 类，并实现了 Map、Cloneable 和 Serializable 接口。AbstractMap提供了Map接口的抽象实现，并提供了一些方法的基本实现。注意，Map接口属于集合框架，但并没有继承 Collection 接口，实际上Map接口是与Collection接口同级别的接口。

内部字段及构造方法 Entry类

  键值对Entry对象存储了键值对key-value，这里的next属性指向发生哈希冲突了的键值对对象。

static class Entry<K,V> implements Map.Entry<K,V> { //键对象，final修饰，不可变 final K key; //值对象 V value; //下一个键值对Entry对象 Entry<K,V> next; //键对象的哈希值 int hash; //提供了一个有参构造方法 Entry(int h, K k, V v, Entry<K,V> n) { value = v; next = n; key = k; hash = h; } } 字段属性

  HashMap的底层是由数组和链表实现的，JDK注释中把Entry数组称为桶，这里规定了桶的默认容量和最大容量。对于桶的容量JDK官方注释都会有这么一句：MUST be a power of two，桶的容量一定要是2的幂次，这里先说结论：桶的容量是2的N次方能够减少哈希冲突，提高桶的利用率，至于原因我们会在后面分析。
  加载因子loadFactor和阈值threshold是一对密不可分的概念，在当前桶的容量下，存储键值对个数超过threshold就会进行扩容，阈值threshold等于桶的容量乘以加载因子；加载因子一般我们就用默认的0.75f,加载因子设置的太小，桶的利用率低，而且频繁扩容也会降低HashMap的性能，设置的加载因子太大，键值对越存越多容易发生哈希冲突，所以0.75是时间复杂度与空间复杂度的一个平衡点。

//桶的初始化默认的长度 static final int DEFAULT_INITIAL_CAPACITY = 16; //桶的最大长度 static final int MAXIMUM_CAPACITY = 1 << 30; //默认加载因子 static final float DEFAULT_LOAD_FACTOR = 0.75f; //Entry数组，空桶 transient Entry<K,V>[] table; //储存元素个数 transient int size; //桶内存储键值对个数的阈值，超过阈值对桶进行resize int threshold; //加载因子 final float loadFactor; //确保fail-fast机制 transient int modCount; // 备选的负载值，以String作为Key时的备选负载值。 static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE; 构造方法

  我们常用的雾草构造器，会调用的HashMap(int initialCapacity, float loadFactor)构造方法，按照默认初始容量为16，加载因子为0.75构造HashMap对象。

public HashMap(int initialCapacity, float loadFactor) { //检查参数有效性 if (initialCapacity < 0) throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) throw new IllegalArgumentException("Illegal load factor: " + loadFactor); // Find a power of 2 >= initialCapacity //注意这个容量并不是直接用输入的参数，而是通过循环左移找到比initialCapacity //且离它最近的2的幂次。如输入12，容量初始化为16 int capacity = 1; while (capacity < initialCapacity) capacity <<= 1; this.loadFactor = loadFactor; //阈值等于桶的容量乘以加载因子（不超过最大容量） threshold = (int)Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); table = new Entry[capacity]; useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); //空方法 init(); } //生成一个空的HashMap,容量大小使用默认值16，负载因子使用默认值0.75 public HashMap() { this(DEFAULT_INITIAL_CAPACITY, DEFAULT_LOAD_FACTOR); } //生成一个空的HashMap,并指定其容量大小，负载因子使用默认的0.75 public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); } public HashMap(Map<? extends K, ? extends V> m) { //实际容量为m.size/0.75和16较大者，0.75f作为加载因子 this(Math.max((int) (m.size() / DEFAULT_LOAD_FACTOR) + 1, DEFAULT_INITIAL_CAPACITY), DEFAULT_LOAD_FACTOR); // 将传入的子Map中的全部元素逐个添加到HashMap中 putAllForCreate(m); } 存储元素 put(K key, V value)