6月安卓手機性能榜：vivo/iQOO霸占旗艦排行榜前三
2023年上半年已經(jīng)正式過去了，我們也迎來了安兔兔V10版本，在新的驍龍8Gen3和天璣9300發(fā)布之前，性能榜的榜單大體會以驍龍8Gen2和天璣9200+為主，至于那顆3.36GHz的驍龍8Gen2領(lǐng)先
HashMap 是一種散列表，它存儲的內(nèi)容是鍵值對(key-value)映射。在 HashMap 中，每個鍵(key)映射到一個值(value)。散列表的工作原理是：當(dāng)通過 put() 方法將鍵值對存儲在 HashMap 中時，HashMap 首先會根據(jù)鍵的 hashCode 值來計算出存儲位置，然后將鍵值對存儲在該位置上。當(dāng)通過 get() 方法獲取鍵值對時，HashMap 再根據(jù)鍵的 hashCode 值來獲取存儲位置，然后返回該位置上的值。
hash算法的優(yōu)化：對每個hash值，在它的低16位中，讓高低16位進行異或，讓它的低16位同時保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會進入數(shù)組的同一位置。
對尋址算法的優(yōu)化
(p = tab[i = (n - 1) & hash] // (n-1) & hash ==> 數(shù)組里的一個位置hash & (n-1) 效果是跟hash對n取模是一樣的，但是與運算的性能要比hash對n取模要高很多。數(shù)組的長度會一直是2的n次方，只要他保持?jǐn)?shù)組長度是2的n次方。
對于上面尋址算法，由于計算機對比取模，與運算會更快。所以為了效率，HashMap 中規(guī)定了哈希表長度為 2 的 k 次方，而 2^k-1 轉(zhuǎn)為二進制就是 k 個連續(xù)的 1，那么 hash & (k 個連續(xù)的 1) 返回的就是 hash 的低 k 個位，該計算結(jié)果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結(jié)果一樣。
也就是說，哈希表長度 length 為 2 的整次冪時， hash & (length - 1) 的計算結(jié)果跟 hash % length 一樣，而且效率還更好。
int 類型占 32 位，可以表示 2^32 種數(shù)（范圍：-2^31 到 2^31-1），而哈希表長度一般不大，在 HashMap 中哈希表的初始化長度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來尋址，那么相當(dāng)于只有低 4 位有效，其他高位不會有影響。這樣假如幾個 hashCode 分別是 210、220、2^30，那么尋址結(jié)果 index 就會一樣而發(fā)生沖突，所以哈希表就不均勻分布了。
尋址算法的優(yōu)化：用與運算替代取模，提升性能。（由于計算機對比取模，與運算會更快）。
在 JDK1.8 中，HashMap 的結(jié)構(gòu)由數(shù)組和鏈表（或紅黑樹）組成。數(shù)組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。從上圖可以看出，HashMap 由一個個 Node 節(jié)點組成，每個節(jié)點包含了鍵值對的信息，以及指向下一個節(jié)點的指針。HashMap 內(nèi)部維護了一個數(shù)組 table，每個元素都是一個鏈表的頭節(jié)點（或者是一個紅黑樹的根節(jié)點），當(dāng)多個鍵映射到同一個位置時，它們會被存儲在同一個鏈表中（或者是同一個紅黑樹中）。當(dāng)鏈表長度超過閾值（默認(rèn)為 8）時，鏈表就會被轉(zhuǎn)換成紅黑樹（如下圖），這樣可以提高查找效率。如果紅黑樹的節(jié)點數(shù)小于等于6，那么就將紅黑樹轉(zhuǎn)換回鏈表，以節(jié)省空間。
轉(zhuǎn)換紅黑樹
在 JDK1.8 中，HashMap 還引入了一個新的概念，叫做負(fù)載因子(load factor)，它是指哈希表中鍵值對的數(shù)量與數(shù)組長度的比值。當(dāng)鍵值對的數(shù)量超過了負(fù)載因子與數(shù)組長度的乘積時，就會觸發(fā)擴容操作，HashMap 會自動將數(shù)組長度擴大一倍，并將原來的鍵值對重新分配到新的數(shù)組中。這樣做的目的是為了保證散列表的性能，因為當(dāng)負(fù)載因子過高時，散列表的性能會急劇下降。
本文鏈接：http://m.rrqrq.com/showinfo-26-10477-0.htmlHashMap 的基礎(chǔ)結(jié)構(gòu)，必須掌握！
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 別再用 “! = null” 做判空了！
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號