数据结构

在分析HashMap源码之前，有必要了解HashMap的数据结构，否则很难理解下面的内容。

从上图中可以很清楚的看到，HashMap的数据结构是数组+链表+红黑树（红黑树since JDK1.8）。我们常把数组中的每一个节点称为一个桶。当向桶中添加一个键值对时，首先计算键值对中key的hash值，以此确定插入数组中的位置，但是可能存在同一hash值的元素已经被放在数组同一位置了，这种现象称为碰撞，这时按照尾插法(jdk1.7及以前为头插法)的方式添加key-value到同一hash值的元素的后面，链表就这样形成了。当链表长度超过8(TREEIFY_THRESHOLD)时，链表就转换为红黑树。

顶部注释

HashMap是Map接口基于哈希表的实现。这种实现提供了所有可选的Map操作，并允许key和value为null（除了HashMap是unsynchronized的和允许使用null外，HashMap和HashTable大致相同。）。此类不保证映射的顺序，特别是它不保证该顺序恒久不变。

此实现假设哈希函数在桶内适当地分布元素，为基本实现(get 和 put)提供了稳定的性能。迭代 collection 视图所需的时间与 HashMap 实例的“容量”（桶的数量）及其大小（键-值映射关系数）成比例。如果遍历操作很重要，就不要把初始化容量initial capacity设置得太高（或将加载因子load factor设置得太低），否则会严重降低遍历的效率。

HashMap有两个影响性能的重要参数：初始化容量initial capacity、加载因子load factor。容量是哈希表中桶的数量，初始容量只是哈希表在创建时的容量。加载因子是哈希表在其容量自动增加之前可以达到多满的一种尺度。initial capacity*load factor就是当前允许的最大元素数目，超过initial capacity*load factor之后，HashMap就会进行rehashed操作来进行扩容，扩容后的的容量为之前的两倍。

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

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

注意，此实现不是同步的。如果多个线程同时访问一个哈希映射，而其中至少一个线程从结构上修改了该映射，则它必须保持外部同步。（结构上的修改是指添加或删除一个或多个映射关系的任何操作；仅改变与实例已经包含的键关联的值不是结构上的修改。）这一般通过对自然封装该映射的对象进行同步操作来完成。如果不存在这样的对象，则应该使用 Collections.synchronizedMap 方法来“包装”该映射。最好在创建时完成这一操作，以防止对映射进行意外的非同步访问，如下所示：
Map m = Collections.synchronizedMap(new HashMap(…));

由所有此类的“collection 视图方法”所返回的迭代器都是fail-fast 的：在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的remove方法，其他任何时间任何方式的修改，迭代器都将抛出 ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不冒在将来不确定的时间发生任意不确定行为的风险。

注意，迭代器的快速失败行为不能得到保证，一般来说，存在非同步的并发修改时，不可能作出任何坚决的保证。快速失败迭代器尽最大努力抛出 ConcurrentModificationException。因此，编写依赖于此异常的程序的做法是错误的，正确做法是：迭代器的快速失败行为应该仅用于检测bug。

此类是 Java Collections Framework 的成员。

从上面的内容中可以总结出以下几点：

• 底层：HashMap是Map接口基于哈希表的实现。
• 是否允许null：HashMap允许key和value为null。
• 是否有序：HashMap不保证映射的顺序，特别是它不保证该顺序恒久不变。
• 何时rehash：超出当前允许的最大容量。initial capacity*load factor就是当前允许的最大元素数目，超过initial capacity*load factor之后，HashMap就会进行rehashed操作来进行扩容，扩容后的的容量为之前的两倍。
• 初始化容量对性能的影响：不应设置地太小，设置地小虽然可以节省空间，但会频繁地进行rehash操作。rehash会影响性能。总结：小了会增大时间开销（频繁rehash）；大了会增大空间开销（占用了更多空间）和时间开销（影响遍历）。
• 加载因子对性能的影响：加载因子过高虽然减少了空间开销，但同时也增加了查询成本。0.75是个折中的选择。总结：小了会增大时间开销（频繁rehash）；大了会也增大时间开销（影响遍历）。
• 是否同步：HashMap不是同步的。
• 迭代器：迭代器是fast-fail的。

定义

先来看看HashMap的定义：

public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable

从中我们可以了解到：

• HashMap<K,V>：HashMap是以key-value形式存储数据的。
• extends AbstractMap<K,V>：继承了AbstractMap，大大减少了实现Map接口时需要的工作量。
• implements Map<K,V>：实现了Map，提供了所有可选的Map操作。
• implements Cloneable：表明其可以调用clone()方法来返回实例的field-for-field拷贝。
• implements Serializable：表明该类是可以序列化的。

