HashMap是基于哈希表实现的，通过键的 hashCode 来快速定位值的存储位置，它允许存储null键和null值。HashMap不保证元素的顺序，特别是它不保证该顺序恒久不变。
HashMap是非同步的，它不支持多线程环境下的并发修改。HashMap 可以说是 Hashtable 的轻量级替代品，不具备同步特性，因此在单线程环境下性能更好。
HashMap的初始容量和加载因子可以调整。
在HashMap中，采用数组+链表的方式来实现对数据的储存。
哈希条目Node
存储的数据是一个继承了Entry的Node类，包含有键值对，并且这个类具有指向下一个Entry的指针。
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
}
transient Node<K,V>[] table;这个类用于表示哈希表中的一个条目（键值对），并且可以链接起来形成链表来处理哈希冲突。
JDK1.8中，为了提高性能，当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树。
hashCode 方法
public final int hashCode() {
return Objects.hashCode(key) ^ Objects.hashCode(value);
}主要作用：
- 生成当前条目的哈希码，该哈希码是基于条目的键（
key）和值（value）的哈希码计算得出的。 - 在哈希表中，
hashCode方法用于确定条目应该存储在哪个哈希桶（bucket）中，以及在查找、删除等操作中快速定位条目。 - 使用异或（
^）操作符来组合键和值的哈希码，可以提供一种合理的哈希分布，减少哈希冲突。
setValue 方法
public final V setValue(V newValue) {
V oldValue = value;
value = newValue;
return oldValue;
}主要作用：
- 更新条目中的值，同时返回更新前的旧值。
- 这个方法允许用户修改哈希表中条目的值，而不改变键。
equals 方法
public final boolean equals(Object o) {
if (o == this)
return true;
return o instanceof Map.Entry<?, ?> e
&& Objects.equals(key, e.getKey())
&& Objects.equals(value, e.getValue());
}主要作用：
- 判断当前条目是否与另一个对象相等。
- 根据
Map.Entry接口的约定，两个条目相等当且仅当它们的键和值都相等。 - 在哈希表中，这个方法用于在查找或删除操作中比较两个条目是否相同。
- 通过使用
==操作符首先检查对象引用是否相同，可以优化性能，因为如果两个引用指向同一个对象，它们必然相等。 - 使用
instanceof操作符和Objects.equals方法确保了类型安全，并且能够正确处理null值。
初始化容量
初始化容量是指HashMap在创建时分配的内部数组（桶）的大小。这个数组的大小决定了HashMap可以存储多少个键值对，同时也影响着HashMap的性能，比如查找、插入和删除操作的效率。
tableSizeFor方法用于将用户指定的容量转换为大于或等于该容量的最小的2的幂次方。
static final int tableSizeFor(int cap) {
int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}这个方法做了以下几件事情：
- 计算cap-1的位数：java这个方法返回
Integer.numberOfLeadingZeros(cap - 1)cap - 1中前导零的个数，即从最高位开始到第一个1出现的位置的位数。 - 使用无符号右移操作：java
-1 >>> Integer.numberOfLeadingZeros(cap - 1)-1是一个32位全为1的二进制数。通过将-1无符号右移上面计算出的位数，我们得到一个二进制数，它的低位都是1，高位都是0，并且位数正好是cap - 1中第一个1出现的位置。 - 确保结果为正数： 如果
cap小于等于0，那么cap - 1将是一个负数，numberOfLeadingZeros将返回0，右移操作将不起作用，因此n会是-1。这里通过(n < 0) ? 1确保了当cap小于等于0时，返回的数组大小至少为1。 - 限制最大容量： 如果计算出的
n大于或等于MAXIMUM_CAPACITY（即2^30），则直接返回MAXIMUM_CAPACITY。这是为了避免创建过大的数组，同时也是因为HashMap内部实现不支持超过MAXIMUM_CAPACITY的数组大小。 - 返回大于或等于cap的最小2的幂： 如果
n既不是负数也不超过最大容量，那么返回n + 1。因为n是低位都是1的数，n + 1将得到一个2的幂次方数，且这个数大于或等于cap。
为什么HashMap的容量要是2的幂？
- 提高哈希分布的均匀性：使用2的幂次方大小作为容量可以使得
index = (n - 1) & hash的操作更加高效和均匀地分布键值对到桶中。 - 简化哈希值的映射：位运算
&（与操作）比取模操作%更快，且在数组大小为2的幂时，index = (n - 1) & hash等价于index = hash % n。
负载因子
负载因子（Load Factor）用来衡量HashMap满的程度。
负载因子 = HashMap中已存储的键值对数量 / HashMap的总容量
在HashMap中，还有一个阈值（Threshold）的概念，当实际存储的键值对数量超过阈值时，就需要对哈希表进行扩容。而阈值就是由容量和负载因子相乘得出的。
负载因子的用途：
- 控制扩容时机： 负载因子决定了HashMap何时进行扩容操作。当HashMap中的元素数量达到其容量与负载因子的乘积时，即认为HashMap太满了，需要进行扩容以维持操作效率。
- 平衡空间和时间效率：
- 高负载因子：减少空间开销，但增加了查询时间（因为碰撞的可能性更高，链表或树可能更长）。
- 低负载因子：提高查询效率，但增加了空间开销（因为HashMap会在达到较低的使用率时就进行扩容）。
在Java的HashMap中，默认的负载因子是0.75，这是一个时间和空间成本平衡的选择。这个值既不会导致HashMap占用过多的空间，也不会使HashMap的性能因为碰撞过多而急剧下降。
扰动函数
HashMap扰动函数的目的是为了改善哈希值的分布，从而减少哈希碰撞的概率，并提高HashMap的性能。
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}- 检查键是否为null：java如果键是null，那么根据HashMap的约定，null键应该映射到数组的第一个位置，所以直接返回0。
return (key == null) ? 0 : ... - 计算键的哈希码：java调用键对象的
h = key.hashCode()hashCode()方法来获取原始的哈希码。这个哈希码是由键对象自己的hashCode()方法计算得到的，该方法应该为不同的对象返回不同的整数。 - 扰动函数：java扰动函数的核心是使用异或操作（
(h = key.hashCode()) ^ (h >>> 16)^）和无符号右移操作（>>>）来混合原始哈希码的高位和低位。- 无符号右移操作：java将原始哈希码
h >>> 16h无符号右移16位。无符号右移会在左边补0，因此，这个操作会丢弃原始哈希码的最高16位，并将它们移动到最低16位的位置。 - 异或操作：java将原始哈希码
(h = key.hashCode()) ^ (h >>> 16)h与其右移16位后的结果进行异或操作。异或操作的特点是，如果两个比较的位不同，则结果为1，否则为0。因此，这个操作会混合原始哈希码的高16位和低16位，从而增加低16位的随机性。
- 无符号右移操作：
为什么需要这样的扰动？
- 提高哈希值的随机性：动函数通过混合高位和低位，增加了随机性，使得哈希值更加均匀地分布在HashMap的数组中。
- 利用所有哈希位：在计算数组索引时，通常只会使用哈希值的低位，因为数组大小有限。扰动函数确保了高位的影响也能体现在最终的索引计算中，使得所有的哈希位都能被有效利用。
put方法
HashMap 的 put 方法用于将键值对插入到哈希表中。下面是 put 方法的执行流程详解：
计算哈希码:
- 使用传入的键
key调用hash()方法来计算该键的哈希码。
- 使用传入的键
检查容量和初始化:
- 如果内部数组
table为空或者长度为0，则调用resize()方法来初始化或调整容量。resize()方法会创建一个新的数组，并且可能迁移已有的元素到新的数组中。
- 如果内部数组
确定索引位置:
- 使用计算出的哈希码和数组长度（
n）计算索引位置i。这里使用了位运算(n - 1) & hash，它相当于取模操作%，但通常更快。
- 使用计算出的哈希码和数组长度（
检查索引位置上的节点:
- 如果索引位置
i上没有节点 (tab[i] == null)，则直接创建一个新节点并将其放置在该位置。 - 新节点
Node设置的信息包括键（key）的哈希码、键、值、下一个节点的引用null。
- 如果索引位置
处理链表中的节点:
- 如果索引位置上有节点，则需要进一步处理：
- 检查该节点是否与要插入的键相同（通过哈希码和键的相等性判断）。如果相同，则更新该节点的值，并返回旧值。
- 如果该节点是一个红黑树节点 (
TreeNode)，则调用putTreeVal()方法将键值对插入到树中。 - 如果该节点是链表中的第一个节点，遍历整个链表直到找到匹配的键或者到达链表尾部。如果找到了匹配的键，则更新其值；如果没有找到，则在链表尾部添加新的节点。
- 如果在链表中添加新节点导致链表长度超过阈值
TREEIFY_THRESHOLD（默认8），则调用treeifyBin()方法将链表转换为红黑树。
- 如果在链表中添加新节点导致链表长度超过阈值
- 如果索引位置上有节点，则需要进一步处理：
树化操作:
treeifyBin()方法将链表转换成树结构。它遍历链表，将每个节点转换为TreeNode，然后构建红黑树结构。
更新状态:
- 在插入新节点后，增加
modCount和size字段。 - 如果
size大于threshold，则调用resize()方法来重新分配更大的数组并重新散列所有元素。 - 调用
afterNodeInsertion()方法进行一些清理工作，例如维护统计信息或触发其他清理任务。
- 在插入新节点后，增加
返回结果:
- 如果插入的是一个新键值对，则返回
null。 - 如果覆盖了一个旧键值对，则返回旧值。
- 如果插入的是一个新键值对，则返回
源码
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}put方法实际执行putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict)方法。
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;
}下面是树化的源码。
final void treeifyBin(Node<K,V>[] tab, int hash) {
int n, index; Node<K,V> e;
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 {
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);
}
}扩容
resize()方法是Java中用于调整HashMap容量的核心方法。当HashMap中的元素数量达到阈值（其容量与负载因子乘积）时，就会触发扩容操作。
final Node<K,V>[] resize() {
// ...
}该方法返回一个新的Node<K,V>[]数组，即调整大小后的新哈希表。
方法步骤
保存旧表和旧容量：
javaNode<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; int oldThr = threshold;这里保存了当前的哈希表
table、容量oldCap和阈值oldThr。初始化新容量和阈值：
javaint newCap, newThr = 0;初始化新容量
newCap和新阈值newThr。判断旧容量：
- 如果旧容量大于0，并且小于最大容量
MAXIMUM_CAPACITY，则新容量是旧容量的两倍，新阈值也是旧阈值的两倍。 - 如果旧容量大于等于最大容量，则阈值设置为
Integer.MAX_VALUE，不再扩容。 - 如果旧容量为0但旧阈值大于0，说明是初始化时阈值被设置为初始容量，这时新容量就是旧阈值。
- 如果旧容量和旧阈值都为0，使用默认值初始化。
- 如果旧容量大于0，并且小于最大容量
计算新阈值： 如果新阈值
newThr为0，根据新容量和负载因子计算新阈值。更新阈值和创建新表：
javathreshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab;更新阈值，并根据新容量创建新的哈希表。
迁移旧表数据到新表：
- 遍历旧表中的每个桶（bucket）。
- 如果桶中只有一个节点，直接将其放入新表。
- 如果桶中是一个树节点，调用
split方法处理。 - 如果桶中是链表，需要重新计算每个节点的位置，因为容量变化了，索引的计算方式也变了。这里使用链表中的两个指针
loHead和hiHead来维护两个链表，分别对应不需要移动和需要移动的节点。
返回新表： 最后，返回新的哈希表数组。
迁移节点的细节
迁移节点的细节
对于链表中的每个节点，通过以下方式判断其在新表中的位置：
(e.hash & oldCap) == 0：如果为真，节点在新表中的位置不变。- 否则，节点在新表中的位置是原位置加上旧容量。
哈希桶索引的计算方式
在Java的HashMap中，哈希桶索引是通过以下公式计算的：
index = e.hash & (cap - 1)这里，e.hash是键的哈希码，cap是当前HashMap的容量（必须是2的幂）。cap - 1会生成一个所有位都是1的二进制数，例如：
- 如果容量是16（即
cap = 16），那么cap - 1是15，二进制表示为0000 1111。 - 如果容量是32（即
cap = 32），那么cap - 1是31，二进制表示为0001 1111。 通过e.hash & (cap - 1)的操作，可以确保计算出的索引始终在0到cap - 1的范围内。
容量加倍的影响
当HashMap进行扩容时，容量会加倍。假设原始容量是16，元素数量大于阈值12（16*0.75）时扩容，扩容后变为32。以下是扩容前后索引计算的变化：
- 在原始容量16时，
cap - 1是15（二进制0000 1111），哈希值与15进行位与操作得到索引。 - 在扩容后的容量32时，
cap - 1是31（二进制0001 1111），哈希值与31进行位与操作得到新的索引。
(e.hash & oldCap) == 0的原理
原始容量oldCap是2的幂，因此oldCap - 1的最高位是0，其余位都是1。当我们扩容时，oldCap的最高位变成了1，其余位仍然是0。
因此，当对哈希值e.hash与oldCap进行位与操作时，我们实际上是在检查哈希值的最高位（在oldCap中对应于新增加的那一位）是否为0：
- 如果
(e.hash & oldCap) == 0，说明哈希值的最高位为0，这意味着在扩容后的索引计算中，哈希值与newCap - 1的位与操作结果不会改变，因此节点的索引位置不变。 - 如果
(e.hash & oldCap) != 0，说明哈希值的最高位为1，这意味着在扩容后的索引计算中，哈希值与newCap - 1的位与操作结果会改变，节点的新索引位置将是原索引加上oldCap。
示例
假设原始容量是16，哈希值是e.hash，扩容后的容量是32：
- 原始索引计算：
e.hash & (16 - 1)=e.hash & 15 - 扩容后索引计算：
e.hash & (32 - 1)=e.hash & 31
如果e.hash是0101 1101（93），则：
(e.hash & 15)=0101 1101 & 0000 1111=0000 1101= 13（原始索引）(e.hash & 31)=0101 1101 & 0001 1111=0001 1101= 29（扩容后索引）
如果(e.hash & 16) == 0，即(e.hash & oldCap) == 0，则原始索引13在扩容后不变。否则，新索引将是原始索引加上oldCap，即13 + 16 = 29。
通过这种方式，HashMap能够在扩容时快速地重新计算节点的索引，而无需重新计算所有键的哈希码。
源码
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) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
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;
@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) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
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;
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;
}自定义类键
在Java中，如果我们要将自定义的对象作为键（Key）存储在HashMap中，那么重写hashCode()和equals()方法通常是必须的。这是因为HashMap通过这两个方法来确定键的唯一性。
hashCode()方法：当我们把一个对象放入HashMap时，HashMap会调用这个对象的
hashCode()方法来决定该对象在哈希表中的位置。默认情况下，
hashCode()返回的是对象内存地址的哈希码。如果不对它进行重写，即使是内容完全相同的对象，也会因为内存地址的不同而得到不同的哈希码，导致它们在HashMap中的位置不一致，这显然违背了HashMap的设计初衷。equals()方法：当HashMap在哈希表中定位到某个位置时，它会使用
equals()方法来确认存放于该位置的对象是否与要存储的对象相同。默认的
equals()方法仅比较对象引用，即内存地址。如果我们不重写它，即使两个对象的哈希码相同，HashMap也无法识别它们是否代表同一个键。想象一下，两个内容相同但内存地址不同的对象，在默认情况下会被视为不同的键，这显然不是我们想要的。