首頁猿問 HashMap2倍擴容,為什么不用...

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

Java

慕運維8079593 2019-12-11 13:09:29

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

查看完整描述

2 回答

拉莫斯之舞

TA貢獻1820條經驗獲得超10個贊

按位和運算比求余運算快是一方面，還有很重要的一點就是這種擴容方式下對元素的重新分配操作更簡單，尤其是在碰撞較多的情況下。原先在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即可。如果是隨意擴容，rehash時就需要對每個元素做如下操作：算出在新數(shù)組中的位置j檢查newTab[j]是否為空，如果為空則賦值到newTab[j]，否則用一個循環(huán)結構找到newTab[j]鏈表的末尾，將元素添加到鏈表末尾。*oldCap為擴容前數(shù)組大小*從java8開始,碰撞的元素還可能是以樹的形式存儲，處理方式略有差異

反對回復 2019-12-12