hashmap的性能問(wèn)題本質(zhì)就是數(shù)組,鏈表,紅黑樹(shù)的問(wèn)題
貼一篇CSDN的文章 對(duì)hashmap的結(jié)構(gòu)講的很簡(jiǎn)單易懂
https://blog.csdn.net/Jae_Peng/article/details/79562432
為什么要用hashmap呢(hashmap的優(yōu)點(diǎn))
假設(shè)分布足夠均勻,沒(méi)有發(fā)生hash碰撞,那就是一個(gè)Node數(shù)組(Node實(shí)現(xiàn)了map.Entry接口 實(shí)際就是鍵值對(duì)數(shù)組 默認(rèn)初始長(zhǎng)度16 空位置為null)
所以查詢數(shù)據(jù)的時(shí)間復(fù)雜度位O(1);
而插入數(shù)據(jù)的時(shí)候通過(guò)hash算法計(jì)算插入位置,然后替換數(shù)組中null位,
(hash算法時(shí)間復(fù)雜度O(1));
綜上 插入查詢都為O(1), 保留了數(shù)組的優(yōu)點(diǎn);
但如果發(fā)生了hash碰撞(hashcode相同)呢?
重復(fù)位會(huì)調(diào)用equals方法(時(shí)間復(fù)雜度O(n)),比較key是否一樣,如果不一樣,則放入單鏈表中,而此時(shí)hashmap查詢的最壞時(shí)間復(fù)雜度也變?yōu)镺(n)
當(dāng)同一個(gè)位置發(fā)生的哈希碰撞越來(lái)越多,鏈表長(zhǎng)度就越來(lái)越長(zhǎng),在jdk1.8之后,鏈表長(zhǎng)度如果>=8,就會(huì)轉(zhuǎn)變成紅黑樹(shù),優(yōu)化插入查詢操作(RB TREE 一種平衡查詢二叉樹(shù) 通過(guò)二分查找 查詢的時(shí)間復(fù)雜度均為O(logn) 而紅黑樹(shù)通過(guò)左旋右旋變色等操作 可以做到自我平衡 能保證時(shí)間復(fù)雜度不變);
hashmap的缺點(diǎn):
hashmap的resize()操作會(huì)對(duì)hashmap進(jìn)行擴(kuò)容操作,擴(kuò)容長(zhǎng)度為原來(lái)的兩倍,而resize會(huì)對(duì)所有原來(lái)的元素重新計(jì)算hash值,很浪費(fèi)性能,如果在多線程環(huán)境下,還會(huì)出現(xiàn)死鎖的問(wèn)題.
決定是否擴(kuò)容取決于負(fù)載因子和元素?cái)?shù)量之積是否大于數(shù)組長(zhǎng)度,默認(rèn)負(fù)載因子為0.75,要避免頻繁擴(kuò)容 在new hashmap時(shí)就能更具情況給定適合的長(zhǎng)度,或者增大負(fù)載因子的值,但負(fù)載因子的值越大,同樣數(shù)組長(zhǎng)度中就有更多的元素,更容易發(fā)生哈希碰撞,插入和查詢的性能就會(huì)下降.
紅黑樹(shù)左旋 右旋 變色
每次插入數(shù)據(jù) 紅黑樹(shù)會(huì)根據(jù)hashcode大小放在左右2邊,如果破壞了紅黑樹(shù)的5條規(guī)則,紅黑樹(shù)就會(huì)自平衡,不管怎么變,都遵循的2條原則:
根節(jié)點(diǎn)是中值 樹(shù)的中序遍歷順序不變
紅黑樹(shù)的5條原則也是為了保證二分查找的性能
