官方承諾：K60至尊版將會首批升級MIUI 15
全新的MIUI 15今天也有了消息，在官宣了K60至尊版將會搭載天璣9200+處理器和獨顯芯片X7的同時，Redmi給出了官方承諾，K60至尊重大更新首批升級，會首批推送MIUI 15。也就是說雖然
HashMap 是一種散列表，它存儲的內容是鍵值對(key-value)映射。在 HashMap 中，每個鍵(key)映射到一個值(value)。散列表的工作原理是：當通過 put() 方法將鍵值對存儲在 HashMap 中時，HashMap 首先會根據鍵的 hashCode 值來計算出存儲位置，然后將鍵值對存儲在該位置上。當通過 get() 方法獲取鍵值對時，HashMap 再根據鍵的 hashCode 值來獲取存儲位置，然后返回該位置上的值。
hash算法的優化：對每個hash值，在它的低16位中，讓高低16位進行異或，讓它的低16位同時保持了高低16位的特征，盡量避免一些hash值后續出現沖突，大家可能會進入數組的同一位置。
對尋址算法的優化
(p = tab[i = (n - 1) & hash] // (n-1) & hash ==> 數組里的一個位置hash & (n-1) 效果是跟hash對n取模是一樣的，但是與運算的性能要比hash對n取模要高很多。數組的長度會一直是2的n次方，只要他保持數組長度是2的n次方。
對于上面尋址算法，由于計算機對比取模，與運算會更快。所以為了效率，HashMap 中規定了哈希表長度為 2 的 k 次方，而 2^k-1 轉為二進制就是 k 個連續的 1，那么 hash & (k 個連續的 1) 返回的就是 hash 的低 k 個位，該計算結果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結果一樣。
也就是說，哈希表長度 length 為 2 的整次冪時， hash & (length - 1) 的計算結果跟 hash % length 一樣，而且效率還更好。
int 類型占 32 位，可以表示 2^32 種數（范圍：-2^31 到 2^31-1），而哈希表長度一般不大，在 HashMap 中哈希表的初始化長度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來尋址，那么相當于只有低 4 位有效，其他高位不會有影響。這樣假如幾個 hashCode 分別是 210、220、2^30，那么尋址結果 index 就會一樣而發生沖突，所以哈希表就不均勻分布了。
尋址算法的優化：用與運算替代取模，提升性能。（由于計算機對比取模，與運算會更快）。
在 JDK1.8 中，HashMap 的結構由數組和鏈表（或紅黑樹）組成。數組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。從上圖可以看出，HashMap 由一個個 Node 節點組成，每個節點包含了鍵值對的信息，以及指向下一個節點的指針。HashMap 內部維護了一個數組 table，每個元素都是一個鏈表的頭節點（或者是一個紅黑樹的根節點），當多個鍵映射到同一個位置時，它們會被存儲在同一個鏈表中（或者是同一個紅黑樹中）。當鏈表長度超過閾值（默認為 8）時，鏈表就會被轉換成紅黑樹（如下圖），這樣可以提高查找效率。如果紅黑樹的節點數小于等于6，那么就將紅黑樹轉換回鏈表，以節省空間。
轉換紅黑樹
在 JDK1.8 中，HashMap 還引入了一個新的概念，叫做負載因子(load factor)，它是指哈希表中鍵值對的數量與數組長度的比值。當鍵值對的數量超過了負載因子與數組長度的乘積時，就會觸發擴容操作，HashMap 會自動將數組長度擴大一倍，并將原來的鍵值對重新分配到新的數組中。這樣做的目的是為了保證散列表的性能，因為當負載因子過高時，散列表的性能會急劇下降。
本文鏈接：http://www.www897cc.com/showinfo-26-10477-0.htmlHashMap 的基礎結構，必須掌握！
聲明：本網頁內容旨在傳播知識，若有侵權等問題請及時與本網聯系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 別再用 “! = null” 做判空了！
下一篇： 游戲引擎項目 Godot 成立開發基金
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯系：2376512515@qq.com 津ICP備18001702號
津公網安備 12010102000574號