紅魔電競平板評測：大屏幕硬實力
前言：三年的疫情因為要上網(wǎng)課的原因激活了平板市場，如今網(wǎng)課的時代已經(jīng)過去，大家的生活都恢復到了正軌，這也就意味著，真正考驗平板電腦生存的環(huán)境來了。也就是面對著這種殘酷的
HashMap 由數(shù)組和鏈表（或紅黑樹）組成。數(shù)組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。數(shù)組中的每個元素都是一個單向鏈表的頭結點，每個鏈表都是由若干個 Node 節(jié)點組成的，每個節(jié)點都包含了鍵值對的信息，以及指向下一個節(jié)點的指針。當多個鍵映射到同一個位置時，它們會被存儲在同一個鏈表中（或者是同一個紅黑樹中）。當鏈表長度超過閾值（默認為 8）時，鏈表就會被轉換成紅黑樹，這樣可以提高查找效率。
在 JDK1.8 中，HashMap 還引入了一個新的概念，叫做負載因子(load factor)，它是指哈希表中鍵值對的數(shù)量與數(shù)組長度的比值。當鍵值對的數(shù)量超過了負載因子與數(shù)組長度的乘積時，就會觸發(fā)擴容操作，HashMap 會自動將數(shù)組長度擴大一倍，并將原來的鍵值對重新分配到新的數(shù)組中。這樣做的目的是為了保證散列表的性能，因為當負載因子過高時，散列表的性能會急劇下降。
解答：在jdk1.8以前，HashMa采用鏈表+數(shù)組，自Jdk1.8以后，HashMap采用鏈表+數(shù)組+紅黑樹。在下圖中橫鏈(0-15)表中表示數(shù)組，豎(1-8)表示鏈表，在數(shù)組長度超過8之后，hashmap將數(shù)組自動轉為紅黑樹。
HashMapJDK1.8鏈表和紅黑樹轉化
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }有一個key的Hash_1值：
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100h >>> 16 // 表示對該hash值右移16位右移后的結果Hash_2為：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111對上述Hash_1和Hash_2的兩個值進行異或
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111=====>: 1111 1111 1111 1111 0000 0101 1000 0011 =====> 轉為10進制int值，這個值就是這個key的hash值hash算法的優(yōu)化：對每個hash值，在它的低16位中，讓高低16位進行異或，讓它的低16位同時保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會進入數(shù)組的同一位置。
(p = tab[i = (n - 1) & hash] // (n-1) & hash ==> 數(shù)組里的一個位置hash & (n-1) 效果是跟hash對n取模是一樣的，但是與運算的性能要比hash對n取模要高很多。數(shù)組的長度會一直是2的n次方，只要他保持數(shù)組長度是2的n次方。
對于上面尋址算法，由于計算機對比取模，與運算會更快。所以為了效率，HashMap 中規(guī)定了哈希表長度為 2 的 k 次方，而 2^k-1 轉為二進制就是 k 個連續(xù)的 1，那么 hash & (k 個連續(xù)的 1) 返回的就是 hash 的低 k 個位，該計算結果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結果一樣。
也就是說，哈希表長度 length 為 2 的整次冪時， hash & (length - 1) 的計算結果跟 hash % length 一樣，而且效率還更好。
int 類型占 32 位，可以表示 2^32 種數(shù)（范圍：-2^31 到 2^31-1），而哈希表長度一般不大，在 HashMap 中哈希表的初始化長度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來尋址，那么相當于只有低 4 位有效，其他高位不會有影響。這樣假如幾個 hashCode 分別是 210、220、2^30，那么尋址結果 index 就會一樣而發(fā)生沖突，所以哈希表就不均勻分布了。
尋址算法的優(yōu)化：用與運算替代取模，提升性能。（由于計算機對比取模，與運算會更快）
hash沖突問題，鏈表+紅黑樹，O(n)和O(logN)。
hashmap采用的就是鏈地址法（拉鏈法），jdk1.7中，當沖突時，在沖突的地址上生成一個鏈表，將沖突的元素的key，通過equals進行比較，相同即覆蓋，不同則添加到鏈表上，此時如果鏈表過長，效率就會大大降低，查找和添加操作的時間復雜度都為O(n)；但是在jdk1.8中如果鏈表長度大于8，鏈表就會轉化為紅黑樹，時間復雜度也降為了O(logn)，性能得到了很大的優(yōu)化。
HashMapJDK1.8鏈表和紅黑樹轉化
HashMap底層是一個數(shù)組，當這個數(shù)組滿了之后，他就會自動進行擴容，變成一個更大數(shù)組。
void resize(int newCapacity) { Entry[] oldTable = table; int oldCapacity = oldTable.length; if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } Entry[] newTable = new Entry[newCapacity]; transfer(newTable, initHashSeedAsNeeded(newCapacity)); table = newTable; threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1); }代碼中可以看到，如果原有table長度已經(jīng)達到了上限，就不再擴容了。如果還未達到上限，則創(chuàng)建一個新的table，并調用transfer方法：
/** * Transfers all entries from current table to newTable. */ void transfer(Entry[] newTable, boolean rehash) { int newCapacity = newTable.length; for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; //注釋1 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); //注釋2 e.next = newTable[i]; //注釋3 newTable[i] = e; //注釋4 e = next; //注釋5 } } }transfer方法的作用是把原table的Node放到新的table中，使用的是頭插法，也就是說，新table中鏈表的順序和舊列表中是相反的，在HashMap線程不安全的情況下，這種頭插法可能會導致環(huán)狀節(jié)點。
源碼如下：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // 記錄原來的數(shù)組長度 int oldThr = threshold; int newCap, newThr = 0; if (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold // 重新計算TREEIFY_THRESHOLD } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; @SuppressWarnings({"rawtypes","unchecked"}) Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; table = newTab; if (oldTab != null) { // 重新計算原來鏈表中的值的hash值在新表對應的hash值 for (int j = 0; j < oldCap; ++j) { Node<K,V> e; if ((e = oldTab[j]) != null) { oldTab[j] = null; if (e.next == null) // 如果元素e的下一個位置沒有值，則說明可以存放元素 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 如果已經(jīng)是紅黑樹的節(jié)點，那就對其重新劃分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order // loHead: 下標不變情況下的鏈表頭 // loTail: 下標不變情況下的鏈表尾 // hiHead: 下標改變情況下的鏈表頭 // hiTail: 下標改變情況下的鏈表尾 // 如果 Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,V> next; do { next = e.next; if ((e.hash & oldCap) == 0) { // 元素e的最新hash如果與原來的值與計算之后如果值為0，就說明是使用原來的index // 尾插法插入元素e if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 與運算不等于0則說明使用新的index if (hiTail == null) hiHead = e; else hiTail.next = e; hiTail = e; } } while ((e = next) != null); if (loTail != null) { loTail.next = null; newTab[j] = loHead; } if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; } } } } } return newTab; }正常情況下，計算節(jié)點在table中的下標的方法是：hash&(oldTable.length-1)，擴容之后，table長度翻倍，計算table下標的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我們有了這樣的結論：這新舊兩次計算下標的結果，要不然就相同，要不然就是新下標等于舊下標加上舊數(shù)組的長度。
數(shù)組長度為16時，有兩個keyA和keyB。
KeyA：n-1: 0000 0000 0000 0000 0000 0000 0000 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&結果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5KeyB:n-1: 0000 0000 0000 0000 0000 0000 0000 1111 hash1: 1111 1111 1111 1111 0000 1111 0001 0101&結果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5在數(shù)組長度為16的時候，他們兩個hash值沖突會使用拉鏈發(fā)解決沖突。
當數(shù)組長度擴容到32之后，需要重新對每個hash值進行尋址，也就是每個hash值跟新的數(shù)組length-1 進行操作。
KeyA：n-1: 0000 0000 0000 0000 0000 0000 000*1* 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&結果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5KeyB:n-1: 0000 0000 0000 0000 0000 000*1* 0000 1111 hash1: 1111 1111 1111 1111 0000 1111 0001 0101&結果: 0000 0000 0000 0000 0000 000*1* 0000 0101 = 21判斷二進制結果是否多出一個bit的1，如果沒有多，那就用原來的index，如果多出來了那就用index+oldCap，通過這個方式，避免了rehash的時候，用每個hash對新數(shù)組的length取模，取模性能不高，位運算性能比較高。
本文鏈接：http://www.tebozhan.com/showinfo-26-10459-0.html深度！HashMap的底層數(shù)據(jù)結構
聲明：本網(wǎng)頁內容旨在傳播知識，若有侵權等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
Copyright ? 2016-2023 天津谷騏科技有限公司 版權所有 sitemap.xml
違法及侵權請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號