HashMap在大厂面试经常问到，比如：数据结构、哈希函数…等原理机制，下面我就全面来详解HashMap@mikechen
HashMap
HashMap是Java集合中非常常用的，用于存储键值对（key-value pairs）。
它基于哈希表实现，提供了高效的存储、和检索操作，数据结构如下图所示：
HashMap 的核心数据结构是一个数组，每个数组元素称为一个桶（bucket）。
// HashMap 内部的数组 Entry<K, V>[] table;
在每个桶中，HashMap 使用链表来存储具有相同哈希值的键值对。
在哈希表的每个桶中，HashMap 使用链表来解决哈希冲突。
每个链表节点是一个 Entry 对象，其中包含：键、值、哈希值和指向下一个节点的指针。
static class Entry<K,V> {
final K key;
V value;
Entry<K,V> next;
final int hash;
Entry(K key, V value, int hash, Entry<K,V> next) {
this.key = key;
this.value = value;
this.next = next;
this.hash = hash;
}
}
从 Java 8 开始，当一个桶中的链表长度超过一定阈值（默认值为 8）时，HashMap 会将链表转换成红黑树。
如下图所示：
// 将链表转换为红黑树
void treeifyBin(Entry<K, V>[] tab, int hash) {
// 创建红黑树并将链表中的元素转移到树中
}
红黑树是一种自平衡的二叉查找树，能够提供对数时间复杂度的操作性能。
红黑树的插入、删除和查找操作都是对数时间复杂度（O(log n)），因此在处理大量哈希冲突时，比链表更高效。
HashMap哈希函数
哈希函数，用于将键映射到数组的索引位置。
比如：HashMap 使用键的 hashCode() 方法生成哈希值，然后对哈希值进行处理，以确定元素在数组中的位置。
如下图所示：
大致流程，如下：
计算哈希值：
hashCode() 方法生成的整数值，被用来计算键在 HashMap 中的存储位置（即数组的索引）；
int hashCode = key.hashCode();
确定桶的位置：
根据 hashCode() 计算出的值，来决定将键值对存储到数组的哪个桶（bucket）中。
为了减少哈希冲突，HashMap 对 hashCode() 的返回值进行扰动处理。
int hash = hashCode ^ (hashCode >>> 16); // 使用位操作来扰动哈希码
如下图所示：
hashCode >>> 16 表示将 hashCode 的二进制表示右移 16 位，右移操作会将高位位移到低位，丢弃低位的部分。
hashCode ^ (hashCode >>> 16) 将原始的哈希码，与其右移后的结果进行异或操作。
异或操作的结果是：将对应位的值进行比较，相同为 0，不同为 1，这样可以混合哈希码的高位、和低位。
这样，混合后的哈希值能够将哈希码的高位和低位进行结合，提高哈希值的随机性，减少模式化现象。
HashMap动态扩容
HashMap 还会在元素数量达到负载因子,（默认为 0.75）乘以当前数组长度时进行扩容。
扩容时，所有元素会被重新哈希到一个新的、更大的数组中。
void resize() {
// 计算新容量
int newCapacity = oldCapacity * 2;
Entry<K, V>[] newTable = new Entry[newCapacity];
// 重新哈希并将旧表的元素转移到新表
for (Entry<K, V> e : table) {
if (e != null) {
transfer(newTable, e);
}
}
table = newTable;
threshold = (int) (newCapacity * loadFactor);
}
整体流程，如下图所示：
扩容过程包括：
创建新数组
扩容时，HashMap 创建一个新的更大的数组；
重新哈希
将旧数组中的所有元素重新计算哈希值，并将它们插入到新数组中，这一过程称为重新哈希（rehashing）。
这些数据结构和机制使 HashMap 在大多数情况下能够提供高效的查找、插入和删除操作。
线程安全
HashMap 是非线程安全的，如果多个线程同时对 HashMap 进行修改，可能会导致数据不一致或其他问题。
在多线程情况下，为了保证线程安全，可以使用 Collections.synchronizedMap、或者ConcurrentHashMap，来解决线程安全。
1.使用Collections.synchronizedMap
这个方法可以将普通的HashMap包装成线程安全的同步Map，但是在高并发场景下性能较低。
2.使用ConcurrentHashMap
ConcurrentHashMap是专门为并发设计的哈希表，它采用了分段锁（在JDK 7及之前）或CAS操作（在JDK 8及之后），可以在高并发环境下提供更高的性能和线程安全性。
