HashMap
- HashMap 与 HashSet 一样，不保证存储的顺序，因为底层是以 hash 表的方式存储的；
- HashMap 底层存储结构为 数组 + 链表+红黑树 （Java 8）；
- HashMap 存储的 key-value 数据类型为 HashMap$Node 类型，该类型实现了 Map$Entry 接口；
- HashMap 没有实现同步，因此是线程不安全的；
HashMap 中的几个常量/变量
```java static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // 默认的 table 数组容量 aka 16 static final float DEFAULT_LOAD_FACTOR = 0.75f; // 默认加载因子为 0.75 static final int MAXIMUM_CAPACITY = 1 << 30; // 集合最大容量的上限是：2的30次幂 static final int TREEIFY_THRESHOLD = 8; // 链表树化临界值 static final int UNTREEIFY_THRESHOLD = 6; // 树转成链表的临界值 static final int MIN_TREEIFY_CAPACITY = 64; // 树化时数组的最小长度
transient Node
<a name="w5kpj"></a># 初始化及扩容机制参考 [HashSet 分析](https://www.yuque.com/zhangshuaiyin/java/wqwnyd#nscaz)- HashMap 是用一个 Node 类型的数组 table 来存储元素的，每一个元素的类型为 Node；```javatransient Node<K,V>[] table;
创建 HashMap 对象时，数组 table 默认为 null，加载因子 loadfactor 默认为 0.75；
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }第一次添加元素时，判断 table 为空数组，默认将 table 扩容到 16，阈值 threshold 为数组长度与加载因子的积 12（resize() 方法）；
- 当添加元素 key-value 时，通过 key 的 hash 值计算该元素在 table 中的索引位置，判断该索引位置是否存在 Node 结点，没有则直接添加；
- 如果索引位置有结点，则判断要添加的元素的 key 与该节点的 key 是否相同，如果相同，则将 value 替换到当前结点，如果不相同，则判断当前结点是否是树结构，是树结构则执行添加树结点操作；
- 如果不是，判断为链表结构，且要添加的元素和链表第一个结点不同，遍历链表判断 key 是否存在，不存在则向链表插入元素，并判断当前链表是否满足树化条件（链表长度大于
等于8），如果存在执行替换操作； 当 table 长度大于阈值 threshold 时，则执行 resize() 方法给 table 进行扩容，扩容大小为原来的 2 倍，同时阈值更新为当前数组长度乘以加载因子；
// putVal() 添加元素成功,table长度加1, 判断是否扩容 if (++size > threshold) resize();当 table 某个节点的链表长度超过 TREEIFY_THRESHOLD（默认 8）后，判断 table 的容量是否达到 MIN_TREEIFY_CAPACITY（默认 64），达到则对当前结点的链表进行树化；否则对 table 扩容；
- 当树的元素减少到 UNTREEIFY_THRESHOLD = 6 时，会进行剪枝操作（转回链表）
阿里巴巴编码规约-初始化指定容量
【推荐】集合初始化时，指定集合初始值大小。
说明：HashMap 使用 HashMap(int initialCapacity) 初始化。
正例：initialCapacity = (需要存储的元素个数 / 负载因子) + 1。
注意负载因子（即 loader factor）默认为 0.75，如果暂时无法确定初始值大小，请设置为 16（即默认值）。
反例：HashMap 需要放置 1024 个元素，由于没有设置容量初始大小，随着元素不断增加，容量 7 次被迫扩大，resize 需要重建 hash 表，严重影响性能。主要方法源码分析
HashMap() - 构造器
无参构造
public HashMap() { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }指定初始容量的构造器
public HashMap(int initialCapacity) { this(initialCapacity, DEFAULT_LOAD_FACTOR); }指定初始容量和加载因子的构造器
public HashMap(int initialCapacity, float loadFactor) { if (initialCapacity < 0) // 异常:初始容量小于0 throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity); // 指定容量大于数组最大容量,初始化为最大容量 if (initialCapacity > MAXIMUM_CAPACITY) initialCapacity = MAXIMUM_CAPACITY; if (loadFactor <= 0 || Float.isNaN(loadFactor)) // 异常:加载因子小于0 or NaN Not a Number throw new IllegalArgumentException("Illegal load factor: " + loadFactor); this.loadFactor = loadFactor; // 指定加载因子大小 // 计算 table 的大小,确保为2的n次幂, // 这里赋值给临界值,在第一次添加元素的时候会初始化为table大小 this.threshold = tableSizeFor(initialCapacity); }putVal() - 添加元素
/** * Implements Map.put and related methods. * * @param onlyIfAbsent if true, don't change existing value * @param evict if false, the table is in creation mode. * @return previous value, or null if none */ final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { Node<K,V>[] tab; Node<K,V> p; int n, i; // 定义辅助变量 // 0. 这里是判断table是否初始化，table = null or table.length = 0 初始化table if ((tab = table) == null || (n = tab.length) == 0) // table:存放元素的Node[]数组 n = (tab = resize()).length; // resize():扩容-数组为空给table初始化16个空间 // 根据key的hash值计算索引值,将table中该索引位置的结点赋值给p,并判断p是否为空 if ((p = tab[i = (n - 1) & hash]) == null) //若p为null(当前位置没有元素)则创建新的结点Node保存当前要添加的数据,存储到当前索引位置 tab[i] = newNode(hash, key, value, null); else { // 这里说明table当前索引位置的结点已经存在数据，下面分情况判断添加元素 Node<K,V> e; K k; // 1. 判断要添加的元素(key)与table中当前索引位置的Node结点是否相同 // condition: ① hash 值相等 && (② 引用相同 || ③ equals判断相等) if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k)))) e = p; // 元素重复 // 2. 判断当前索引位置元素结点是否是红黑树类型 else if (p instanceof TreeNode) e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value); // 3. 说明当前索引位置结点为链表,且第一个结点与要添加的元素key不同,就遍历链表判断key是否存在 else { for (int binCount = 0; ; ++binCount) { if ((e = p.next) == null) { // 如果key和链表中所有节点元素都不相同，则添加到链表最后 p.next = newNode(hash, key, value, null); // 添加元素后判断当前链表是否已经有了8个节点，够8个则将当前链表转成红黑树 // 这里调用treeifyBin()方法会判断table大小是否足够64个，到达64个才会树化 // 不满 64 个空间，会先给 table 扩容 if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st treeifyBin(tab, hash); break; // 退出 for 循环 } // 如果要添加的元素key在链表中已经存在，则直接退出循环 // condition: ① hash 值相等 && (② 引用相同 || ③ equals判断相等) if (e.hash == hash && ((k = e.key) == key || (key != null && key.equals(k)))) break; p = e; // 当前节点后移 } } // 要添加的元素 key 已存在，则将重复的元素返回 if (e != null) { // existing mapping for key V oldValue = e.value; // 将要添加的 value 替换掉旧值 if (!onlyIfAbsent || oldValue == null) e.value = value; afterNodeAccess(e); return oldValue; } } ++modCount; // 修改次数 // 添加元素成功,table长度加1, 判断是否扩容 数组长度是否大于阈值 if (++size > threshold) resize(); afterNodeInsertion(evict); // HashMap 没有实现该方法, 供子类实现扩充功能 // return null 表示要添加的元素在table中不存在, 添加成功 return null; }resize() - table 扩容
给 table 初始化或者将数组大小翻倍，如果 table 为null，则根据默认值指定初始容量和边界值；否则，因为我们的 table 数组容量是 2 的 n 次幂，所以每个 bin 中的元素一定保持相同的索引，或者在新 table 中移动 2 的 n 次幂的偏移量（元素在新数组中的索引位置为 原来的索引 或者是 原来的索引 + 原容量大小）
/** * Initializes or doubles table size. If null, allocates in * accord with initial capacity target held in field threshold. * Otherwise, because we are using power-of-two expansion, the * elements from each bin must either stay at same index, or move * with a power of two offset in the new table. * * @return the table */ 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倍(<<1 == *2) // 旧容量已经到达最大容量就扩大临界值 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 } // 将旧临界值赋值给新容量，这里的场景为初始化时使用了带参数的构造器-tableSizeFor() else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; // 数组初始化 else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } // 这里也是初始化指定容量大小的场景，临界值赋值给容量，这里给临界值重新计算值 if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; // table 边界值更新为新的边界值 @SuppressWarnings({"rawtypes","unchecked"}) // 创建新 table 容量为默认初始容量或之前容量的2倍 Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; // 原数组不为null，说明是扩容-遍历之前的table 赋值给新数组 if (oldTab != null) { for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { // 当前索引存在元素 e oldTab[j] = null; // 方便回收空间 // 1. 当前索引位置只有一个元素，没有下一个结点 if (e.next == null) // 重新计算当前元素在新table中的索引，将当前索引结点放到新table newTab[e.hash & (newCap - 1)] = e; // 2. 当前索引位置有下一个结点，且是红黑树,指定树的操作 else if (e instanceof TreeNode) ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 3. 当前索引位置有下一个结点，这里是链表类型 else { // preserve order Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; // 依次遍历链表结点，确定新数组索引位置 do { next = e.next; // 取出下一个结点 // 扩容核心操作查看：https://www.yuque.com/zhangshuaiyin/java/sv07ip#DYnvE // 判断当前元素在新数组的索引是否改变 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; } } } } } return newTab; }treeifyBin() - 树化
树化-将数组中的链表转成红黑树 ```java /**
- 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
} while ((e = e.next) != null); // 链表结点后移 // 将树的头节点放在数组的当前索引位置，然后转换成红黑树 if ((tab[index] = hd) != null)// 将链表结点转换为树结点类型 TreeNode TreeNode<K,V> p = replacementTreeNode(e, null); if (tl == null) hd = p; // 给头节点赋值为当前索引结点 else { // 将树结点连接起来 p.prev = tl; tl.next = p; } tl = p; // 给尾结点赋值
} }hd.treeify(tab);
// For treeifyBin
TreeNode
<a name="xs1Sy"></a>
## remove() - 根据key删除
```java
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
Node<K,V>[] tab; Node<K,V> p; int n, index; // 辅助变量
// table 不为空，且指定key的hash计算的索引位置有元素
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
Node<K,V> node = null, e; K k; V v; // 辅助变量
// 1 判断要删除的元素是否是指定索引链表的第一个元素
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
// 2 不是第一个元素，判断链表是否还有其他元素
else if ((e = p.next) != null) {
// 2.1 有其他元素且为树结点
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else { // 2.2 有其他元素，为链表结构
do { // 遍历链表，依次判断要删除的元素的位置
// 根据hash、key的值找到要删除的元素
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break; // 找到，退出
}
p = e; // p 是要删除节点的上一个节点
} while ((e = e.next) != null);
}
}
// 找到元素，执行删除操作
if (node != null && (!matchValue || (v = node.value) == value ||
(value != null && value.equals(v)))) {
if (node instanceof TreeNode) // 树结点删除
((TreeNode<K,V>)node).removeTreeNode(this, tab, movable);
else if (node == p) // 链表只有一个元素删除
tab[index] = node.next;
else // 链表中有多个元素删除
p.next = node.next;
++modCount; // 计数器+1
--size; // 长度 -1
afterNodeRemoval(node);
return node;
}
}
return null;
}
get() - 根据key获取
public V get(Object key) {
Node<K,V> e;
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;
// 数组不为空，且根据hash计算的索引位置有结点
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
// 查询的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) {
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);
}
}
return null;
}
HashMap集合(高级)
参考：https://www.bilibili.com/video/BV1nJ411J7AA 链接：https://pan.baidu.com/s/1GTNPKHKqgCYDiuXqUqUxZA 提取码：90et
HashMap继承关系
HashMap继承关系如下图所示：
说明：
- Cloneable 空接口，表示可以克隆。 创建并返回 HashMap 对象的一个副本。
- Serializable 序列化接口。属于标记性接口。HashMap 对象可以被序列化和反序列化。
- AbstractMap 父类提供了 Map 实现接口。以最大限度地减少实现此接口所需的工作。
table 数组容量必须是 2 的 n 次幂
HashMap 在添加元素的时候，添加到数组的索引位置是根据 key 的 hash 值与数组长度减一 做按位与操作计算得来的（hash & (length - 1)）。为了使元素更加分散的添加到数组中，当数组长度为 2 的 n 次幂时，计算索引的结果和 hash % length 相等(取余效率低)，这样能够减少哈希碰撞。
也就是说，当 length 为 2 的 n 次幂时 hash & (length - 1) = hash % length；
而当我们手动传入数组长度不是 2 的 n 次幂时，HashMap 底层会执行什么样的操作呢？
由于 HashMap 提供了传递数组长度的构造器，所以我们可以手动给 HashMap 传递 table 长度，而数组长度必须是 2 的 n 次幂，当我们传入其他值时，HashMap 会通过一系列的 位移运算 和 或运算 得到比传递值大且最接近指定大小的 2 的 n 次幂的数值；
// 创建HashMap集合的对象，指定数组长度是10，不是2的幂
HashMap hashMap = new HashMap(10);
public HashMap(int initialCapacity) { // initialCapacity=10
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}
public HashMap(int initialCapacity, float loadFactor) { // 10, 0.75
if (initialCapacity < 0) // false
throw new IllegalArgumentException("Illegal initial capacity: " + initialCapacity);
if (initialCapacity > MAXIMUM_CAPACITY) // false
initialCapacity = MAXIMUM_CAPACITY;
if (loadFactor <= 0 || Float.isNaN(loadFactor)) // false
throw new IllegalArgumentException("Illegal load factor: " + loadFactor);
this.loadFactor = loadFactor;
this.threshold = tableSizeFor(initialCapacity); // initialCapacity=10
}
/**
* Returns a power of two size for the given target capacity.
*/
static final int tableSizeFor(int cap) { // int cap = 10
// 这里防止cap已经是2的n次幂, 2的n次幂执行下面操作会扩大2倍
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;
}
通过 位移运算 和 或运算 最终得到的结果为从二进制最左侧的1开始，右边全部为1；
00000000 00000000 00000000 00001001 // 9
00000000 00000000 00000000 00001101 // 9 | 9 >>> 1 = 13
00000000 00000000 00000000 00001111 // 13 | 13 >>> 2 = 15
由于整数最大位数为 32,因此最大值为 32 个 1,这时已经变成负数了,返回之前会判断。如果为负数，返回1；如果大于等于 MAXIMUM_CAPACITY 2^30 ，返回 MAXIMUM_CAPACITY ，否则返回 n + 1；最终赋值给 threshold 临界值，在第一次添加元素给数组 table 扩容的时候，赋值给 table 的长度值，并计算新的临界值 threshold 为 数组长度乘以加载因子。
为什么链表长度为 8 时进行树化？
在 HashMap 源码中有这样一段描述：
/** Because TreeNodes are about twice the size of regular nodes, we
* use them only when bins contain enough nodes to warrant use
* (see TREEIFY_THRESHOLD). And when they become too small (due to
* removal or resizing) they are converted back to plain bins. In
* usages with well-distributed user hashCodes, tree bins are
* rarely used. Ideally, under random hashCodes, the frequency of
* nodes in bins follows a Poisson distribution
* (http://en.wikipedia.org/wiki/Poisson_distribution) with a
* parameter of about 0.5 on average for the default resizing
* threshold of 0.75, although with a large variance because of
* resizing granularity. Ignoring variance, the expected
* occurrences of list size k are (exp(-0.5) * pow(0.5, k) /
* factorial(k)). The first values are:
*
* 0: 0.60653066
* 1: 0.30326533
* 2: 0.07581633
* 3: 0.01263606
* 4: 0.00157952
* 5: 0.00015795
* 6: 0.00001316
* 7: 0.00000094
* 8: 0.00000006
* more: less than 1 in ten million
*
* The root of a tree bin is normally its first node. However,
* sometimes (currently only upon Iterator.remove), the root might
* be elsewhere, but can be recovered following parent links
* (method TreeNode.root()).
*/
因为树结点 TreeNode 占用空间大小比链表结点 Node 大两倍，所以在结点够多时才使用树结点。并且当树结点太少（由于删除或者调整大小）也会被转换为普通的 bins。在hashCode 分布均匀时，树 bins 很少使用。理想情况下，在随机的 hashCode 中，bins 中结点存放的概率服从 泊松分布(http://en.wikipedia.org/wiki/Poisson_distribution))，默认调整阈值为0.75，平均参数约为0.5，尽管由于调整粒度的差异很大。忽略方差，列表大小k的预期出现次数是(exp(-0.5)*pow(0.5, k)/factorial(k))。
根据注释中的说明，在 hashCode 离散型很好的时候，链表中存储到第八个索引的概率极小，树化的概率非常小。选择大小 8 是从概率学的角度出发，进行的空间与时间的权衡。
数组扩容后如何计算元素的新索引
在 JDK 1.7 是采用重新计算 hash 的方式，这样要对数组中所有的元素重新计算 hash 值，影响效率，Java 8 对计算索引做了优化。
HashMap 在进行扩容时，使用的 rehash 方式非常巧妙，因为每次扩容都是翻倍，与原来计算的 (n-1) & hash 的结果相比，只是多了一个 bit 位，所以节点要么就在原来的位置，要么就被分配到”原位置+旧容量“这个位置。
举例：
正是因为这样巧妙的 rehash 方式，既省去了重新计算 hash 值的时间，而且同时，由于新增的 1 bit 是 0还是 1 可以认为是随机的，在 resize 的过程中保证了 rehash 之后每个桶上的节点数一定小于等于原来桶上的节点数，保证了 rehash 之后不会出现更严重的 hash 冲突，均匀的把之前的冲突的节点分散到新的桶中了。
讲义
若有收获，就点个赞吧
0 人点赞
