hashmap造成鏈表的原因有哪些

小億
105
2023-12-21 21:04:38

HashMap中的鏈表是由以下原因造成的：

  1. 哈希沖突：當(dāng)不同的鍵映射到相同的哈希桶（bucket）時(shí)，就會(huì)產(chǎn)生哈希沖突。為了解決沖突，HashMap使用鏈表將具有相同哈希值的鍵值對(duì)存儲(chǔ)在同一個(gè)桶中。

  2. 不均勻的哈希函數(shù)：如果哈希函數(shù)不均勻，即無(wú)法將鍵均勻地分布在哈希桶中，就會(huì)導(dǎo)致某些桶中的鍵值對(duì)相對(duì)較多，從而形成鏈表。

  3. 高負(fù)載因子：負(fù)載因子是指哈希表中的鍵值對(duì)數(shù)量與桶的數(shù)量之比。如果負(fù)載因子過(guò)高，即鍵值對(duì)數(shù)量多于桶的數(shù)量，就會(huì)導(dǎo)致桶中的鏈表長(zhǎng)度增加，從而影響HashMap的性能。

  4. 擴(kuò)容：當(dāng)HashMap的負(fù)載因子超過(guò)預(yù)設(shè)閾值時(shí)，就需要進(jìn)行擴(kuò)容操作。在擴(kuò)容過(guò)程中，HashMap會(huì)重新計(jì)算鍵的哈希值，并根據(jù)新的桶數(shù)量將鍵值對(duì)重新分配到不同的桶中，可能會(huì)導(dǎo)致某些桶中的鏈表長(zhǎng)度增加。

需要注意的是，從JDK 8開(kāi)始，HashMap在鏈表長(zhǎng)度達(dá)到一定閾值（默認(rèn)是8）時(shí)，會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù)，以提高查找效率。

0 踩