hashmap 为什么采用2的幂次方
时间: 2023-10-03 08:09:53 浏览: 97
HashMap的容量为什么必须是2的幂?
5星 · 资源好评率100%
HashMap采用2的幂次方作为数组长度的原因有以下几点:
1. 快速计算数组下标:使用2的幂次方作为数组长度,可以通过位运算(&)快速计算数组下标,而不需要使用取模等较慢的操作。
2. 减少哈希冲突:哈希函数通常会将键的哈希码映射到数组的下标上,如果数组长度不是2的幂次方,哈希码的低位可能无法充分参与计算,导致哈希冲突较多,而使用2的幂次方作为数组长度,可以保证哈希码的所有位都可以充分参与计算,减少哈希冲突的概率。
3. 方便扩容:HashMap在扩容时,会将原来的数组长度翻倍,如果数组长度不是2的幂次方,翻倍后可能会导致哈希码映射到的下标发生大幅度变化,需要重新计算所有键的下标,而使用2的幂次方作为数组长度,翻倍后只需要将原来的下标的低位增加一位即可,不需要重新计算所有键的下标,方便扩容操作。
阅读全文