913内容整理
一、数据存储结构
数组+链表基础结构：HashMap在JDK 1.7版本中的底层实现是基于数组和链表的组合。数组的每一个位置（也称为“桶”或“槽位”），都对应一个链表的头部。当不同的键通过哈希函数计算得到同一个数组下标时，这些键值对会被存放在同一个桶中的链表上。链表的存在解决了哈希冲突问题，使得即使多个键的哈希值相同，也能通过链表顺序存储而不丢失数据。
红黑树优化：为了进一步优化性能，从JDK 1.8开始，当链表的长度超过一定阈值（默认为8）时，链表会被转换为红黑树。红黑树是一种自平衡的二叉查找树，它能将查找、插入和删除操作的时间复杂度保持在O(log n)。这一优化对于大规模数据操作尤其重要，有效提升了性能。
二、哈希算法与定位
哈希算法：HashMap通过哈希算法来确定键应该存放在数组的哪个位置。系统首先调用键对象的hashCode方法，再使用HashMap内部的哈希函数处理得到的哈希码，最终将其映射到数组的一个索引位置上。具体来说，HashMap使用indexFor()方法，通过将哈希值与数组长度减一的结果进行按位与操作(&)来确定对象在数组中的具体位置。由于数组长度总是2的幂次方，按位与操作等价于取模操作，从而提高了计算效率。
索引计算：HashMap中的索引计算是快速定位键值对的关键。通过将键的哈希值与数组长度减一的结果进行按位与操作，可以快速确定该键值对在数组中的位置。这种设计确保了无论数据集多大，都能以常数时间复杂度定位到键值对的位置。
三、扩容机制
扩容触发条件：HashMap引入了负载因子的概念（默认值为0.75），当元素数量达到数组长度与负载因子乘积时，就会触发扩容。扩容是HashMap维持高性能的重要机制，通过增大数组容量来降低哈希冲突的概率。
扩容过程：扩容涉及创建一个新数组，其大小通常是原数组的两倍，并将原有数据重新散列到新数组中。这个过程虽然可能会耗费一定的时间，但长远来看，通过减少哈希冲突，提升了HashMap的整体性能。
四、链表转红黑树优化
树化阈值：当一个链表的长度超过8时，为了提高查询效率，链表会被转换为红黑树。这是一种优化措施，用以提高长链表中的操作效率。
反树化阈值：在进行扩容操作时，如果红黑树中的节点数量降到6以下，红黑树会被转回链表。这一机制保证了数据结构的灵活性和高效性，避免了不必要的树化开销。
五、高效查找与插入
查找操作：HashMap通过高效的哈希算法和索引计算，能够快速定位到键所对应的数组位置。即使在发生哈希冲突的情况下，链表或红黑树的结构也能保证高效的查找。
插入操作：新键值对的插入同样依赖于哈希算法和索引计算。如果有哈希冲突，新元素会被插入到链表的头部或红黑树的相应位置，保持数据结构的有序性。
