已解決430363個問題，去搜搜看，總會有你想問的

求大佬指點哈！HashMap2倍擴容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴容了啊萬分感謝

首頁猿問求大佬指點哈！HashMap2倍擴...

求大佬指點哈！HashMap2倍擴容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴容了啊萬分感謝

JavaScript

精慕HU 2019-10-25 20:50:47

問題描述HashMap一定2倍擴容,因為存儲位置由(length-1)&hash(key)確定,如果用hash(key)%length確定存儲,不就不用必須2倍擴容了嗎?可以隨意擴容,為什么不采用?是因為hash(key)%length性能較(length-1)&hash(key)低?

查看完整描述

2 回答

慕容森

TA貢獻1853條經驗獲得超18個贊

按位和運算比求余運算快是一方面，還有很重要的一點就是這種擴容方式下對元素的重新分配操作更簡單，尤其是在碰撞較多的情況下。原先在oldTab[i]位置的元素在resize后要么在newTab[i]，要么在newTab[i+oldCap],而且只有oldTab[i]上的元素會被分配到這兩個位置對節點鏈表oldTab[i]做rehash時，只需要根據hash&oldCap是否等于0拆分成low、high兩個鏈表，然后直接賦值newTab[i]=low,newTab[i+oldCap]=high即可。如果是隨意擴容，rehash時就需要對每個元素做如下操作：算出在新數組中的位置j檢查newTab[j]是否為空，如果為空則賦值到newTab[j]，否則用一個循環結構找到newTab[j]鏈表的末尾，將元素添加到鏈表末尾。*oldCap為擴容前數組大小*從java8開始,碰撞的元素還可能是以樹的形式存儲，處理方式略有差異

反對回復 2019-10-25

2 回答
0 關注
366 瀏覽

關注

添加回答

舉報

0/150

提交

取消

亚洲在线久爱草,狠狠天天香蕉网,天天搞日日干久草,伊人亚洲日本欧美

熱搜

最近搜索清空

求大佬指點哈！HashMap2倍擴容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴容了啊萬分感謝

求大佬指點哈！HashMap2倍擴容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴容了啊萬分感謝

2 回答

添加回答

求大佬指點哈！HashMap2倍擴容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴容了啊萬分感謝

求大佬指點哈！HashMap2倍擴容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴容了啊萬分感謝