HashMap大家平时工作中出现的频率应该是非常高的，它是一个散列表，它存储的内容是键值对(key-value)映射。
HashMap 继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
其底层数据结构是数组称之为哈希桶，每个桶里面放的是链表，链表中的每个节点，就是哈希表(指代HashMap)中的每个元素。JDK 1.8 之后，当链表大于 8 并且哈希表长度大于 64 时，链表结构会转换成红黑树结构。
注意哈希桶的容量与哈希表的容量的差别，一个指数组容量一个指hashMap容量
【注意：本文基于JDK 1.8】
特点：
- 线程不安全
- 允许key与value为null
- 遍历无序
- 链表大于 8 并且哈希表长度大于 64，转成红黑树
- 达到threshold=(capacity * load factor)会进行扩容，默认扩容因子0.75
链表节点（哈希表元素）
先了解存储在哈希表上的元素，链表的结构：
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 String toString() { return key + "=" + value; }
//节点哈希值，将key的hashCode 和 value的hashCode 异或
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}
//设置新的value 同时返回旧value
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}
//重写equals方法key和value都相等元素才相等
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;
}
}成员属性
常量
/**
* HashMap默认容量为16，必须是2的次方
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
/**
* 最大容量 2的30次方
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认加载因子(扩容因子) 0.75
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* 转化成红黑树的阈值，当哈希桶的链表结点数量大于等于8时，转化成红黑树
*/
static final int TREEIFY_THRESHOLD = 8;
/**
* 如果当前是红黑树结构，当桶的链表结点数量小于6时，会转换成链表
*/
static final int UNTREEIFY_THRESHOLD = 6;
/**
* 最小树容量
* 当哈希表的容量达到64时，也会转换为红黑树结构
*/
static final int MIN_TREEIFY_CAPACITY = 64;变量
/**
* 哈希桶，存放链表，长度是2的N次方，或者初始化时为0.
*/
transient Node<K,V>[] table;
/**
* 迭代功能
*/
transient Set<Map.Entry<K,V>> entrySet;
/**
* 哈希表元素数量
*/
transient int size;
/**
* 统计该map修改的次数
*/
transient int modCount;
/**
* 阈值，当元素数量，即哈希表的容量达到阈值时，会进行扩容（数组扩容）
*
* @serial
*/
int threshold;
/**
* 加载因子，用于计算哈希表元素数量的阈值。 threshold = 哈希桶.length * loadFactor;
*
* @serial
*/
final float loadFactor;构造器
无参构造
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}指定初始化容量的构造函数
public HashMap(int initialCapacity) {
this(initialCapacity, DEFAULT_LOAD_FACTOR);
}指定初始化容量和加载因子的构造函数
// 同时指定初始化容量 以及 加载因子， 用的很少，一般不会修改loadFactor
public HashMap(int initialCapacity, float loadFactor) {
// 初始化容量不能为负数
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal initial capacity: " +
initialCapacity);
// 初始化容量不能超过2的30次方
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
// 加载因子不能为负数
if (loadFactor <= 0 || Float.isNaN(loadFactor))
throw new IllegalArgumentException("Illegal load factor: " +
loadFactor);
this.loadFactor = loadFactor;
// 规整阈值大小，保证阈值为 >=初始化容量的2的n次方的值
this.threshold = tableSizeFor(initialCapacity);
}
//根据期望容量cap，返回2的n次方形式的 哈希桶的实际容量 length。 返回值一般会>=cap
static final int tableSizeFor(int cap) {
int n = cap - 1;
//经过下面的 或 和位移 运算， n最终各位都是1。
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
//判断n是否越界，返回 2的n次方作为 table（哈希桶）的阈值
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}合并其他Map元素的构造函数
//新建一个哈希表，同时将另一个map m 里的所有元素加入表中
public HashMap(Map<? extends K, ? extends V> m) {
this.loadFactor = DEFAULT_LOAD_FACTOR;
putMapEntries(m, false);
}
//将另一个Map的所有元素加入表中，参数evict初始化时为false，其他情况为true
final void putMapEntries(Map<? extends K, ? extends V> m, boolean evict) {
//获取m的元素数量
int s = m.size();
if (s > 0) {
//如果当前表是空的
if (table == null) { // pre-size
//根据m的元素数量和当前表的加载因子，计算出阈值
float ft = ((float)s / loadFactor) + 1.0F;
//修正阈值的边界，不能超过MAXIMUM_CAPACITY
int t = ((ft < (float)MAXIMUM_CAPACITY) ?
(int)ft : MAXIMUM_CAPACITY);
//如果新的阈值大于当前阈值
if (t > threshold)
//返回一个 >=新的阈值的 满足2的n次方的阈值
threshold = tableSizeFor(t);
}
//如果当前元素表不是空的，但是m的元素数量大于阈值，说明一定要扩容。
else if (s > threshold)
resize();
//遍历 m 依次将元素加入当前表中。
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);
}
}
}注意区别阈值与容量：在这里哈希桶即table还没被初始化，所以阈值就是哈希桶table初始化容量的大小，在扩容函数中初始化之后，阈值会被重新设置！
扩容
目的：初始化或加倍哈希桶大小
触发条件：
- 首次初始化，有可能是第一个put操作或者第一个putAll操作，也有可能是使用批量添加元素的构造函数
- 已经初始化，putAll批量添加元素，增加元素的总个数大于阈值
- 已经初始化，putVal添加一个节点后，节点个数大于阈值
final Node<K,V>[] resize() {
//oldTab 为当前表的哈希桶
Node<K,V>[] oldTab = table;
//当前哈希桶的容量
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//当前的阈值
int oldThr = threshold;
//初始化新的容量和阈值为0
int newCap, newThr = 0;
//如果当前容量大于0
if (oldCap > 0) {
//如果当前容量已经到达上限
if (oldCap >= MAXIMUM_CAPACITY) {
//则设置阈值是2的31次方-1
threshold = Integer.MAX_VALUE;
//同时返回当前的哈希桶，不再扩容
return oldTab;
}
//否则新的容量为旧的容量的两倍。
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//如果当前的容量达到16的话，新的阈值也等于旧的阈值的2倍
newThr = oldThr << 1; // double threshold
}
//如果当前表是空的，但是有阈值。代表是初始化时指定了容量、阈值的场景
else if (oldThr > 0) // initial capacity was placed in threshold
//那么新表的容量就等于旧的阈值
newCap = oldThr;
//如果当前表是空的，且没有阈值。代表是初始化时没有指定任何容量/阈值参数
else { // zero initial threshold signifies using defaults
//此时新表的容量为默认的容量 16
newCap = DEFAULT_INITIAL_CAPACITY;
//新的阈值为默认容量16 * 默认加载因子0.75f = 12
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//如果新的阈值是0，对应的是 当前表是空的，但是有阈值的情况
if (newThr == 0) {
//根据新表容量 和 加载因子 求出新的阈值
float ft = (float)newCap * loadFactor;
//进行越界修复
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//更新阈值
threshold = newThr;
//根据新的容量 构建新的哈希桶
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
//更新哈希桶引用
table = newTab;
//如果以前的哈希桶中有元素
//下面开始将当前哈希桶中的所有节点转移到新的哈希桶中
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
//遍历
if ((e = oldTab[j]) != null) {
//置空原哈希桶以便GC
oldTab[j] = null;
//如果当前链表中就一个元素，（没有发生哈希碰撞）
if (e.next == null)
//直接将这个元素放置在新的哈希桶里。
//注意这里取下标 是用 哈希值 与 桶的长度-1 。
//由于桶的长度是2的n次方，这么做其实是等于 一个模运算。但是效率更高
newTab[e.hash & (newCap - 1)] = e;
//如果发生过哈希碰撞 ,而且是节点数超过8个，转化成了红黑树
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
//如果发生过哈希碰撞，节点数小于8个。则要根据链表上每个节点的哈希值，依次放入新哈希桶对应下标位置。
else { // JDK 8优化部分
//因为扩容是容量翻倍，所以原链表上的每个节点，现在可能存放在原来的下标，即low位， 或者扩容后的下标，即high位。 high位= low位+原哈希桶容量
//低位链表的头结点、尾节点
Node<K,V> loHead = null, loTail = null;
//高位链表的头节点、尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 原索引
//利用哈希值 与 旧的容量，可以得到哈希值取模后，判断hash的高位是否为0决定新哈希桶的位置
//关于高低位原理见下面的链接
if ((e.hash & oldCap) == 0) {
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
}
// 原索引+oldCap
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;
}
//将高位链表存放在新index处
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}关于(e.hash & oldCap) == 0 高低位的原理引用了一篇博文介绍如下：
首先我们要明确三点:
- oldCap一定是2的整数次幂, 这里假设是2^m
- newCap是oldCap的两倍, 则会是2^(m+1)
- hash对数组大小取模(n - 1) & hash 其实就是取hash的低m位
例如:
我们假设 oldCap = 16, 即 2^4,
16 - 1 = 15, 二进制表示为 0000 0000 0000 0000 0000 0000 0000 1111
可见除了低4位, 其他位置都是0（简洁起见，高位的0后面就不写了）, 则 (16-1) & hash 自然就是取hash值的低4位,我们假设它为 abcd.以此类推, 当我们将oldCap扩大两倍后, 新的index的位置【小陈注：指从map中get值的index，(length - 1) & hash】就变成了 (32-1) & hash, 其实就是取 hash值的低5位. 那么对于同一个Node, 低5位的值无外乎下面两种情况:
0abcd
1abcd
其中, 0abcd与原来的index值一致, 而1abcd = 0abcd + 10000 = 0abcd + oldCap故虽然数组大小扩大了一倍，但是同一个key在新旧table中对应的index却存在一定联系： 要么一致，要么相差一个 oldCap。
而新旧index是否一致就体现在hash值的第4位(我们把最低为称作第0位), 怎么拿到这一位的值呢, 只要:
hash & 0000 0000 0000 0000 0000 0000 0001 0000
上式就等效于hash & oldCap
故得出结论:如果 (e.hash & oldCap) == 0 则该节点在新表的下标位置与旧表一致都为 j
如果 (e.hash & oldCap) == 1 则该节点在新表的下标位置 j + oldCap
根据这个条件, 我们将原位置的链表拆分成两个链表, 然后一次性将整个链表放到新的Table对应的位置上.
原博文：
https://segmentfault.com/a/1190000015812438
另外美团的技术团队文章也有具体的解释，也可以看看
https://tech.meituan.com/2016/06/24/java-hashmap.html
这里加一点自己的理解：
1.为什么区分高低位？即为啥有的链表的值要挪？
因为get()与put()方法，数据存储在数组里，数组的位置是通过(length - 1) & hash计算出来的，所以扩容之后get的时候是用新的扩容之后的长度(扩容后的长度- 1) & hash去取得，所以你想要得到指定的值必须在扩容的时候把这个值放到指定的位置里，翻倍之后的容量转成二进制相当于比多了一位（例如2变4->010与100）计算index时（001与011），问题就在多的这一位上了，之后的流程参照上面的解释即可。
增与改
HashMap的put方法既是新增也是修改，当key存在则会覆盖原本的key的value。
添加（修改）单个元素
public V put(K key, V value) {
//先计算key的hash值
return putVal(hash(key), key, value, false, true);
}//扰动函数
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}这个函数被称为扰动函数，是为了解决hash碰撞问题，它综合hash值高位和低位的特征，并存放在低位，因此在与运算时，相当于高低位一起参与了运算，以减少hash碰撞的概率。为什么要将高位添加到低位呢？这是因为在HashMap中取桶下标的方式是通过 hash&(哈希桶.size-1)来替代模操作，而位操作的时候hashCode只有低位参与位运算。
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
//tab存放 当前的哈希桶， p用作临时链表节点
Node<K,V>[] tab; Node<K,V> p; int n, i;
//如果当前哈希表是空的，代表是初始化
if ((tab = table) == null || (n = tab.length) == 0)
//直接扩容哈希表，并且将扩容后的哈希桶长度赋值给n（即默认的16）
n = (tab = resize()).length;
//如果当前index的节点是空的，表示没有发生哈希碰撞。直接构建一个新节点Node，挂载在index处。
if ((p = tab[i = (n - 1) & hash]) == null)
tab[i] = newNode(hash, key, value, null);
else {
//发生哈希碰撞，链地址法解决哈希冲突
Node<K,V> e; K k;
//判断是否是对key进行覆盖value操作
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);
//如果追加节点后，链表数量>=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;
}
}
//如果e不是null，说明有需要覆盖的节点
if (e != null) { // existing mapping for key
//则覆盖节点值，并返回原oldValue
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
e.value = value;
//空实现函数，LinkedHashMap重写
afterNodeAccess(e);
return oldValue;
}
}
//修改modCount
++modCount;
//更新size，并判断是否需要扩容。
if (++size > threshold)
resize();
//空实现函数，LinkedHashMap重写
afterNodeInsertion(evict);
return null;
}批量添加（修改）元素
public void putAll(Map<? extends K, ? extends V> m) {
putMapEntries(m, true);
}putMapEntries这个方法在构造函数里已经分析，这里不多做赘述。
不覆盖添加
JDK 8新增了这个方法，当插入的key在Map里存在，不会覆盖。如方法名所表示，当Map里不存在将插入的key才执行插入。
@Override
public V putIfAbsent(K key, V value) {
return putVal(hash(key), key, value, true, true);
}查询
get(Object key)
public V get(Object key) {
Node<K,V> e;
//先对key进行hash操作
return (e = getNode(hash(key), key)) == null ? null : e.value;
}final Node<K,V> getNode(int hash, Object key) {
// first 是待查找节点的前置节点
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//如果哈希表不为空，则根据hash值算出的index下有节点的话
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);
//找到链表里的key值
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}关于下标的计算方式为(n - 1) & hash可以和上面的扩容函数关联上了！
getOrDefault(Object key, V defaultValue)
如果获取不到key的value就使用传入的默认值返回
@Override
public V getOrDefault(Object key, V defaultValue) {
Node<K,V> e;
return (e = getNode(hash(key), key)) == null ? defaultValue : e.value;
}containsKey(Object key)
public boolean containsKey(Object key) {
return getNode(hash(key), key) != null;
}containsValue(Object value)
public boolean containsValue(Object value) {
Node<K,V>[] tab; V v;
//遍历哈希桶上的每一个链表
if ((tab = table) != null && size > 0) {
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next) {
//如果找到value一致的返回true
if ((v = e.value) == value ||
(value != null && value.equals(v)))
return true;
}
}
}
return false;
}删除
remove(Object key)
public V remove(Object key) {
Node<K,V> e;
return (e = removeNode(hash(key), key, null, false, true)) == null ?
null : e.value;
}//matchValue是true，则必须key 、value都相等才删除
//如果movable参数是false，在删除节点时，不移动其他节点
final Node<K,V> removeNode(int hash, Object key, Object value,
boolean matchValue, boolean movable) {
// p 是待删除节点的前置节点
Node<K,V>[] tab; Node<K,V> p; int n, index;
if ((tab = table) != null && (n = tab.length) > 0 &&
(p = tab[index = (n - 1) & hash]) != null) {
//node是待删除节点
ode<K,V> node = null, e; K k; V v;
//如果链表头的就是需要删除的节点
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
node = p;
else if ((e = p.next) != null) {
//否则循环遍历 找到待删除节点，赋值给node
if (p instanceof TreeNode)
node = ((TreeNode<K,V>)p).getTreeNode(hash, key);
else {
do {
if (e.hash == hash &&
((k = e.key) == key ||
(key != null && key.equals(k)))) {
node = e;
break;
}
p = e;
} while ((e = e.next) != null);
}
}
//如果有待删除节点node， 且 matchValue为false，或者值也相等
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;//修改modCount
--size;//修改size
//LinkedHashMap回调函数
afterNodeRemoval(node);
return node;
}
}
return null;
}remove(Object key, Object value)
@Override
public boolean remove(Object key, Object value) {
return removeNode(hash(key), key, value, true, true) != null;
}遍历
entrySet()
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es;
return (es = entrySet) == null ? (entrySet = new EntrySet()) : es;
}final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public final int size() { return size; }
public final void clear() { HashMap.this.clear(); }
//获取迭代器
public final Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public final boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Node<K,V> candidate = getNode(hash(key), key);
return candidate != null && candidate.equals(e);
}
public final boolean remove(Object o) {
if (o instanceof Map.Entry) {
Map.Entry<?,?> e = (Map.Entry<?,?>) o;
Object key = e.getKey();
Object value = e.getValue();
return removeNode(hash(key), key, value, true, true) != null;
}
return false;
}
public final Spliterator<Map.Entry<K,V>> spliterator() {
return new EntrySpliterator<>(HashMap.this, 0, -1, 0, 0);
}
public final void forEach(Consumer<? super Map.Entry<K,V>> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
//遍历哈希桶
for (int i = 0; i < tab.length; ++i) {
//遍历哈希桶中不为null的链表数据
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}
}final class EntryIterator extends HashIterator
implements Iterator<Map.Entry<K,V>> {
public final Map.Entry<K,V> next() { return nextNode(); }
}abstract class HashIterator {
Node<K,V> next; // next entry to return
Node<K,V> current; // current entry
int expectedModCount; // for fast-fail
int index; // current slot
HashIterator() {
//因为hashmap也是线程不安全的，所以要保存modCount。用于fail-fast策略
expectedModCount = modCount;
Node<K,V>[] t = table;
current = next = null;
index = 0;
//next 初始时，指向 哈希桶上第一个不为null的链表头
if (t != null && size > 0) { // advance to first entry
do {} while (index < t.length && (next = t[index++]) == null);
}
}
public final boolean hasNext() {
return next != null;
}
//遍历HashMap时，顺序是按照哈希桶从低到高，链表从前往后，依次遍历的。属于无序集合。
final Node<K,V> nextNode() {
Node<K,V>[] t;
Node<K,V> e = next;
//fail-fast策略
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
if (e == null)
throw new NoSuchElementException();
//依次取链表下一个节点，
if ((next = (current = e).next) == null && (t = table) != null) {
//如果当前链表节点遍历完了，则取哈希桶下一个不为null的链表头
do {} while (index < t.length && (next = t[index++]) == null);
}
return e;
}
public final void remove() {
Node<K,V> p = current;
if (p == null)
throw new IllegalStateException();
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
current = null;
K key = p.key;
//利用removeNode 删除节点
removeNode(hash(key), key, null, false, false);
expectedModCount = modCount;
}
}forEach(BiConsumer<? super K, ? super V> action)
JDK 8新增的方法，可以不借助entryset就能完成遍历，但实际上代码和entryset里的foreach基本是一样的。
@Override
public void forEach(BiConsumer<? super K, ? super V> action) {
Node<K,V>[] tab;
if (action == null)
throw new NullPointerException();
if (size > 0 && (tab = table) != null) {
int mc = modCount;
for (int i = 0; i < tab.length; ++i) {
for (Node<K,V> e = tab[i]; e != null; e = e.next)
action.accept(e.key, e.value);
}
if (modCount != mc)
throw new ConcurrentModificationException();
}
}其他的一些方法
compute(K key,BiFunction remappingFunction)
用key来获取map中的value再做进一步的计算，如果key不存在且BiFunction 计算出来的value不为null则会新增，如果计算出来的value是null则会删除，如果既存在这个key，计算得到的value不为null则会替换。
@Override
public V compute(K key,
BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
if (remappingFunction == null)
throw new NullPointerException();
int hash = hash(key);
Node<K,V>[] tab; Node<K,V> first; int n, i;
int binCount = 0;
TreeNode<K,V> t = null;
Node<K,V> old = null;
if (size > threshold || (tab = table) == null ||
(n = tab.length) == 0)
n = (tab = resize()).length;
if ((first = tab[i = (n - 1) & hash]) != null) {
if (first instanceof TreeNode)
old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);
else {
Node<K,V> e = first; K k;
do {
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k)))) {
old = e;
break;
}
++binCount;
} while ((e = e.next) != null);
}
}
//上面是找key对应value的过程在get中已经解读过了，不再赘述
V oldValue = (old == null) ? null : old.value;
// 将原本map中的值进行计算
V v = remappingFunction.apply(key, oldValue);
//这个key是否存在
if (old != null) {
if (v != null) {
//替换原本的value
old.value = v;
//LinkedHashMap回调函数
afterNodeAccess(old);
}
else
//计算出来的新value是null的时候移除这个key
removeNode(hash, key, null, false, true);
}
//如果key不存在且计算出来的v不为null
else if (v != null) {
//如果是红黑树
if (t != null)
t.putTreeVal(this, tab, hash, key, v);
else {
//新增节点
tab[i] = newNode(hash, key, v, first);
if (binCount >= TREEIFY_THRESHOLD - 1)
treeifyBin(tab, hash);
}
//修改 修改次数以及个数
++modCount;
++size;
//LinkedHashMap回调函数
afterNodeInsertion(true);
}
return v;
}computeIfAbsent(K key,Function mappingFunction)
如果 key 对应的 value 不存在，则使用获取 remappingFunction 重新计算后的值，并保存为该 key 的 value，否则不计算返回 value。
代码和上面差不多就做简单使用介绍。
public V computeIfPresent(K key,BiFunction remappingFunction)
如果 key 对应的 value 不存在，则返回 null，如果存在，则返回通过 remappingFunction 重新计算后的值并替换map中该key的value。
小结
本文中其实对于红黑树的内部逻辑都规避了，将来有机会再写一篇关于的红黑树的笔记。
- 扩容是一个特别耗性能的操作，所以在使用HashMap的时候，最好能够初始化Map的大小避免频繁扩容；
- 负载因子是可以修改的，也可以大于1，但是建议不要轻易修改；
- HashMap是线程不安全的，并发环境建议使用ConcurrentHashMap；
- JDK 1.8引入红黑树大程度优化了HashMap的性能。
参考
https://tech.meituan.com/2016/06/24/java-hashmap.html
https://segmentfault.com/a/1190000016058789
https://zhangxutong.blog.csdn.net/article/details/77413921
https://juejin.cn/post/6844904015088599054#heading-31
https://blog.csdn.net/weixin_43895374/article/details/104857263