01、摘要
在集合系列的第一章，咱们了解到，Map 的实现类有 HashMap、LinkedHashMap、TreeMap、IdentityHashMap、WeakHashMap、Hashtable、Properties 等等。
关于 HashMap，一直都是一个非常热门的话题，只要你出去面试，我保证一定少不了它！
本文主要结合 JDK1.7 和 JDK1.8 的区别，就 HashMap 的数据结构和实现功能，进行深入探讨，废话也不多说了，直奔主题！
02、简介
“在程序编程的时候，HashMap 是一个使用非常频繁的容器类，它允许键值都放入 null 元素。除该类方法未实现同步外，其余跟 Hashtable 大致相同，但跟 TreeMap 不同，该容器不保证元素顺序，根据需要该容器可能会对元素重新哈希，元素的顺序也会被重新打散，因此不同时间迭代同一个 HashMap 的顺序可能会不同。
HashMap 容器，实质还是一个哈希数组结构，但是在元素插入的时候，存在发生 hash 冲突的可能性；
对于发生 Hash 冲突的情况，冲突有两种实现方式，一种开放地址方式（当发生 hash 冲突时，就继续以此继续寻找，直到找到没有冲突的 hash 值），另一种是拉链方式（将冲突的元素放入链表）。Java HashMap 采用的就是第二种方式，拉链法。
在 jdk1.7 中，HashMap 主要是由数组+链表组成，当发生 hash 冲突的时候，就将冲突的元素放入链表中。
从 jdk1.8 开始，HashMap 主要是由数组+链表+红黑树实现的，相比 jdk1.7 而言，多了一个红黑树实现。当链表长度超过 8 的时候，就将链表变成红黑树，如图所示。
关于红黑树的实现，因为篇幅太长，在《集合系列》文章中红黑树设计，也有所介绍，这里就不在详细介绍了。
03、源码解析
直接打开 HashMap 的源码分析，可以看到，主要有 5 个关键参数：
- threshold：表示容器所能容纳的 key-value 对极限。
- loadFactor：负载因子。
- modCount：记录修改次数。
- size：表示实际存在的键值对数量。
- table：一个哈希桶数组，键值对就存放在里面。
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable { //所能容纳的key-value对极限 int threshold; //负载因子 final float loadFactor; //记录修改次数 int modCount; //实际存在的键值对数量 int size; //哈希桶数组 transient Node<K,V>[] table; }
接着来看看Node这个类，Node是HashMap的一个内部类，实现了Map.Entry接口，本质是就是一个映射(键值对)
static class Node<K,V> implements Map.Entry<K,V> { final int hash;//hash值 final K key;//k键 V value;//value值 Node<K,V> next;//链表中下一个元素 }
在 HashMap 的数据结构中，有两个参数可以影响 HashMap 的性能：初始容量（inital capacity）和负载因子（load factor）。
初始容量（inital capacity）是指 table 的初始长度 length（默认值是 16）；
负载因子（load factor）用指自动扩容的临界值（默认值是 0.75）；
threshold是HashMap所能容纳的最大数据量的Node(键值对)个数，计算公式threshold = capacity * Load factor。当 entry 的数量超过capacity*load_factor时，容器将自动扩容并重新哈希，扩容后的HashMap容量是之前容量的两倍，所以数组的长度总是 2 的 n 次方。
初始容量和负载因子也可以修改，具体实现方式，可以在对象初始化的时候，指定参数，比如：
Map map = new HashMap(int initialCapacity, float loadFactor);
但是，默认的负载因子 0.75 是对空间和时间效率的一个平衡选择，建议大家不要修改，除非在时间和空间比较特殊的情况下，如果内存空间很多而又对时间效率要求很高，可以降低负载因子 Load factor 的值；相反，如果内存空间紧张而对时间效率要求不高，可以增加负载因子 loadFactor 的值，这个值可以大于 1。同时，对于插入元素较多的场景，可以将初始容量设大，减少重新哈希的次数。
HashMap 的内部功能实现有很多，本文主要从以下几点，进行逐步分析。
- 通过 K 获取数组下标；
- put 方法的详细执行；
- resize 扩容过程；
- get 方法获取参数值；
- remove 删除元素；
3.1、通过 K 获取数组下标
不管增加、删除还是查找键值对，定位到数组的位置都是很关键的第一步，打开 hashMap 的任意一个增加、删除、查找方法，从源码可以看出，通过key获取数组下标，主要做了 3 步操作，其中length指的是容器数组的大小。
源码部分：
/**获取hash值方法*/ static final int hash(Object key) { int h; // h = key.hashCode() 为第一步 取hashCode值（jdk1.7） // h ^ (h >>> 16) 为第二步 高位参与运算（jdk1.7） return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//jdk1.8 } /**获取数组下标方法*/ static int indexFor(int h, int length) { //jdk1.7的源码，jdk1.8没有这个方法，但是实现原理一样的 return h & (length-1); //第三步 取模运算 }
3.2、put 方法的详细执行
put(K key, V value)方法是将指定的 key, value 对添加到 map 里。该方法首先会对 map 做一次查找，看是否包含该 K，如果已经包含则直接返回；如果没有找到，则将元素插入容器。具体插入过程如下：
具体执行步骤
- 1、判断键值对数组 table[i]是否为空或为 null，否则执行 resize()进行扩容；
- 2、根据键值 key 计算 hash 值得到插入的数组索引 i，如果 table[i]==null，直接新建节点添加；
- 3、当 table[i]不为空，判断 table[i]的首个元素是否和传入的 key 一样，如果相同直接覆盖 value；
- 4、判断 table[i] 是否为 treeNode，即 table[i] 是否是红黑树，如果是红黑树，则直接在树中插入键值对；
- 5、遍历 table[i]，判断链表长度是否大于 8，大于 8 的话把链表转换为红黑树，在红黑树中执行插入操作，否则进行链表的插入操作；遍历过程中若发现 key 已经存在直接覆盖 value 即可；
- 6、插入成功后，判断实际存在的键值对数量 size 是否超多了最大容量 threshold，如果超过，进行扩容操作；
put 方法源码部分
/** * put方法 */ public V put(K key, V value) { 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; //1、判断数组table是否为空或为null if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //2、判断数组下标table[i]==null if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { Node<K,V> e; K k; //3、判断table[i]的首个元素是否和传入的key一样 if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; //4、判断table[i] 是否为treeNode else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //5、遍历table[i]，判断链表长度是否大于8 for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { p.next = newNode(hash, key, value, null); //长度大于8，转红黑树结构 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; } } //传入的K元素已经存在，直接覆盖value if (e != null) { // existing mapping for key V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; //6、判断size是否超出最大容量 if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }
其中，与 jdk1.7 有区别的地方，第 4 步新增了红黑树插入方法，源码部分：
/** * 红黑树的插入操作 */ final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V>[] tab, int h, K k, V v) { Class<?> kc = null; boolean searched = false; TreeNode<K,V> root = (parent != null) ? root() : this; for (TreeNode<K,V> p = root;;) { //dir:遍历的方向， ph:p节点的hash值 int dir, ph; K pk; //红黑树是根据hash值来判断大小 // -1:左孩子方向 1:右孩子方向 if ((ph = p.hash) > h) dir = -1; else if (ph < h) dir = 1; //如果key存在的话就直接返回当前节点 else if ((pk = p.key) == k || (k != null && k.equals(pk))) return p; //如果当前插入的类型和正在比较的节点的Key是Comparable的话，就直接通过此接口比较 else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) { if (!searched) { TreeNode<K,V> q, ch; searched = true; //尝试在p的左子树或者右子树中找到了目标元素 if (((ch = p.left) != null && (q = ch.find(h, k, kc)) != null) || ((ch = p.right) != null && (q = ch.find(h, k, kc)) != null)) return q; } //获取遍历的方向 dir = tieBreakOrder(k, pk); } //上面的所有if-else判断都是在判断下一次进行遍历的方向，即dir TreeNode<K,V> xp = p; //当下面的if判断进去之后就代表找到了目标操作元素,即xp if ((p = (dir <= 0) ? p.left : p.right) == null) { Node<K,V> xpn = xp.next; //插入新的元素 TreeNode<K,V> x = map.newTreeNode(h, k, v, xpn); if (dir <= 0) xp.left = x; else xp.right = x; //因为TreeNode今后可能退化成链表，在这里需要维护链表的next属性 xp.next = x; //完成节点插入操作 x.parent = x.prev = xp; if (xpn != null) ((TreeNode<K,V>)xpn).prev = x; //插入操作完成之后就要进行一定的调整操作了 moveRootToFront(tab, balanceInsertion(root, x)); return null; } } }
