(源码基于JDK1.7)
HashMap的无参实例构造方法默认初始化容量是16（2的4次方）。如果我们使用指定初始化容量的实例构造函数，可以传入一个指定的值，但是实际HashMap在初始化底层存储数据的数组时，会使用一个大于等于指定值的2的幂的数作为数组的初始化容量。并且如果HashMap中元素的个数大于等于阈值并且根据key的哈希值和数组长度减一做按位与运算获取的数组下标位置元素非空，则需要扩容，扩容后容量是原来的2倍，也仍然是一个2的幂，那么HashMap为什么这样来做呢？
我们来从put(K key, V value)方法来一探究竟。先贴上put方法的源码：
public V p
在Java的集合框架中，HashMap是一种常用的键值对存储结构，其内部机制依赖于高效的哈希函数和数组+链表的存储方式。标题所提到的问题——HashMap的容量必须是2的幂，这是一个关键的设计决策，涉及到哈希表的性能和空间利用率。
HashMap的默认初始容量是16，这是2的4次方。当使用带容量参数的构造函数创建HashMap时，传入的容量会被调整为大于等于该值的最小的2的幂。例如，如果传入的容量是10，实际上HashMap会将容量设置为16。这种做法的背后有以下几个原因：
1. **高效索引计算**：HashMap通过`indexFor`方法将哈希值转换为数组下标。这个方法使用的是`h & (length-1)`的计算方式，其中`h`是哈希值，`length`是数组的容量。如果`length`是2的幂，那么`length - 1`的二进制形式会是一个全1的位序列。当与哈希值进行按位与操作时，结果会是一个范围在0到`length - 1`之间的数，这正好对应了数组的合法下标。若`length`不是2的幂，那么按位与运算的结果可能无法覆盖所有下标，导致部分数组位置永远不会被使用，从而浪费空间。
2. **优化哈希冲突**：通过使用2的幂作为容量，可以确保哈希函数的分布尽可能均匀，减少哈希冲突的可能性。哈希冲突会影响HashMap的查找、插入和删除效率，因为当哈希冲突发生时，数据会被存储到链表中，而链表操作比直接数组访问慢。
3. **快速扩容**：HashMap在元素数量达到当前容量的75%时会进行扩容，新的容量是旧容量的2倍，即2的幂。这样做的好处是，现有的所有键的哈希值在新容量下依然可以通过相同的`indexFor`方法计算出新的下标，因此在扩容过程中，只需要将原有的链表拆分到新的桶中，而不需要重新计算所有键的哈希值，大大提高了扩容效率。
4. **内存对齐**：在计算机硬件层面，内存分配通常以字节对齐，2的幂大小的内存块更容易满足对齐要求，从而提高内存访问速度。
总结来说，HashMap的容量必须是2的幂，主要是为了实现高效、均匀的哈希索引计算，优化空间利用率，简化扩容策略，并且考虑到硬件层面的内存对齐优化。这样的设计使得HashMap在处理大量数据时能够保持较好的性能表现。在实际开发中，理解这些细节有助于更好地使用和优化HashMap。
- 1
- 2
前往页