HashMap 是 Java 中非常重要的集合类型，其具有快速存储，快速查找（时间复杂度非常低，非效非常高），自动扩容等特点，在实际开发中经常用到。
关于 HashMap 特性，底层原理也是面试中被问到概率极高的问题，因为 HashMap 涉及到好几个基本数据结构及相关算法知识，如组数，链表，二叉树及变种，Hash算法等。所以有必要对其深入理解。
哈希表
HashMap 使用了基本的数据结构，先了解下有助于理解。详细可能考 数据结构与算法(一)：数组、链表、哈希表。
哈希表（Hash Table）：，提供键（Key） 和值（Value）映射关系。只要给出 key ，就可以高效查找到映射的 Value，时间复杂度接近于 Ο(1)，在哈希表中添加，删除，查找等操作，性能非常高 。
哈希表在本质上也是一个数组，通过 哈希函数 将 Key 的哈希值转换为数组的索引，使key:hashcode -> index 建立映射关系。
例如一个长度为 8 的数组，key 为 001121，使用取模运算，转换为数组下标 index = hashcode("001121") % Array.length = 1420036703 / 8 = 7。
哈希冲突
通过哈希函数得出的元素在数组中的索引位已被占用， 就出现了哈希冲突。将哈希值转换为有限的数组索引，很大概率出现哈希冲突的问题。解决此问题通常有两种方式：一种是开放 寻址法，一种是 链表法（数组+链表）。
HashMap 用到了链表法，数组中的每一个元素不仅是一个 Entry 对象，还可能是一个链表的头节点。每一个 Entry 对象通过 next 指针指向它的下一个 Entry 节点。当新来的 Entry 映射到与之冲突的数组位置时，只需插入到对应的链表中即可。
链表法缺点：如果链表越来越长，则链表查找的性能就会越来越差，在 HashMap 中执行插入和查询操作的时间复杂度就提高到了 O(n)。（HashMap 是遍历到链表尾节插入）。
JDK 7 的 HashMap 的数据结构是基于 哈希表+链表。
JDK 8 对 HashMap 的数据结构进行了优化，引入了 红黑树，即采用了 哈希表+链表 / 红黑树 的数据结构，当链表长度超过 8 时，则将链表树化，这样就避免了超长链表的缺点，红黑树的查询插入的时间复杂度是 O(logn)，提高了性能。
HashMap
相关特性
Java 语言中，要了解某一功能特性，最好的方式是阅读源码上的注释，JDK 源码的注释是非常严谨和规范的。这一点值的学习。
HashMap 是基于 哈希表 的 Map 接口的实现，提供所有可选的 Map 操作。
- 允许 Key 为 null 值和 Value 为 null 值。
- 不同步，非线程安全。
- 不保证有序（如插入顺序），也不保证恒定时间顺序不变（若扩容的话则会重新分布）。
假设哈希函数将元素适当地分布在存储桶(Buckets)之间，为基本的 get/put 操作提供了稳定的性能。迭代 Collection 视图所需的时间与 HashMap 实例的容量(capacity：桶的数量)及其大小（键/值映射的元素数量）成比例。所以，如果迭代性能很重要，则不要将初始容量设置得太高（或将加载因子设置得太低）。
源码分析
类继承
public class HashMap<K,V> extends AbstractMap<K,V> implements Map<K,V>, Cloneable, Serializable {
private static final long serialVersionUID = 362498820763181265L;
//.......省略其它.......
}
HashMap 继承自父类（AbstractMap），实现了Map、Cloneable、Serializable 接口。
- Map 接口定义了一组通用的操作。
- Cloneable 接口表示可以进行拷贝，在HashMap中，实现的是浅层次拷贝，即拷贝的是对象的引用，而不是对象本身，被拷贝对象的改变会影响被拷贝的对象。
- Serializable 接口表示 HashMap 实现了序列化，设置了序列化版本号。即
HashMap对象会保存至本地，之后可以恢复。
构造方法
HashMap 实例有两个影响其性能的参数：初始容量和负载因子。容量是哈希表中存储桶的数量，初始容量只是创建哈希表时的容量。
size（个数）：Map 中 Key-Value 元素的个数。
Capacity（容量）：是哈希表中存储桶(Buckets)的数量，初始容量（initialCapacity）只是创建哈希表时的容量，默认是
16，最大容量是1073741824。loadFactor（负载因子）：是在哈希表的容量自动扩容之前，衡量哈希表满表的系数，默认是
0.75f。当哈希表中的元数个数超过了负载因子和当前容量的乘积时，则认为满表并对哈希表进行重置（即，内部数据结构被重建），使得新哈希表的存储桶数大约是之前桶数的两倍。
默认负载因子(0.75f)在时间和空间成本之间提供了一个较好的权衡。较高的值会减少空间开销，但会增加查找成本。
设置初始容量，应考虑 Map 中预期的元数个数及其负载因子，以最大程序地减少重新哈希操作的次数。
如果设置了初始容量且大于最大容量除以负载因子的值，则不会发生任何重新哈希操作。附加参考load factor in HashMap。
threshold（扩容前阀值）：
threshold = capacity * loadFactor，当size大于threshold时会执行resize扩容操作。
成员变量：
/**
* map 中包含 key/value 元素个数
*/
transient int size;
/**
* 默认的初始容量 - 必须是2的幂数
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大的容量, 如果构造方法传入的容量超过此值时，则使用此最大值
* 必须是2的幂数, MAXIMUM_CAPACITY = 1 << 30 = 1073741824
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认负载因子,如果没有显式指定负载因子时使用
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
HashMap 构造方法：
/**
* 传入初始容量和负载因子(0.75)构造一个空的实例
*/
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);
this.loadFactor = loadFactor;
//threshold=(capacity * loadFactor), 是决定是否扩容的阀值(注意,此代表容易误解)
this.threshold = tableSizeFor(initialCapacity);
}
/**
* 传入初始容量,使用默认的负载因子(0.75)构造一个空的实例
*/
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
/**
* 使用默认的初始容量(16) 和 默认的负载因子(0.75)构造一个空的实例
*/
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
/**
* 将其它 Map 的元素添加到此 HashMap
*/
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
/**
* 利用已存在的 map 创建 HashMap
* 被 Map 构造方法,Map.putAll 和 Map.clone 调用
*/
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//得到 m 中的元素总数
int s = m.size();
if (s > 0) {
//判断是否需要初始化 table
if (table == null) { // pre-size
//计算HashMap容量
float ft = ((float)s / loadFactor) + 1.0F;
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
if (t > threshold)
//重新计算阀值
threshold = tableSizeFor(t);
}
//判断是否进行扩容
else if (s > threshold)
resize();
//遍历原始的 Map,调用 putVal 方法添加元素
for (Map.Entry<? extends K, ? extends V> e : m.entrySet()) {
K key = e.getKey();
V value = e.getValue();
//插入元素
putVal(hash(key), key, value, false, evict);
}
}
}
public HashMap(int initialCapacity, float loadFactor)在此构造方法中设置了
threshold的值， 这个值是扩容前的阀值，当 HashMap 的size大于threshold时，就执行resize()，也就是扩容。扩容操作是在调用
putVal方法添加元素时触发的，源码如下：final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { //...........省略........ if (++size > threshold) //size 大于 threshold,执行扩容 resize(); //...........省略........ }构造方法中
this.threshold = tableSizeFor(initialCapacity)不易理解，若写成this.threshold = tableSizeFor(initialCapacity) * this.loadFactor，就更易理解threshold = capacity * loadFactor的定义。注意，此构造方法中并没有对
table这个成员变量初始化，而是被推迟到第一次执行put方法时赋值，初始化table会调用resize()方法，在resize方法中对threshold进行重新赋值。transient Node<K,V>[] table; 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; if ((tab = table) == null || (n = tab.length) == 0) //第一次执行 put 方法时进入,调用 resize 方法 n = (tab = resize()).length; //.......省略...... } final Node<K,V>[] resize() { //第一次执行put, table == null Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // oldCap=0 int oldThr = threshold;//实例传入的容量 int newCap, newThr = 0; if (oldCap > 0) { //.....省略..... } else if (oldThr > 0) // 初始化容量,threshold 初始值也是初始容量 newCap = oldThr; else { // 若没有赋值,则使用默认值 newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; //小于允许的最大容量,返回 ft = (float)newCap * loadFactor; newCap = oldThr = threshold; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } //重新给 threshold 赋值 threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) //创建容量为 newCap 的 newTab Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; //.......省略....... return newTab; }static final int tableSizeFor(int cap)该方法返回一个大于等于且最接近
cap的 2 的幂次方整数。如给定 9，返回 2 的 4 次方 16，以给threshold赋初始值。在构建 HashMap 实例时会给 threshold 赋初始值，调用
tableSizeFor方法得到的，此值实际也是 HashMap 的初始容量。/** * 返回一个大于等于且最接近 cap 的2的幂次方整数。如给定9，返回2的4次方16。 */ static 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; }从上代码可以看出，HashMap 的容量必定是
2的幂数(即Node<K,V>[] table和newTab的容量必定是 2 的幂数)，就是如果构建实例时传入了的容量值不是2的幂数，例如给定 9，则容量实际是 16，即在的创建实例传入的容量可能不是 HashMap 实际的容量，实际容量是调用tableSizeFor方法计算得出，是最接近 cap 的 2 的幂次方整数，等于或大于指定的的容量值。方法执行逻辑分析：
第一行代码
int n = cap - 1是为了防止cap已经是 2 的幂时，执行完后面逻辑后返回的值是cap的 2 倍，因为cap已经是 2 的幂，就已经满足条件了，2倍就存在浪费了。。将
n转为二进制执行>>>无符号右移，高位直接补 0，再执行或|运行，然后赋值。可将n |= n>>>1翻译为n = n | (n>>>1)。此算法的核心是让某些二进制位全部都变为 1。
Hash算法
HashMap 底层的数据结构是 数组+链表/红黑树，主干是数组。
get / put 方法通过对 key 进行 hash 运算，再通过算法将 hash 值转换为数组索引， 实际是建立一个 key -> index 的映射关系，这样在每次根据 Key 查找时，就可以计算出对应的数组索引，就可以直接找到对应的 key-value对象，时间复杂度是 O(1)。
HashMap 的 get/put 都是先对 Key 执行hash后再做业务操作，源码如下。
public V get(Object key) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
/** 要理解HashMap中的Hash算法的精秒之处,最好先看下方法的注释。
* Computes key.hashCode() and spreads (XORs) higher bits of hash
* to lower. Because the table uses power-of-two masking, sets of
* hashes that vary only in bits above the current mask will
* always collide. (Among known examples are sets of Float keys
* holding consecutive whole numbers in small tables.) So we
* apply a transform that spreads the impact of higher bits
* downward. There is a tradeoff between speed, utility, and
* quality of bit-spreading. Because many common sets of hashes
* are already reasonably distributed (so don't benefit from
* spreading), and because we use trees to handle large sets of
* collisions in bins, we just XOR some shifted bits in the
* cheapest possible way to reduce systematic lossage, as well as
* to incorporate impact of the highest bits that would otherwise
* never be used in index calculations because of table bounds.
*/
static final int hash(Object key) {
int h;
//当 key 为 null 时，存储的是索引为 0 的位置，即第一个位置
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
key.hashCode() 得到散列值为 32位有符号 int 整数，取值范围从 -2,147,483,648 到 2,147,483,647，前后加起来大概 40亿的映射空间，如果直接用来做为数组索引，不一定有这么大连续的内存，且太浪费没必要。HashMap 的初始容量才 16，Key 的 hash 值是不能直接拿来用的，需要通过一定算法映射成数组索引来找到在哈希表中的位置。
HashMap 中的 hash 方法是先调用 hashCode() 方法取得 hash 值，再将 hash 值无符号右移 16 位，正好是 32位的一半，高位全补 0，再与原 hash 值做异或^运算（高半区与低半区做异或运算），对低位进行了扰动，混合了原始哈希码的高位和低位，异或后的值的高区 16 位 与原始 hash 值相比没有变化，低区的 16 位发生了变化，增加了低位的随机性，使该 hashCode 映射成数组下标时可以更均匀。
哈希表数组索引计算：
从 HashMap 的
get / put源码中可以看到计算数组index方式是：index =(n - 1) & hashn是哈希表的容量，是 2 的 幂次方，是数组table的长度。hash是对 key 执行 hashCode 再将高16位 与 低16位做异或运算后的值。
写个测试例子，看看
(n - 1) & hash这个算法计算出来的索引。@Test public void arrayIndex() { int n = 16; //假如有20个元素,数组容量是16, key 分别是 0-19, 使用索引算法计算出结果 for (int i = 0; i < 20; i++) { int key = i; int keyHash = new Integer(key).hashCode(); int val = keyHash >>> 16; int hash = keyHash ^ val; int index = ((n - 1) & hash); //int index = hash % n; System.out.print(index + ", "); } System.out.println(); } //输出结果： // & 与运算 ：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3, // % 取余运算：0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 0, 1, 2, 3,从上输出结果可以看出，计算索引的
&与运算 与 求余运算 得出的结果一致的，超过数组容量计算出的索引位存在冲突。计算索引算法解析：
(n - 1) & hash：（数组长度-1）正好相当于一个 低位掩码，低位全是 1，&与操作时的结果是将散列值的高位全部归零，只保留低位值，这个值一定是小于n的，就满足数组索引取值范围，所以用来做数组下标。效果等同于hash % n，但计算机的位运算 比 算术运算 高效的多。10100101 11000100 00100101 & 00000000 00000000 00001111 ------------------------------------------------------- 00000000 00000000 00000101 // & 与运算,高位全归零,只保留低位值如果直接使用 key 的 hash 进行
&与运算，就算 hash 分布再松散，要是只取最后几位的话，冲突就会很严重。如果散列本身做得不好，分布上成等差数列的漏洞，恰好使最后几个低位呈现规律性重复，就极其糟糕。
这时扰动函数的价值就体现出来了，将高半区与低半区进行异或运算，使高半位充分参与 Hash 运算。看下面这个图。
为什么数组长度必须是2的幂：
从上面内容可知，数组长度
n是 2 的幂，n - 1转二进制后，低位全是 1，而扩容后的容量是原来的 2 倍，扩容后的容量二进制表示正好是在n -1的二进制全为1的前一位加1，即扩容后只有一位差，也就是多出了最左位的 1。这样在通过
(n - 1) & hash的时候，只要 hash 对应的最左边的那一个差异位为0，就能保证得到的新的数组索引和老数组索引一致。
put方法
HashMap 通过 put 方法插入元素，Key 和 Value 可以为 null。put 方法调用了 putVal 方法来插入元素。
HashMap 的主干是一个 Node<K,V> 类型的 Entry 数组，Entry 是 HashMap 的基本组成单元，每一个 Entry 包含一个key-value键值对（其实就是一个保存了两个对象之间映射关系的一种集合）。
HashMap 的插入操作分两步：先进行查找，如果 key 已经存在，则覆盖 Value；否则根据查找到的位置，新建节点完成插入。
成员变量
/** * 第一次使用时初始化, 必要会调用大小。分配时, 长度一定是 2 的幂次方 * 实际存储 key-value 数组, key和value被封装成了 Node * JDK 1.8 之前存放链表的表头,1.8中引入红黑树,链表树化后,就是树的根 */ transient Node<K,V>[] table; /** * map 中 key-value 元素个数 */ transient int size; /** * HashMap 结构被修改的次数 */ transient int modCount; /** * threshold = capacity * loadFactor * 扩容前的阀值 */ int threshold; /** * 扩容因子 */ final float loadFactor; /** * JDK 1.8 对Hash冲突可能导致超长链表做了优化,引入了红黑树。 * 当链表中节点个数大于 TREEIFY_THRESHOLD, 就会将链表树化,以提高查询效率。 * 链表转为树的阀值。此值必须大于2，且至少等于8, */ static final int TREEIFY_THRESHOLD = 8; /** * 非树化的阀值。对于已经是树形的桶，会做一个split操作 * 若剩下的元素个数小于 UNTREEIFY_THRESHOLD, 则将其非树化,重新转回链表结构 * 此值应小于 UNTREEIFY_THRESHOLD, 且最大值为 6 */ static final int UNTREEIFY_THRESHOLD = 6; /** * 树化的最小 table 容量,如果没达到容量但节点又太多,则使用扩容 * 当一个链表中的元素个数大于树化阀值并请求 treeifyBin 操作 * 值至少为 4 * TREEIFY_THRESHOLD 的值, 以避免 resize 和 树化阀值之间的冲突 */ static final int MIN_TREEIFY_CAPACITY = 64;Node
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; } public final K getKey() { return key; } public final V getValue() { return value; } public final V setValue(V newValue) { V oldValue = value; value = newValue; return oldValue; } public final String toString() { return key + "=" + value; } //重写了 hashCode() 方法 public final int hashCode() { return Objects.hashCode(key) ^ Objects.hashCode(value); } //判断两个node是否相等,若key和value都相等，返回true。可以与自身比较为true 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; } }put 方法源码
public V put(K key, V value) { //调用 putVal, 传入了 key 的 hash 值 return putVal(hash(key), key, value, false, true); } /** * Map.put 和相关方法的实现 */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; //如果是第一次执行, table 为 null, 调用 resize() 扩容初始化 table if ((tab = table) == null || (n = tab.length) == 0) n = (tab = resize()).length; //确定传入Key的hashd在数组中对应的下标 i, p 在这里被赋值 if ((p = tab[i = (n - 1) & hash]) == null) //槽位如果为 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)))) //若该位置上的第一个元素p与传入的元素信息匹配,则将使用 p 给 e 赋值 e = p; else if (p instanceof TreeNode) //如果 p 是树形节点, 一棵红黑树的根节点,调用 putTreeVal 执行操作 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); else { //走到这里,说明 p 是个链表头,则遍历链表, binCount 表示链表节点数 for (int binCount = 0; ; ++binCount) { // e 指向 p 的下一个节点 if ((e = p.next) == null) { //如果为 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)))) //如果在链表中匹配到 Key,跳出循环 break; //用于遍历桶中的链表, p = e; } } if (e != null) { // existing mapping for key //走到这里,说明找到了与 key 相匹配的节点 e //暂存有节点当前的值为 oldValue V oldValue = e.value; if (!onlyIfAbsent || oldValue == null) //如果 onlyIfAbsent=true,则已存在的值不被覆盖,随非旧值为 null //onlyIfAbsent=false, 则用新值覆盖旧值 e.value = value; //钩子方法,HashMap中是个空方法，但是在其子类LinkedHashMap中会被Override //通知子类:节点e被访问过了 afterNodeAccess(e); //返回已被覆盖的节点e的oldValue return oldValue; } } /*******执行到这里,说明没有匹配的 Key,是新节点插入******/ //结构修改计数 +1,创建迭代器后结构被并发修改,引发 fail-fast ++modCount; //插入元数后, size+1, 如果已大于扩容的阀值 if (++size > threshold) // 如果 size 大于扩容阀值,则调用 resize()执行扩容 resize(); //钩子方法,通知子类有新节点插入 afterNodeInsertion(evict); //新节点插入,无旧值可返回,返回null return null; }
插入操作的大致流程：
先通过 Key 的 hash 定位到 table 数组中的一个桶位。
如果桶位没有被占用，则新建节点插入，记录结构修改数，判断是否扩容，结束。
如果桶被占用，则与第一个元素(节点)进行匹配，若成功，则无需后续的树判断和链表遍历操作，直接覆盖；否则的话则判断节点类型。
如果桶的第一个节点 p 是 TreeNode 类型，则表示桶中存在的是一棵红黑树，则调用
putTreeVal方法来处理。否则，该桶中就是一个链表，则对有进行遍历。若遍历链表的某个节点匹配到了 e，就跳出循环执行覆盖；否则循环直到链表尾节点(必为 null)，新建节点，挂在链表尾节点上，自己成为新的链表尾。
在链表插入新节点时，还会判断链表的长度是否达到树化的阀值，如果大于阀值，则调用
treeifyBin方法来树化。每插入一个新元素，size 会加 1，最后根据 size 是否大于扩容阀值，如果大于阀值，则调用
resize执行扩容操作。
get方法
了解了 HashMap 的 Hash 算法和 put 方法的逻辑，get 方法就更容易理解了。
/**
* 返回 key 映射的值, 如果没有映射就返回 null
*/
public V get(Object key) {
Node<K,V> e;
//null 判断,返回值
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
/**
* Map.get 和相关方法的实现
*/
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) {
//进入这里,表示 table 有元素,并且索引位不为 null
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//如果第一个元素的 hash 相等, 且(key 相等 或 equals 为 true)
return first;
if ((e = first.next) != null) {
//进入这里,表示需要从链表或红黑树中查找
if (first instanceof TreeNode)
//如果槽位是 TreeNode 类型,表示是红黑树,调红黑树的 getTreeNode 查找
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);//do...while...循环
}
}
return null;
}
链表树化
如果数组桶位是个链表，在向链表插入元素后，会判断链表的长度是否大于树化阀值，如果大于，则调用 treeifyBin 方法将链表树化。树化过程是创建树和向树中插入节点。
TreeNode
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> { TreeNode<K,V> parent; // red-black tree links TreeNode<K,V> left; TreeNode<K,V> right; TreeNode<K,V> prev; // needed to unlink next upon deletion boolean red; TreeNode(int hash, K key, V val, Node<K,V> next) { super(hash, key, val, next); } //.....省略方法..... }treeifyBin 源码
如果 table 数组为 null 或长度小于树化要求的最小容量,则用扩容取代树化
/** * Replaces all linked nodes in bin at index for given hash unless * table is too small, in which case resizes instead. * 将链表转化为红黑树 */ final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,V> e; //判断, 给 n 赋值,tab 的容量 if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY) //如果 table 数组为 null 或长度小于树化要求的最小容量,则用扩容取代树化 resize(); else if ((e = tab[index = (n - 1) & hash]) != null) { //这里给数组索引index赋值 //走进来,定位到hash对应的桶位,赋值给 e //定义两个树形节点指针,分别指向链表头,尾节点 TreeNode<K,V> hd = null, tl = null; do { //将 Node 类型节点替换为 TreeNode 类型的 p TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) //若为 null,则将 p 赋值给 hd hd = p; else { //将tl赋值为p的前节点 p.prev = tl; //将p赋值为tl的下一节点 tl.next = p; } //尾指针后移 tl = p; //如果有子节点则继续循环 } while ((e = e.next) != null); //将链表头节点插入table的index位置 if ((tab[index] = hd) != null) //通过 treeify 方法将链表树化 hd.treeify(tab); } }treeify树化
/** * Forms tree of the nodes linked from this node. * @return root of tree * 将链表树化 */ final void treeify(Node<K,V>[] tab) { //声明根节点 root TreeNode<K,V> root = null; //声明变量 x,next,从调用节点 this 开始遍历 for (TreeNode<K,V> x = this, next; x != null; x = next) { //下一节点 next = (TreeNode<K,V>)x.next; //当前x节点的左右子树置为空 x.left = x.right = null; if (root == null) { x.parent = null; //根节点的父节点为 null x.red = false; //红黑树根结点为黑色 //若 root 为空,则将 x 赋值为根节点 root root = x; } //否则,将当前节点插入到已有的树中 else { K k = x.key; int h = x.hash; Class<?> kc = null; for (TreeNode<K,V> p = root;;) { //第二层循环执行对一个节点的插入操作 //从根结点开始循环寻找适合 x 的位置,并完成插入 int dir, ph; K pk = p.key; if ((ph = p.hash) > h) //若 x.hash 小于p的,则往p的左子树中继续寻找 dir = -1; else if (ph < h) //否则在右子树中寻找 dir = 1; else if ((kc == null && (kc = comparableClassFor(k)) == null) || (dir = compareComparables(kc, k, pk)) == 0) //若两节点hash值相等，且key不可比，则利用System.identityHashCode方法来决定一个方向 dir = tieBreakOrder(k, pk); //将当前节点p暂存为xp TreeNode<K,V> xp = p; //根据上面算出的 dir 值选择将 p 向下左子树或右子树移 //若为空,说明找到合适位置执行插入,否则继续循环 if ((p = (dir <= 0) ? p.left : p.right) == null) { //将 parent 指针指向 xp x.parent = xp; if (dir <= 0) //根据dir决定x是作为xp的左孩子还是右孩子 xp.left = x; else xp.right = x; //每次插入新节点后都需要做平衡操作(满足红黑树性质) root = balanceInsertion(root, x); break; //插入完成,跳出循环 } } } } //对红黑树的平衡调整可能会更换根节点， //通过moveRootToFront方法确保table[index]中的节点与插入前相同 moveRootToFront(tab, root); }
resize扩容
HashMap 在调用 put 方法添加元素后，发现元素总数（size）大于了阀值（threshold），就会执行扩容操作。
阀值(threshold) = 容量(capacity ) * 负载因子(loadFactor)，默认的负载因子是 0.75f，可理解为当一个 Map 填满了 75% 的 Bucket 时，就会调用 resize 方法进行扩容。
putVal()源码：
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)
//首次put table==null
n = (tab = resize()).length;
//......中间代码忽略......
// 结构被修改次数
++modCount;
//修改 size 的值, 本次 put 成功后 ++size
if (++size > threshold)
//size 大于 threshold,则调用 resize() 进行扩容
resize();
afterNodeInsertion(evict);
return null;
}
resize()源码：
/**
* 初始化或翻倍增加表大小。如果为空,则根据阀值(threshold)来分配置初始容量(capacity)
* 否则,因为使用的是 2 的幂,所以每个 Bucket 中的元素必须保持相同的索引,或者在新表中以 2 的幂偏移。
*/
final Node<K,V>[] resize() {
// 当前已存在的 table
Node<K,V>[] oldTab = table;
// oldTab 为 null 表示 table 还未初始化, oldCap=0
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 如果使用空参构造没有指定容量,就不会给阀值赋值,默认就为 0
// 如果指定了初始容量,threshold 就会在构造方法中被赋值为最接近初始容量值的2的幂方整数
int oldThr = threshold;
// 初始化新的 table 容量和阀值
int newCap, newThr = 0;
// 如果 oldCap > 0 表示 table 已初始化,HashMap有执行 put 添加元素
if (oldCap > 0) {
//如果旧容量大于允许的最大值 1<< 30
if (oldCap >= MAXIMUM_CAPACITY) {
//则将阀值赋值为int类型最大值,表示充分使用空间
threshold = Integer.MAX_VALUE;
//不能执行扩容,返回旧表
return oldTab;
}
//将旧容量向左移一位,即增加1倍,再赋值给新的容量,若小于允许的最大容量，且大于默认的初始容量
//注意:在这个if判断条件里设置了扩容的大小 newCap = oldCap << 1
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//阀值也进行扩容,即增加1倍
newThr = oldThr << 1;
}
//如果旧阀值大于 0,即调用 HashMap 构造方法显式传入了阀值
//如果创建 HashMap 实例指定了初始容量,初始化 table 走进这里
else if (oldThr > 0)
//初始化容量为阀值(注意,是在这里赋初始化容量)
newCap = oldThr;
else {
//否则就使用默认的大小,计算阀值
//使用 HashMap 空参构造,初始化 table 会直接走到这里赋初始值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果构造方法指定了容量,table初始化,此 newThr 初始值一直是 0
if (newThr == 0) {
//计算阀值
float ft = (float)newCap * loadFactor;
//给阀值赋值(新容量小于允许最大容量,且 ft 小于)
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//赋新的阀值
threshold = newThr;
/**
* 下面是重点了,构建新的 table
*/
@SuppressWarnings({"rawtypes","unchecked"})
//创建一个新容量大小数组 newTab
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//赋值
table = newTab;
if (oldTab != null) {
//老的桶不为 null, 就循环遍历转移元素
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//oldTab[j] 上存在元素就赋值给 e
if ((e = oldTab[j]) != null) {
//旧的置为 null
oldTab[j] = null;
//如果 e 没有后续节点
if (e.next == null)
//直接计算 e 在 newTab 上的位置并放入。
newTab[e.hash & (newCap - 1)] = e;
//如果 e 是 TreeNode 类型节点, 要进行 红黑树的 rehash 操作
else if (e instanceof TreeNode)
//将红黑树分隔成2次插入到新桶中
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
//走取这里,说明该节点是个链表
//将连表拆成2个链表,分别找到新桶中的位置后插入
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
//获得子节点
next = e.next;
//因容量是 2 的幂次方,二进制表示只有 1 位是 1,其它全是 0
//容量再与 hash 做与运算,则得到的只能是 1 或 0
if ((e.hash & oldCap) == 0) {
//索引不变的链表
if (loTail == null)
//头,形成链表
loHead = e;
else
//尾,存在(hash冲突)则插入到子节点
loTail.next = e;
loTail = e;
}
else {
//索引发生改变的链表
if (hiTail == null)
//形成连表
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
//do...while循环,至少会执行一次
} while ((e = next) != null);
//定位2个链表在新桶中的位置,然手插入
if (loTail != null) { // 原 bucket 位置的尾指针不为空(即还有子节点)
loTail.next = null; // 链表最后得有个 null
newTab[j] = loHead; // 链表头指针放在新桶的相同下标(j)处
}
if (hiTail != null) {
hiTail.next = null;
//扩容是原来的2倍,原与旧容量与操作不为 0 的元素要迁移
//而这个新的位置正好是当前位置+旧容量
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
非线程安全
HashMap 使用同步，是非线程安全的。如果多个线程同时访问，且至少有一个线程修改了其结构，则必须在外部进行同步。（结构修改：指添加或删除一个或多个元素的任何操作；仅更改键的值不是结构修改）。
如果无法在外部进行同步，则应使用如下方式来包装 Map，最好是在创建实例时完成此操作。
Map m = Collections.synchronizedMap(new HashMap(...))
HashMap 的所有 集合视图 方法返回的迭代器都是快速失败（fail-fast）的，如果在创建迭代器后的任何时间结构被修改，除了迭代器自己的 remove 方法外，该迭代器都将抛出 ConcurrentModificationException 异常。因此，面对并发修改，迭代器会快速干净地失败，防止任何风险，迭代器的快速失败行为仅应用于检测错误。
HashMap是非线程安全的，其主要体现：
- 在 JDK 1.7 中，在多线程环境下，扩容时会造成环形链或数据丢失。
- 在 JDK 1.8 中，在多线程环境下，会发生数据覆盖的情况。
具体分析可参考 HashMap 为什么线程不安全？。
与HashTable区别
| HashMap | HashTable | |
|---|---|---|
| 线程安全 | 非线程案全， 性能相对高些。 |
线程安全，方法上使用synchronized ，比较粗暴 |
| NULL值 | 允许 Key / Value 为 Null， Key 为 Null 时存在 table 数组第一个节点上。 判断键是否存在使用 containsKey() 方法 |
不允许 Key 为Null |
| 继承关系 | 继承自 AbstractMap | 继承自 Dictionary |
| 初始容量与负载因子 | 初始容量：16 负载因子：0.75f |
初始容量：11 负载因子：0.75f |
| 扩容方式 | 原容量的2倍：newCap = oldCap << 1 | 原容量的2倍+1： newCapacity = (oldCapacity << 1) + 1 |
| 底层结构 | JDK 7 ：数组 + 链表 JDK 8 ：数组 + 链表 / 红黑树 |
数组 + 链表 |
| 哈希算法 | hash = (h = key.hashCode()) ^ (h >>> 16) index = (n - 1) & hash |
hash = key.hashCode(); index = (hash & 0x7FFFFFFF) % tab.length; |
与HashSet区别
HashSet 不是 Key / Value 结构，仅仅是存储不重复的元素。
HashSet 的内部实现是 HashMap，HashSet 里面的元素填充到 HashMap 的 Key，HashMap 的 Vaule 使用同一个 Object 对象填充。
因此 HashSet 也是非线程安全的，HashSet 可以理解为 HashMap 的简化版。
HashSet 构造方法
public HashSet() {
map = new HashMap<>();
}
HashSet add方法
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
数据结构图
JDK 1.7
HashMap 数据结构图
JDK 1.8
HashMap 数据结构图
put 方法逻辑图
相关参考
- 解析HashMap的tableSizeFor方法。
- 源码分析系列文章-HashMap
- 深入理解HashMap系列
- 美团：Java 8系列之重新认识HashMap
- 一文读懂 JDK8 HashMap
- HashMap中的hash算法总结
- HashMap中的hash算法中的几个疑问
- JDK 源码中 HashMap 的 Hash 方法原理
- HashMap死循环分析的修正版
- 重新认识JDK1.8 中不一样的HashMap：提供了 JDK1.7 VS JDK1.8 性能比较。
- 红黑树在HashMap中的应用：说明了红黑树的操作
- Java集合之 JDK7 HashMap：演示了容量为何为2的幂，重写 equals和 hashCode 方法
- HashMap分析之红黑树树化过程：描述了红黑树及树操作
- 关于 HashMap 1.8 的重大更新：对比了Jdk1.7与Jdk1.8的区别，脑图，流程图。
- HashMap 数组+链表+红黑树：比较多，但也比较杂，排版不好
- Jdk1.7 HashMap底层实现和原理：描述了链表的几种形式，补充了 1.8 的区别
- Jdk 1.8 扩容后的元素新位置为原位置+原数组长度：解释了
newTab[j + oldCap] = hiHead - HashMap之put方法流程解读：详细描述 put 方法。
- 了解数据结构：Array、HashMap、List：描述了多数据结构的插入、查找、删除的时间复杂度比较
- 掌握 HashMap 看这一篇文章就够了：Jdk 1.7 和 1.8 较全面的比较分析
- 彻底理解HashMap的元素插入原理：图较多，比较清晰
- HashMap是如何工作的？：哈希冲突的解决方法，在维基百科中，总结出了四大类
- What is the significance of load factor in HashMap?
注意：本文归作者所有，未经作者允许，不得转载
