根據(jù) Java7 HashMap 的介紹,我們知道,查找的時(shí)候,根據(jù) hash 值我們能夠快速定位到數(shù)組的具體下標(biāo),但是之后的話,需要順著鏈表一個(gè)個(gè)比較下去才能找到我們需要的,時(shí)間復(fù)雜度取決于鏈表的長(zhǎng)度,為 O(n)。
為了降低這部分的開(kāi)銷(xiāo),在 Java8 中,當(dāng)鏈表中的元素達(dá)到了 8 個(gè)時(shí),會(huì)將鏈表轉(zhuǎn)換為紅黑樹(shù),在這些位置進(jìn)行查找的時(shí)候可以降低時(shí)間復(fù)雜度為 O(logN)。