"为什么每次扩容是2的n次幂？-HashMap源码分析"
HashMap作为Java中常用的哈希映射类，其内部实现涉及到许多关键知识点。首先，HashMap使用哈希表的数据结构，通过键（Key）的hashCode计算出哈希值，这个哈希值用于确定键值对在数组中的位置，即下标。由于哈希函数并不完美，不同对象可能会计算出相同的哈希值，导致所谓的哈希冲突。
为了解决哈希冲突，HashMap在JDK 1.8中引入了数组+链表+红黑树的混合结构。当链表长度达到一定阈值（通常为8）时，链表会转换为红黑树，以保持查询效率。关键属性包括：
1. **容量(capacity)**: 指HashMap中桶的数量，默认为16。容量总是2的幂，如16、32、64等，这是为了便于位运算，提高效率。
2. **装载因子(loadFactor)**: 表示HashMap填满的程度，默认值为0.75f。装载因子越高，空间利用率越高，但可能导致更多的哈希冲突；反之，装载因子越低，冲突减少，但空间浪费增加。
3. **阈值(threshold)**: 当HashMap的元素数量超过阈值时，会触发扩容操作。阈值等于容量乘以装载因子。
HashMap有四种构造方法，可以指定初始容量和装载因子。当添加元素导致size超过阈值时，HashMap会进行扩容。扩容过程通常是将当前容量翻倍，这能确保通过`(n-1)`与哈希值进行与运算时，仍能有效地求余，避免冲突。
`Hash()`函数是HashMap中用于计算哈希值的关键部分，它对原始的hashCode进行优化，减少冲突的可能性。只有当哈希值超过2的16次方时，`Hash()`函数才会产生显著效果。
`Resize()`函数负责处理扩容操作。如果table为空，它会按照threshold分配空间；否则，将现有元素复制到新table中，新位置可能在原索引或加上2的次幂位移。这样设计保证了原有的哈希关系尽可能不变，同时保持了高效性。
`put()`过程是HashMap的核心操作，它先计算键的哈希值，找到合适的插入位置，如果位置已有元素，则处理冲突，可能是链表的链接或红黑树的插入。
总结来说，HashMap通过2的n次幂扩容策略，结合高效位运算，保证了哈希表的高效性和均匀分布，从而优化了查找、插入和删除操作的性能。理解这些原理对于深入掌握Java集合框架至关重要。
我的内容管理
展开
