常常应用 Java 的 HashMap，但你有理解过其外部的实现原理么？数据是如何存储的？哈希抵触是如何解决的？
本篇文章将带你深刻源码探索 HashMap 的实现原理。
文档正文
HashMap 是 Map 接口的实现类，实现了所有可选的操作，并且容许 null key 和 null value。（能够简略的了解与 HashTable 性能雷同，除了它是不同步的，以及反对空值。）
存取效率：在存储的元素均匀分布在桶中时，get 和 put 元素的工夫不变。遍历的效率与 capacity 相干，因而如果重视遍历的效率，不要把 capacity 初始值设的很大，或把负载系数设的很小。
非同步：不要用多线程同时批改。
一、类定义
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {继承自 AbstractMap，并实现 Map、Cloneable、Serializable 接口。
一）实现的接口
Cloneable和 Serializabel 都是标识接口，外面没有办法定义。实现这种接口仅用于标识这个类应该有这中性能。
Map接口中定义了要实现的办法，并且给出了局部办法的实现。
https://blog.csdn.net/weixin_44203158/article/details/109340113
Q：接口外面能够实现办法么？
A：是能够的！
从 Java8 之后增加了这个性能，次要思考的是若接口发生变化，所有的实现类都要跟着进行批改。但有了接口能够实现办法后，就不必再改实现类了。
Q：接口中实现办法有default和static两种润饰？
A：用default润饰的叫默认办法，用static润饰的叫静态方法。default能够被重写，然而static不行。
Q：实现多个接口的默认办法抵触怎么办？
A：在实现类中重写，且可调用接口中默认的办法。
Q：那为什么不必抽象类？
A：抽象类不能多继承。
二）继承的类
AbstractMap 抽象类提供对 Map 接口的根本实现，以加重实现 Map 接口的工作量。
对于不可变的 Map 实现类，只须要实现 entrySet() 办法。
对于可变的 Map 实现类，还须要实现 put()、remove() 等办法。
二、成员变量
/** * The default initial capacity - MUST be a power of two. */ static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16 /** * The maximum capacity, used if a higher value is implicitly specified * by either of the constructors with arguments. * MUST be a power of two <= 1<<30. */ static final int MAXIMUM_CAPACITY = 1 << 30; /** * The load factor used when none specified in constructor. */ static final float DEFAULT_LOAD_FACTOR = 0.75f; /** * The bin count threshold for using a tree rather than list for a * bin. Bins are converted to trees when adding an element to a * bin with at least this many nodes. The value must be greater * than 2 and should be at least 8 to mesh with assumptions in * tree removal about conversion back to plain bins upon * shrinkage. */ static final int TREEIFY_THRESHOLD = 8; /** * The bin count threshold for untreeifying a (split) bin during a * resize operation. Should be less than TREEIFY_THRESHOLD, and at * most 6 to mesh with shrinkage detection under removal. */ static final int UNTREEIFY_THRESHOLD = 6; /** * The smallest table capacity for which bins may be treeified. * (Otherwise the table is resized if too many nodes in a bin.) * Should be at least 4 * TREEIFY_THRESHOLD to avoid conflicts * between resizing and treeification thresholds. */ static final int MIN_TREEIFY_CAPACITY = 64;从变量和正文中能看出 HashMap 类的局部个性
- 定义容量须要是 2 的次方数。因而示意的时候也用位运算来定义的
- 默认负载达到 75% 时会扩容
- 单个桶存的元素数大于 8 会变为树形存储，小于 6 改回列式存储
- 当 capacity 大于 64 时，才会触发单节点的树形转换
容量为什么应用 2 的次方数？
在HashMap中采纳的是除留余数法，即table[hash % length]
在古代CPU中求余是最慢的操作，所以人们想到一种奇妙的办法来优化它，即length为2的指数幂时，hash % length = hash & (length-1)
如何做到的？
https://www.cnblogs.com/sanzao/p/10245212.html
https://blog.csdn.net/u014540814/article/details/88354793
// 上面的代码用于调整容量，将容量调为下一个 2 次方数// 简略来说应用了位运算的形式，将这个数第一个 1 前面的所有位都换为 1static final int tableSizeFor(int cap) { int n = cap - 1; n |= n >>> 1; n |= n >>> 2; n |= n >>> 4; n |= n >>> 8; n |= n >>> 16; return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;}被标记为 transient 的变量
Q：transient 关键字是做什么的？
A：避免属性被序列化
Q：为什么要用 transient 润饰？
A：出于平安问题思考
transient Node<K,V>[] table;三、重要外部类
一）Node
最重要的外部类 Node，定义了 HashMap 中的节点。
/** * Basic hash bin node, used for most entries. (See below for * TreeNode subclass, and in LinkedHashMap for its Entry subclass.) */ 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) { this.hash = hash; this.key = key; this.value = value; this.next = next; } // ...... }留神到应用了泛型类
https://segmentfault.com/a/1190000002646193
Q：什么是泛型类？
A：类名 + 一对尖括号。 person<X>。在 JDK 5 中呈现。
Q：为什么要用泛型类？
A：其中一个重要起因是为了创立容器类。假如没有泛型，为了反对不同类型的容器，可能须要定义多个类来反对。但有了泛型能够只用定义一个。缩小了编码的冗余。
Q：泛型定义写在什么地位？
A：泛型类写到类名前面，泛型办法写到返回类型之前。
Q：泛型的类型是何时确定的？
A：应该是在编译时确定的。
有 4 个成员变量
final int hash;final K key;V value;Node<K,V> next;hashCode() 计算形式有些奇怪？
public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); // 为什么要用异或运算符？}四、重要函数
hash()
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }getNode()
这个外面体现了很多设计思维
first = tab[(n - 1) & hash]从这里能够猜出来- hash 底层放到了一个数组外面
- 容量设计为 2 的指数，在这里
n-1二进制全是 1，不便做 & 运算
在节点抵触时，会有两种检索抵触的形式。先判断是不是树节点，不是才程序遍历
final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,V> first, e; int n; K k; if ((tab = table) != null && (n = tab.length) > 0 && (first = tab[(n - 1) & hash]) != null) { 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); } } return null; }
putVal()
插入数据
- 表的空容量判断
- 桶上如果没有元素，间接新建
桶上如果已有元素
- 先判断 key 值是否存在，如果存在则将要替换 value
- 如果是树结构，依照树的形式解决
- 如果是列表构造，遍历看是否有 key 雷同的
若须要新建 Node 节点
- 树转换的计数 + 1
- table 存储量 + 1，若大于 threshold 则 resize()
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; if ((p = tab[i = (n - 1) & hash]) == null) tab[i] = newNode(hash, key, value, null); else { 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; } } ++modCount; if (++size > threshold) resize(); afterNodeInsertion(evict); return null; }resize()在扩容时会调用的函数
// 扩容时会依照 2 倍的形式扩容else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold// 重新整理数据for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) // 如果该节点没有 hash 抵触，则放到原位或者2倍的地位 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 如果有 hash 抵触，且抵触很多（用树状存储），会进行拆分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order // 有 hash 抵触，用列表寄存，整体放到 [j + oldCap] 地位上 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } 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; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } }}treeifyBin()final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; // 如果 table 自身容量还很小，先应用扩容 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { TreeNode<K,V> hd = null, tl = null; do { // 其实是调用 LinkedHashMap 构造方法，TreeNode 也是 LinkedHashMap 扩大而来 TreeNode<K,V> p = replacementTreeNode(e, null); // 这里是串成一个双向链表 if (tl == null) hd = p; else { p.prev = tl; tl.next = p; } tl = p; } while ((e = e.next) != null); if ((tab[index] = hd) != null) // 将链表转换成树（红黑树），暂不具体钻研了 hd.treeify(tab); } }前面函数大同小异，可本人探索。