2019獨角獸企業(yè)重金招聘Python工程師標(biāo)準(zhǔn)>>>

HashMap為了存取高效，要盡量較少碰撞，就是要盡量把數(shù)據(jù)分配均勻，每個鏈表長度大致相同。

關(guān)鍵就在于把當(dāng)前數(shù)據(jù)存放到哪一個桶中，這個算法就是取模運算。

假設(shè)：

length：HashMap的容量

hash：當(dāng)前key的哈希值

取模運算為 hash % length

但是，在計算機中，直接取模運算的效率不如位運算（&），什么是位運算？就是對于二進制數(shù)據(jù)的按位運算，1和1才得1，其他都得0，比如：1011 & 1100 = 1000

sun公司的大牛們發(fā)現(xiàn)，當(dāng)容量為2的n次方時，hash & (length - 1) == hash % length ，于是就在源碼中做了優(yōu)化，通過 hash & (length - 1) 來替代取模運算，而前提就是容量必須為2的n次方。這樣做的好處在于：

1. 提高操作運算效率（位運算效率 > 取模運算效率）

2.?減少碰撞，數(shù)據(jù)均勻分布，提高HashMap查詢效率

為什么可以減少碰撞？舉個例子，現(xiàn)在兩個hash分別是2和3,：

比如 length 為 9 的情況：3&(9-1)=0? 2&(9-1)=0 ，都在0上，碰撞了；

比如 length 為 8 的情況：3&(8-1)=3? 2&(8-1)=2 ，不同位置上，不碰撞；

?

轉(zhuǎn)載于:https://my.oschina.net/edwardge/blog/1844438

總結(jié)

以上是生活随笔為你收集整理的HashMap的容量（桶的数量）为什么要是2的n次方的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。