Overview
HashMap是Java编程中最常用的数据结构之一，本文基于JDK1.8从源码角度来分析HashMap的存储结构和常用操作。HashMap实现了Map接口，Map接口的实现类还有Hashtable、LinkedListHashMap和TreeMap。具体的继承结构请参考JDK Document。
学过数据结构的同学都知道Hash表的实现方式，其实HashMap就是Hash表的一个实现。HashMap是key-value结构的，根据key的hashCode可以快速访问到key对应的value，访问操作的时间复杂度为O(1)。但HashMap在多线程的场景下并不能保证数据的一致性，如果要在多线程的场景下使用Map结构，可以考虑使用Collections工具类的synchronizedMap方法使HashMap变为线程安全的，同时也可以考虑使用ConcurrentHashMap。
那HashMap和其他几个Map接口的实现类有什么区别呢？
和Hashtable的区别：Hashtable是线程安全的，是JDK的遗留类，内部实现使用synchronized关键字对方法加锁，效率和并发性不好。在线程安全的场景下可以使用ConcurrentHashMap替代，ConcurrentHashMap内部实现使用了分段锁，效率和并发性都要比Hashtable好。另一个区别是HashMap可以有有个null键和多个null值，Hashtable是不可以的。
和LinkedHashMap的区别：LinkedHashMap是Map的实现类同时也是HashMap子类，与HashMap不同的地方在于LinkedHashMap底层使用链表实现，因此LinkedHashMap能够维护记录插入顺序，能够按次序访问，而HashMap的key是无序的，这一点和HashSet一致。
和TreeMap的区别：TreeMap实现了Map的同时也实现了SortedMap接口，底层基于RB-Tree（红黑树）实现，TreeMap能够根据自然序或者给定的比较器维护记录的存储顺序。需要注意的是，在使用TreeMap的时候key对象需要实现Comparable接口或者在构造TreeMap时传入自定义Comparator，否则会在运行时抛出java.lang.ClassCastException异常。
在使用Map时，需要确保key对象是不可变的，也就是说key的hash是不会改变的，如果key的hash发生变化，就会出现key访问不到value的情况。需要保证equals()方法和hashCode()方法所描述的对象是一致的，即两个对象的equals()方法返回true那么这两个对象的hashCode()方法也要返回相同的值。这也是重写equals()方法通常也要重写hashCode()方法的原因。
存储结构
HashMap的结构是数组、链表和RB-Tree的组合，总体来说是数组用来进行hash寻址，用链表存储hash冲突的Entry，在冲突多时用RB-Tree来提高存取效率。
在HashMap的结构中存储的是key-value实体Entry<K,V>，更准确的说是存储的Node<K,V>，Node<K,V>是HashMap的一个静态内部类，实现了Map.Entry接口。是key-value的包装类。
static class Node<K,V> implements Map.Entry<K,V> { final int hash; final K key; V value; Node<K,V> next; Node(int hash, K key, V value, Node<K,V> next) {...} public final K getKey() { return key; } public final V getValue() { return value; } public final String toString() { return key + "=" + value; } public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } public final V setValue(V newValue) {...} public final boolean equals(Object o) { if (o == this) return true; if (o instanceof Map.Entry) { Map.Entry<?,?> e = (Map.Entry<?,?>)o; if (Objects.equals(key, e.getKey()) && Objects.equals(value, e.getValue())) return true; } return false; } }
HashMap中有一个Node[]类型的字段，用来当做hash桶，Node中hash字段用来快速定位hash桶的索引。
transient Node<K,V>[] table; //（transient关键字作用是在序列化时过滤掉此字段）
除此之外，HashMap还有几个比较重要的字段。
//HashMap中所有key-value实体的集合 transient Set<Map.Entry<K,V>> entrySet; //当前HashMap的大小（k-v实体个数） transient int size; //整个HashMap结构变化的次数 transient int modCount; //在下次扩容之前能容纳k-v实体的最大值，threshold=(capacity * load factor)。 int threshold; //负载因子 final float loadFactor;
初始化和扩容
HashMap的初始化时把HashMap所需要的数据结构和字段构造出来，并给定初始字段值。比如构造Node数组，设定初始化容量和负载因子等。这些可以通过HashMap的构造方法来实现。如果构造HashMap时不指定initialCapacity和loadFactor就会使用默认值，initialCapacity的默认值是16，HashMap的最大容量是2^30；默认的loadFactor值为0.75，含义是在存储数量达到当前Node[]数组长度的75%时进行下一次扩容。默认0.75也是hash冲突和空间利用率之间的权衡。
注意，loadFactor的值是可以大于1的，因为threshold=capacity * load factor，这里的capacity是Node[]数组的长度，除Node[]数组外使用链表和红黑树来存储冲突的记录，所以理论上整个HashMap对象存储的记录数可以大于capacity，也就是说size并不被capacity所限制。
当HashMap存储的记录数达到threshold=capacity * load factor后就要进行一次扩容，把容量扩大到之前的2倍，具体方法使创建一个新的长度为原来2倍的Node[]数组替换掉之前的Node[]数组。替换数组并不是简单的拷贝而是要把记录分散在新的数组中。在JDK1.8以前是采用rehash的方法，JDK1.8对此做了优化，避免了重新计算hash而且能将记录均匀的分散在新的Node[]数组中。具体做法是，在Node[]数组扩容到原来的2倍时，key的hash长度在原来的基础上多出一位，那么这一位可以是0也可以是1，当是0时索引不变，1时索引变为原索引+原容量。因为0和1是可以认为是随机的所以均匀分布的效果和rehash理论上是一致的。
来欣赏一下JDK1.8优化后的resize代码，简直是艺术品。
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { //超过2^30就不能再扩容了，把threshold设置为int最大值，就不会再扩容。 if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } //没有超过最大值就扩容到原先的2倍 else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold //第一次初始化并指定了容量 newCap = oldThr; else { // zero initial threshold signifies using defaults //第一次初始化没有指定容量，使用默认容量16 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { //计算新的threshold float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];//新的大桶 table = newTab; if (oldTab != null) { //把记录移动到新的桶中，并释放原有记录的引用。 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null)//没有冲突直接赋值 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode)//如果是红黑树节点，拆分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // 如果是链表节点，保留链表顺序 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; //如果新增高位为0，索引位置不变 if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } //如果新增高位为1，索引位置变为原索引+oldCap else { if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); //放置原索引位置 if (loTail != null) { loTail.next = null; newTab[j] = loHead; } //放置原索引+oldCap位置 if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }
put()方法分析
弄清楚了HashMap的结构和扩容机制，put()和get()操作直接按照步骤来分析就可以了。put()操作的主要是如下几个步骤：
- 首先判断Node[]数组table是否为空或null，如果是空那么进行一次resize，这次resize只是起到了一次初始化的作用。
- 根据key的值计算hash得到在table中的索引i，如果table[i]==null则添加新节点到table[i]，然后判断size是否超过了容量限制threshold，如果超过进行扩容。
- 如果在上一步table[i]不为null时，判断table[i]节点是否和当前添加节点相同（这里使用hash和equals判断，因此需要保证hashCode()方法和equals()方法描述的一致性），如果相同则覆盖该节点的value。
- 如果上一步判断table[i]和当前节点不同，那么判断table[i]是否为红黑树节点，如果是红黑树节点则在红黑树中添加此key-value。
- 如果上一步判断table[i]不是红黑树节点则遍历table[i]链表，判断链表长度是否超过8，如果超过则转为红黑树存储，如果没有超过则在链表中插入此key-value。（jdk1.8以前使用头插法插入）。在遍历过程中，如果发现有相同的节点（比较hash和equals）就覆盖value。
- 维护modCount和size等其他字段。
public V put(K key, V value) { //传入key的hash值，对hashCode值做位运算 return putVal(hash(key), key, value, false, true); } final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果tab为null，则通过resize初始化 if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //计算key的索引，如果为当前位置为null，直接赋值 if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { //如果当前位置不为null Node<K,V> e; K k; //如果相同直接覆盖 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //如果是红黑树节点，添加节点到红黑树，如果过程中发现相同节点则覆盖 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); //如果是链表节点 else { for (int binCount = 0; ; ++binCount) { //如果 if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; } //找到相同节点则覆盖 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; } } //覆盖 if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } //结构变化次数+1 ++modCount; //如果size超过最大限制，扩容 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
get()方法分析
明确了put()方法，get()方法的分析就变得非常容易了，首先看一下如何通过hash确定key在桶中的索引位置。
static final int hash(Object key) { //jdk1.8 & jdk1.7 int h; // h = key.hashCode() 为第一步 取hashCode值 // h ^ (h >>> 16) 为第二步 高位参与运算 return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); } //jdk1.8已经把这个方法省略了，但是在访问时直接使用这个计算策略。 static int indexFor(int h, int length) { return h & (length-1); //第三步 取模运算 }
如下就是get()方法的具体分析：
public V get(Object key) { Node<K,V> e; //传入key的hash return (e = getNode(hash(key), key)) == null ? null : e.value; } final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; //这里访问(n - 1) & hash其实就是jdk1.7中indexFor方法的作用 if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { //判断桶索引位置的节点是不是相同（通过hash和equals判断），如果相同返回此节点 if (first.hash == hash && // always check first node ((k = first.key) == key || (key != null && key.equals(k)))) return first; if ((e = first.next) != null) { //判断是否是红黑树节点，如果是查找红黑树 if (first instanceof TreeNode) return ((TreeNode<K,V>)first).getTreeNode(hash, key); do { //如果是链表，遍历链表 if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) return e; } while ((e = e.next) != null); } } //如果不存在返回null return null; }
补充
除以上的分析以外，HashMap还有许多其他方法，包括判空、删除、清空、替换、遍历以及JDK1.8新增的函数式语法和Lambda表达式的内容。代码总行数多达两千多行，如果感兴趣或遇到相应问题可以具体分析。已经了解了HashMap的存储结构和关键操作的步骤，再去分析其他方法就比较容易了。
小结
从以上的对HashMap源码的分析，可以得出一些使用上的技巧和有用的结论。
- HashMap不是线程安全的，多线程的场景推荐使用ConcurrentHashMap。
- JDK1.8对HashMap做了大量优化，值得尝试。
- 在初始化时最好能够给出估算的容量大小，避免频繁扩容影响使用效率。
- 负载因子是可以修改的，但是0.75是容量和冲突之间的权衡，如果不是目的特别明确不要轻易修改。
- 重写equals()方法的同时也要重写hashCode()方法。
- HashMap源码写的真棒:）
参考资料：
Java™ Platform, Standard Edition 8 API Specification
java.util.HashMap源码