HashMap的工作原理

哈希表的數(shù)據(jù)結(jié)構(gòu)

HashMap底層數(shù)據(jù)結(jié)構(gòu)是哈希表, 也叫散列表。

哈希表就是一個數(shù)組, 數(shù)組的每個元素是一個單向鏈表。

數(shù)組就是一種順序存儲結(jié)構(gòu), 特點是可以通過數(shù)組的下標(biāo)(索引值)快速的訪問數(shù)組的每個元素, 實現(xiàn)了隨機訪問; 在向數(shù)組中插入元素/刪除元素時, 可能需要擴容,移動/復(fù)制元素,效率比較低。

單向鏈表就是一種鏈?zhǔn)酱鎯Y(jié)構(gòu), 特點插入/刪除時,不需要移動元素,效率比較高;在訪問元素時總是從頭結(jié)點逐個訪問,相對數(shù)組效率比較低。

HashMap的put(key,value)的工作原理

HashMap的get工作原理

JDK8中HashMap的改進

JDK8哈希表中的紅黑樹

HashMap中的哈希碰撞