下图是HashMap的类结构层次图。

静态全局变量

    /*** 默认初始化容量，值为16* 必须是2的n次幂.*/static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16/*** 最大容量, 容量不能超出这个值。如果一个更大的初始化容量在构造函数中被指定，将被MAXIMUM_CAPACITY替换.* 必须是2的倍数。最大容量为1<<30，即2的30次方。*/static final int MAXIMUM_CAPACITY = 1 << 30;/*** 默认的加载因子。*/static final float DEFAULT_LOAD_FACTOR = 0.75f;/*** 将链表转化为红黑树的临界值。* 当添加一个元素被添加到有至少TREEIFY_THRESHOLD个节点的桶中，桶中链表将被转化为树形结构。* 临界值最小为8*/static final int TREEIFY_THRESHOLD = 8;/*** 恢复成链式结构的桶大小临界值* 小于TREEIFY_THRESHOLD，临界值最大为6*/static final int UNTREEIFY_THRESHOLD = 6;/*** 桶可能被转化为树形结构的最小容量。当哈希表的大小超过这个阈值，才会把链式结构转化成树型结构，否则仅采取扩容来尝试减少冲突。* 应该至少4*TREEIFY_THRESHOLD来避免扩容和树形结构化之间的冲突。*/static final int MIN_TREEIFY_CAPACITY = 64;

静态内部类Node

    /*** HashMap的节点类型。既是HashMap底层数组的组成元素，又是每个单向链表的组成元素*/static class Node<K,V> implements Map.Entry<K,V> {//key的哈希值final int hash;final K key;V value;//指向下个节点的引用Node<K,V> next;//构造函数Node(int hash, K key, V value, Node<K,V> next) {this.hash = hash;this.key = key;this.value = value;this.next = 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) {V oldValue = value;value = newValue;return oldValue;}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;}}

核心方法

get( Object key)

    /*** 返回指定的key映射的value，如果value为null，则返回null。** @see #put(Object, Object)*/public V get(Object key) {Node<K,V> e;//如果通过key获取到的node为null，则返回null，否则返回node的value。getNode方法的实现就在下面。return (e = getNode(hash(key), key)) == null ? null : e.value;}

从源码中可以看到，get(E e)可以分为三个步骤：

1. 通过hash(Object key)方法计算key的哈希值hash。
2. 通过getNode( int hash, Object key)方法获取node。
3. 如果node为null，返回null，否则返回node.value。

先来看看哈希值是如何计算的。

hash( Object key)

不管增加、删除、查找键值对，定位到哈希桶数组的位置都是很关键的第一步。计算位置的方法如下

(n - 1) & hash

其中的n为数组的长度，hash为hash(key)计算得到的值。

    /*** 计算key的哈希值。*/static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);}

从代码中可以看到，计算位置分为三步，第一步，取key的hashCode，第二步，key的hashCode高16位异或低16位，第三步，将第一步和第二部得到的结果进行取模运算。

为什么要做异或运算？

设想一下，如果n很小，假设为16的话，那么n-1即为15（0000 0000 0000 0000 0000 0000 0000 1111），这样的值如果跟hashCode()直接做与操作，实际上只使用了哈希值的后4位。如果当哈希值的高位变化很大，低位变化很小，这样很容易造成碰撞，所以把高低位都参与到计算中，从而解决了这个问题，而且也不会有太大的开销。

为什么要做按位与运算 & 而不用%取模的方式  ？

因为按位与运算的效率比百分号取模的运算效率高很多。这里的桶容量为什么设置成2的n次方，这里是16，因为这样如上图所示高位全是0，因此与hash按位与运算（上下都是1就是1，否则是0）之后的余数恰好就是hash%n。

看完哈希值是如何计算之后，看看如何通过key和hash获取node。

