HashMap原理分析

未专门声明的情况,都是 1.8 的代码。

hash函数

确定桶的算法:

1
i = (n - 1) & hash

本质是为了将 hash 这个 int 通过取模,获得一个数组上的一个位置,这个获取需要均匀,等价于 i = hash % n。有点类似数据库分库分表的路由算法。

在 n 为 2 的 n 次方时,i = (n - 1) & hash 等价于 i = hash % n。并且性能更好,位运算比求余计算性能更好。

Read more