HashMap的容量(桶的数量)为什么要是2的n次方

    技术2025-02-03  8

    HashMap的容量(桶的数量)为什么要是2的n次方

    HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同。 关键就在于把当前数据存放到哪一个桶中,这个算法就是取模运算。

    假设: length:HashMap的容量 hash:当前key的哈希值 取模运算为 hash % length 但是,在计算机中,直接取模运算的效率不如位运算(&),什么是位运算?就是对于二进制数据的按位运算,1和1才得1,其他都得0,比如:1011 & 1100 = 1000

    sun公司的大牛们发现,当容量为2的n次方时,hash & (length - 1) == hash % length ,于是就在源码中做了优化,通过 hash & (length - 1) 来替代取模运算,而前提就是容量必须为2的n次方。这样做的好处在于:

    提高操作运算效率(位运算效率 > 取模运算效率)减少碰撞,数据均匀分布,提高HashMap查询效率

    为什么可以减少碰撞? 举个例子,现在两个hash分别是2和3: 比如 length 为 9 的情况:3&(9-1)=0 2&(9-1)=0 ,都在0上,碰撞了; 比如 length 为 8 的情况:3&(8-1)=3 2&(8-1)=2 ,不同位置上,不碰撞;

    Processed: 0.009, SQL: 9