getNode( int hash, Object key)

    /*** 根据key的哈希值和key获取对应的节点** @param hash 指定参数key的哈希值* @param key 指定参数key* @return 返回node，如果没有则返回null*/final Node<K,V> getNode(int hash, Object key) {Node<K,V>[] tab; Node<K,V> first, e; int n; K k;//如果哈希表不为空，而且key对应的桶上不为空if ((tab = table) != null && (n = tab.length) > 0 &&(first = tab[(n - 1) & hash]) != null) {//如果桶中的第一个节点就和指定参数hash和key匹配上了if (first.hash == hash && // always check first node((k = first.key) == key || (key != null && key.equals(k))))//返回桶中的第一个节点return first;//如果桶中的第一个节点没有匹配上，而且有后续节点if ((e = first.next) != null) {//如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点if (first instanceof TreeNode)return ((TreeNode<K,V>)first).getTreeNode(hash, key);//如果当前的桶不采用红黑树，即桶中节点结构为链式结构do {//遍历链表，直到key匹配if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))return e;} while ((e = e.next) != null);}}//如果哈希表为空，或者没有找到节点，返回nullreturn null;}//如果当前不是树根节点通过root()方法寻找树根，然后掉用find方法final TreeNode<K,V> getTreeNode(int h, Object k) {return ((parent != null) ? root() : this).find(h, k, null);}

    /*** 通过给定的hash 和 key 从树根节点寻找指定的节点返回* The kc argument caches comparableClassFor(key) upon first use* comparing keys.*/final TreeNode<K,V> find(int h, Object k, Class<?> kc) {TreeNode<K,V> p = this;do {int ph, dir; K pk;//这个树根据hash排序的，TreeNode<K,V> pl = p.left, pr = p.right, q;// 如果比当前hash小走左子树if ((ph = p.hash) > h)p = pl;// 如果比当前hash大走右子树else if (ph < h)p = pr;//当前节点hash正好等于给定的hash，且key正好等于给定的key，返回该节点else if ((pk = p.key) == k || (k != null && k.equals(pk)))return p;//如果左子树恰好为空，走右子树else if (pl == null)p = pr;//如果右子树恰好为空，走左子树else if (pr == null)p = pl;//这里只会是一种情况当前节点hash等于给定hash，但是key不等于给定的keyelse if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;else if ((q = pr.find(h, k, kc)) != null)return q;elsep = pl;} while (p != null);return null;}

compareableClassFor(Object x)

  /*** 如果对象x的类是C，如果C实现了Comparable<C>接口，那么返回C，否则返回null*/static Class<?> comparableClassFor(Object x) {if (x instanceof Comparable) {Class<?> c; Type[] ts, as; Type t; ParameterizedType p;if ((c = x.getClass()) == String.class) // 如果x是个字符串对象return c; // 返回String.class/** 为什么如果x是个字符串就直接返回c了呢 ? 因为String  实现了 Comparable 接口，可参考如下String类的定义* public final class String implements java.io.Serializable, Comparable<String>, CharSequence*/// 如果 c 不是字符串类，获取c直接实现的接口（如果是泛型接口则附带泛型信息）if ((ts = c.getGenericInterfaces()) != null) {for (int i = 0; i < ts.length; ++i) { // 遍历接口数组// 如果当前接口t是个泛型接口// 如果该泛型接口t的原始类型p 是 Comparable 接口// 如果该Comparable接口p只定义了一个泛型参数// 如果这一个泛型参数的类型就是c，那么返回cif (((t = ts[i]) instanceof ParameterizedType) &&((p = (ParameterizedType)t).getRawType() ==Comparable.class) &&(as = p.getActualTypeArguments()) != null &&as.length == 1 && as[0] == c) // type arg is creturn c;}// 上面for循环的目的就是为了看看x的class是否 implements  Comparable<x的class>}}return null; // 如果c并没有实现 Comparable<c> 那么返回空}

compareComparables(Class<?> kc, Object k, Object x)

 /*** 经过上面的方法之后，到了这里一定是实现了Comparable接口* 如果x所属的类是kc，返回k.compareTo(x)的比较结果* 如果x为空，或者其所属的类不是kc，返回0*/@SuppressWarnings({"rawtypes","unchecked"}) // for cast to Comparablestatic int compareComparables(Class<?> kc, Object k, Object x) {return (x == null || x.getClass() != kc ? 0 :((Comparable) k).compareTo(x));}

get方法总结

从源码中可以看到，get(E e)可以分为三个步骤：

1. 通过hash(Object key)方法计算key的哈希值hash。
2. 通过getNode( int hash, Object key)方法获取node。
3. 如果node为null，返回null，否则返回node.value。

hash方法又可分为三步：

1. 取key的hashCode第二步
2. key的hashCode高16位异或低16位
3. 将第一步和第二部得到的结果进行取模运算。

getNode方法又可分为以下几个步骤：

1. 如果哈希表为空，或key对应的桶为空，返回null
2. 如果桶中的第一个节点就和指定参数hash和key匹配上了，返回这个节点。
3. 如果桶中的第一个节点没有匹配上，而且有后续节点
   1. 如果当前的桶采用红黑树，则调用红黑树的get方法去获取节点
   2. 如果当前的桶不采用红黑树，即桶中节点结构为链式结构，遍历链表，直到key匹配
4. 找到节点返回null，否则返回null。