資料結構
HashMap是一個以key,value鍵值對存盤的集合,效率高使用方便
內部結構是一個陣列加(鏈表or紅黑樹)的方式存盤
哈希因子
初始化的時候是可以自己指定的,默認的哈希因子是0.75
threshold為他的陣列長度,他的陣列長度是2的n次方
假如我們傳入一個值為65
65-1就是64 二進制就是1000000
1000000|100000==1100000（n |= n >>> 1）
1100000|=11000=1111000（n |= n >>> 2）
1111000|111=1111111（n |= n >>> 4）
后面的已經可以不用算了
1111111+1=10000000
所以說這個演算法是用或運算讓HashMap的陣列長度怎么都是2的n次方
為什么是2的n次方了,下面會講
有興趣的可以自己去算下
下標
HashMap是怎么確定傳進來的物件陣列下標的位置了
用物件的hashCode與自己的前16位于后16位做異或運算,打散他的hsahCode值讓前后位都參與運算
然后在用計算后的hsahCode與長度-1做與運算
為什么要這樣計算了
我們剛剛說了他的長度是2的n次方
2的n次方-1 假如n=3
二進制就是10000-1=1111
假如是5=n 就是1000000-1=111111
假如hashcode=1101010111001
1111|1101010111001=1001
111111|1101010111001=111001
這樣就可以計算出下標,也可以用hsahCode跟陣列長度取模,但是這樣沒有這種演算法效率高
有人就會發現
1100|1101010111001也不會超過陣列長度,但是這個的話就會導致一個問題
1100為0的地方計算出來的位永遠為0,就會導致不均勻
擴容
當插入的容量不夠用的時候就會擴容
HashMap的擴容機制就是當陣列使用率達到他的哈希因子默認是0.75,并當前下標不為空,key值不相等的情況下才會進行擴容
所以假如陣列長度為16的HashMap最大可以存12(一個下標12個)+15(其他下標都為空)=27個
他擴容的為了滿足2的n次方所以就直接擴容兩倍
哈希因子默認是0.75有利于避免hash碰撞提高查找效率,當然也可能會浪費一點空間
值太大,查找慢,值太小空間浪費大
紅黑樹
就算HashMap盡量避免了hash碰撞,但還是難免的
當發生hash碰撞也就是下標一樣,使用要使用陣列加鏈表的方式存盤,直接存放在鏈表里面,
當一個下標的鏈表長度達到8的時候就會變成一個紅黑樹,鏈表太長查找速度慢,這樣有利于提高查詢效率
又當長度降為6的時候紅黑樹又會轉為鏈表,避免總是轉換,有損性能
總結
HashMap的查詢非常快,底層設計的很巧妙,但是HashMap不是執行緒安全的,多執行緒的時候避免使用
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/235433.html
標籤：其他