摘要：HashMap通过调用键的hashCode方法并应用一个扰动函数来计算哈希值。扰动函数的设计是为了减少哈希冲突，它通过将哈希码的高位与低位进行混合来实现。
HashMap的put操作过程主要包括以下几个步骤：
计算键的哈希值定位桶（Bucket）处理冲突调整哈希表大小HashMap通过调用键的hashCode方法并应用一个扰动函数来计算哈希值。扰动函数的设计是为了减少哈希冲突，它通过将哈希码的高位与低位进行混合来实现。
static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode) ^ (h >>> 16);}在HashMap中，key.hashCode >>> 16 这个操作是为了减少哈希冲突，并提高哈希表的性能。为什么是16而不是其他数字呢？比如32？
哈希表的长度通常是2的幂：HashMap的数组长度（即桶的数量）通常是2的幂。性能优化：选择16作为右移的位数是一个经验值，这个值是在多次实验和调优后确定的。避免高位信息丢失：如果右移的位数过多（例如32位，这实际上相当于丢弃了整个哈希码的高位），那么哈希值将完全由低位决定，这可能导致哈希冲突的增加。计算出的哈希值用于确定键值对在哈希表中的存储位置，即数组的索引。由于哈希表的大小通常是2的幂，因此可以通过(n - 1) & hash快速计算数组索引，其中n是数组的长度。
// 在putVal方法中，使用这个hash函数来确定桶的位置final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node tab;Node p;int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize).length;// 使用(n - 1) & hash来确定桶的位置if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 桶中已有元素，进行后续处理（如链表插入、红黑树转换等）}// ...（后续处理代码省略）}当两个不同的键映射到相同的数组索引时，会发生哈希冲突。HashMap这样处理冲突：
链表法：在JDK 1.8及之前版本中，当发生冲突时，会将新节点添加到链表的末尾。在JDK 1.8及以后版本中，如果链表长度超过一定阈值（默认为8），则会考虑将链表转换为红黑树以优化查找性能。红黑树：在JDK 1.8及以后版本中，如果链表长度超过8且数组容量大于等于64，链表会转换为红黑树。红黑树的插入、删除和查找操作都具有较高的性能。大家可以看下源码，JDK8的：
final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node tab;Node p;int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize).length;// 使用(n - 1) & hash来确定桶的位置if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {// 桶中已有元素，处理冲突Node 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)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 nodetreeifyBin(tab, i);break;}if (e.hash == hash &&((k = e.key) == key || (key != null && key.equals(k))))break;p = e;}}if (e != null) { // existing mapping for keyV oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;afterNodeAccess(e);return oldValue;}}++modCount;if (++size > threshold)resize;afterNodeInsertion(evict);return null;}在HashMap中，当元素数量超过当前数组的容量乘以加载因子（默认是0.75）时，会触发扩容操作。扩容操作主要在putVal方法中进行检查，并在必要时调用resize方法。
final Node resize {Node oldTab = table; // 获取旧entry数组int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取旧entry数组的大小int oldThr = threshold; // 获取旧entry数组的扩容临界值（数组大小*加载因子）int newCap, newThr = 0;// 如果旧entry数组容量大于0if (oldCap > 0) {// 如果旧entry数组容量超出最大值，则不进行扩容处理，直接返回if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 新entry数组扩容至旧entry数组的两倍else if ((newCap = oldCap = DEFAULT_INITIAL_CAPACITY)newThr = oldThr 0)newCap = oldThr;// 否则，进行数组默认初始化else {newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}threshold = newThr; // 更新扩容临界值Node newTab = (Node)newNode[newCap]; // 创建新的entry数组table = newTab; // 更新table为新的entry数组// 将旧entry数组中的元素重新hash并转移到新entry数组中for (int j = 0; j e;if ((e = oldTab[j]) != null) {oldTab[j] = null;if (e.next == null) // 没有形成链状，则直接把该entry重新hash分配到新的entry数组中newTab[e.hash & (newCap - 1)] = e;else if (e instanceof TreeNode) // 树形结构，则进行拆分处理((TreeNode)e).split(this, newTab, j, oldCap);else { // 链表结构，进行拆解处理Node loHead = null, loTail = null;Node hiHead = null, hiTail = null;Node next;do {next = e.next;if ((e.hash & oldCap) == 0) {if (loTail == null)loHead = e;elseloTail.next = e;loTail = e;} else {if (hiTail == null)hiHead = e;elsehiTail.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;}扩容过程主要这几步：
获取旧数组及其属性：首先获取旧的entry数组（table），然后获取其大小（oldCap）和扩容临界值（oldThr）。计算新数组大小和临界值：根据旧数组的大小和扩容规则（通常是扩容为原来的两倍），计算新数组的大小（newCap）和新的扩容临界值（newThr）。更新扩容临界值：将新的扩容临界值（newThr）赋值给threshold，以便后续扩容时使用。创建新数组：创建一个新的entry数组（newTab），大小为newCap。将table更新为新数组：将table引用指向新的entry数组newTab。重新hash并转移元素：遍历旧entry数组，将每个位置的元素（可能是链表或树形结构）重新hash并转移到新entry数组的相应位置。加载因子为什么是0.75？
泊松分布的应用：当加载因子为0.75时，根据泊松分布的特性，可以计算出桶中元素数量的概率分布。例如，桶中元素数量为8的概率非常低，这有助于在链表长度过长时及时转换为红黑树结构，以提高性能。0.75作为加载因子的默认值，是经过大量实践和测试得出的经验值。它能够在大多数情况下提供良好的性能和空间利用率。
HashMap在JDK8中的实现基于数组和链表（以及红黑树，当链表长度超过一定阈值时），并且没有内置同步机制来确保多线程环境下的线程安全。因此，当多个线程同时访问和修改HashMap时，可能会导致数据不一致的问题。
并发扩容的问题在多线程环境下，如果两个线程同时执行扩容操作，可能会导致数据不一致或丢失。
如果一个线程正在扩容，而另一个线程也在尝试插入新元素，那么可能会出现新元素被插入到旧数组中的情况，或者新元素在迁移到新数组时丢失。
数据覆盖问题ConcurrentHashMap是Java提供的一个线程安全的Map实现。它内部采用了分段锁（在JDK7中）或CAS+Synchronized（在JDK8及以后版本中）等机制来保证线程安全。
因此，使用ConcurrentHashMap可以避免HashMap在多线程环境下的安全性问题，同时保持较高的性能。
来源：马士兵老师
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
