当前位置：首页 > article >正文

Java高频面试之集合-14

article 2025/3/19 12:18:08

hello啊，各位观众姥爷们！！！本baby今天来报道了！哈哈哈哈哈嗝🐶

面试官：为什么 HashMap 的容量是 2 的倍数呢？

HashMap的容量被设计为2的幂次，主要基于以下原因：

高效的索引计算
- 位运算替代取模：当容量为2的幂次时，计算元素在数组中的索引可以通过位运算 hash & (capacity - 1) 实现，效率远高于取模运算 hash % capacity。例如：
```
// 当 capacity = 16 (2^4) 时：
int index = hash & (16 - 1); // 等价于 hash % 16，但更快
```
- 硬件优化：位运算在底层硬件中执行更快，仅需几个时钟周期，而取模运算需要更多指令。
均匀的哈希分布
- 哈希函数优化：HashMap对键的哈希值进行二次处理（如异或高位与低位），确保低位分布更均匀：
```
static final int hash(Object key) {
    int h;
    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
```
- 减少冲突：当容量为2的幂次时，哈希值的高位信息通过按位与操作参与索引计算，避免仅依赖低位导致冲突。
扩容的便捷性
- 容量翻倍：扩容时容量直接翻倍（如16→32），新索引可通过位运算快速确定：
```
// 旧容量为16时，扩容后为32：
if ((e.hash & oldCap) == 0) {
    // 新索引 = 原索引
} else {
    // 新索引 = 原索引 + 原容量
}
```
- 减少重新哈希开销：无需重新计算所有元素的索引，仅需判断高位是否为1。

用户输入的自动修正

容量对齐：若用户指定初始容量非2的幂次，HashMap会通过 tableSizeFor() 方法调整为最近的2的幂次：

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

总结

设计选择	优势
2的幂次容量	位运算高效计算索引，提升性能。
哈希函数优化	高位参与索引计算，减少哈希冲突。
扩容机制	翻倍扩容配合位运算，快速重新分配元素。
自动容量修正	确保用户输入的容量符合2的幂次，保持设计一致性。

示例：