首頁猿問 HashMap2倍擴(kuò)容,為什么不用...

HashMap2倍擴(kuò)容,為什么不用hash(key)%length存儲,這樣就不用必須2倍擴(kuò)容了啊求解答！

JavaScript

哆啦的時光機(jī) 2019-11-03 10:22:37

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

查看完整描述

2 回答

汪汪一只貓

TA貢獻(xiàn)1898條經(jīng)驗獲得超8個贊

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