首頁(yè) 猿問跪求！HashMap2倍擴(kuò)容,為什...

跪求！HashMap2倍擴(kuò)容,為什么不用hash(key)%length存儲(chǔ),這樣就不用必須2倍擴(kuò)容了啊求大佬指點(diǎn)！

JavaScript

蕪湖不蕪 2019-10-16 09:09:20

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

查看完整描述

2 回答

慕田峪4524236

TA貢獻(xiàn)1875條經(jīng)驗(yàn) 獲得超5個(gè)贊

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