JVM優(yōu)化：實(shí)戰(zhàn)OutOfMemoryError異常
一、Java堆溢出堆內(nèi)存中主要存放對(duì)象、數(shù)組等，只要不斷地創(chuàng)建這些對(duì)象，并且保證 GC Roots 到對(duì)象之間有可達(dá)路徑來(lái)避免垃 圾收集回收機(jī)制清除這些對(duì)象，當(dāng)這些對(duì)象所占空間超過(guò)
HashMap 由數(shù)組和鏈表（或紅黑樹）組成。數(shù)組是 HashMap 的主體，鏈表和紅黑樹則是為了解決哈希沖突而存在的。數(shù)組中的每個(gè)元素都是一個(gè)單向鏈表的頭結(jié)點(diǎn)，每個(gè)鏈表都是由若干個(gè) Node 節(jié)點(diǎn)組成的，每個(gè)節(jié)點(diǎn)都包含了鍵值對(duì)的信息，以及指向下一個(gè)節(jié)點(diǎn)的指針。當(dāng)多個(gè)鍵映射到同一個(gè)位置時(shí)，它們會(huì)被存儲(chǔ)在同一個(gè)鏈表中（或者是同一個(gè)紅黑樹中）。當(dāng)鏈表長(zhǎng)度超過(guò)閾值（默認(rèn)為 8）時(shí)，鏈表就會(huì)被轉(zhuǎn)換成紅黑樹，這樣可以提高查找效率。
在 JDK1.8 中，HashMap 還引入了一個(gè)新的概念，叫做負(fù)載因子(load factor)，它是指哈希表中鍵值對(duì)的數(shù)量與數(shù)組長(zhǎng)度的比值。當(dāng)鍵值對(duì)的數(shù)量超過(guò)了負(fù)載因子與數(shù)組長(zhǎng)度的乘積時(shí)，就會(huì)觸發(fā)擴(kuò)容操作，HashMap 會(huì)自動(dòng)將數(shù)組長(zhǎng)度擴(kuò)大一倍，并將原來(lái)的鍵值對(duì)重新分配到新的數(shù)組中。這樣做的目的是為了保證散列表的性能，因?yàn)楫?dāng)負(fù)載因子過(guò)高時(shí)，散列表的性能會(huì)急劇下降。
解答：在jdk1.8以前，HashMa采用鏈表+數(shù)組，自Jdk1.8以后，HashMap采用鏈表+數(shù)組+紅黑樹。在下圖中橫鏈(0-15)表中表示數(shù)組，豎(1-8)表示鏈表，在數(shù)組長(zhǎng)度超過(guò)8之后，hashmap將數(shù)組自動(dòng)轉(zhuǎn)為紅黑樹。
HashMapJDK1.8鏈表和紅黑樹轉(zhuǎn)化
static final int hash(Object key) { int h; return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16); }有一個(gè)key的Hash_1值：
Hash_1: 1111 1111 1111 1111 1111 1010 0111 1100h >>> 16 // 表示對(duì)該hash值右移16位右移后的結(jié)果Hash_2為：
Hash_2: 0000 0000 0000 0000 1111 1111 1111 1111對(duì)上述Hash_1和Hash_2的兩個(gè)值進(jìn)行異或
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 =====> 轉(zhuǎn)為10進(jìn)制int值，這個(gè)值就是這個(gè)key的hash值hash算法的優(yōu)化：對(duì)每個(gè)hash值，在它的低16位中，讓高低16位進(jìn)行異或，讓它的低16位同時(shí)保持了高低16位的特征，盡量避免一些hash值后續(xù)出現(xiàn)沖突，大家可能會(huì)進(jìn)入數(shù)組的同一位置。
(p = tab[i = (n - 1) & hash] // (n-1) & hash ==> 數(shù)組里的一個(gè)位置hash & (n-1) 效果是跟hash對(duì)n取模是一樣的，但是與運(yùn)算的性能要比hash對(duì)n取模要高很多。數(shù)組的長(zhǎng)度會(huì)一直是2的n次方，只要他保持?jǐn)?shù)組長(zhǎng)度是2的n次方。
對(duì)于上面尋址算法，由于計(jì)算機(jī)對(duì)比取模，與運(yùn)算會(huì)更快。所以為了效率，HashMap 中規(guī)定了哈希表長(zhǎng)度為 2 的 k 次方，而 2^k-1 轉(zhuǎn)為二進(jìn)制就是 k 個(gè)連續(xù)的 1，那么 hash & (k 個(gè)連續(xù)的 1) 返回的就是 hash 的低 k 個(gè)位，該計(jì)算結(jié)果范圍剛好就是 0 到 2^k-1，即 0 到 length - 1，跟取模結(jié)果一樣。
也就是說(shuō)，哈希表長(zhǎng)度 length 為 2 的整次冪時(shí)， hash & (length - 1) 的計(jì)算結(jié)果跟 hash % length 一樣，而且效率還更好。
int 類型占 32 位，可以表示 2^32 種數(shù)（范圍：-2^31 到 2^31-1），而哈希表長(zhǎng)度一般不大，在 HashMap 中哈希表的初始化長(zhǎng)度是 16（HashMap 中的 DEFAULT_INITIAL_CAPACITY），如果直接用 hashCode 來(lái)尋址，那么相當(dāng)于只有低 4 位有效，其他高位不會(huì)有影響。這樣假如幾個(gè) hashCode 分別是 210、220、2^30，那么尋址結(jié)果 index 就會(huì)一樣而發(fā)生沖突，所以哈希表就不均勻分布了。
尋址算法的優(yōu)化：用與運(yùn)算替代取模，提升性能。（由于計(jì)算機(jī)對(duì)比取模，與運(yùn)算會(huì)更快）
hash沖突問(wèn)題，鏈表+紅黑樹，O(n)和O(logN)。
hashmap采用的就是鏈地址法（拉鏈法），jdk1.7中，當(dāng)沖突時(shí)，在沖突的地址上生成一個(gè)鏈表，將沖突的元素的key，通過(guò)equals進(jìn)行比較，相同即覆蓋，不同則添加到鏈表上，此時(shí)如果鏈表過(guò)長(zhǎng)，效率就會(huì)大大降低，查找和添加操作的時(shí)間復(fù)雜度都為O(n)；但是在jdk1.8中如果鏈表長(zhǎng)度大于8，鏈表就會(huì)轉(zhuǎn)化為紅黑樹，時(shí)間復(fù)雜度也降為了O(logn)，性能得到了很大的優(yōu)化。
HashMapJDK1.8鏈表和紅黑樹轉(zhuǎn)化
HashMap底層是一個(gè)數(shù)組，當(dāng)這個(gè)數(shù)組滿了之后，他就會(huì)自動(dòng)進(jìn)行擴(kuò)容，變成一個(gè)更大數(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長(zhǎng)度已經(jīng)達(dá)到了上限，就不再擴(kuò)容了。如果還未達(dá)到上限，則創(chuàng)建一個(gè)新的table，并調(diào)用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中，使用的是頭插法，也就是說(shuō)，新table中鏈表的順序和舊列表中是相反的，在HashMap線程不安全的情況下，這種頭插法可能會(huì)導(dǎo)致環(huán)狀節(jié)點(diǎn)。
源碼如下：
final Node<K,V>[] resize() { Node<K,V>[] oldTab = table; int oldCap = (oldTab == null) ? 0 : oldTab.length; // 記錄原來(lái)的數(shù)組長(zhǎng)度 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 // 重新計(jì)算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) { // 重新計(jì)算原來(lái)鏈表中的值的hash值在新表對(duì)應(yīng)的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的下一個(gè)位置沒有值，則說(shuō)明可以存放元素 newTab[e.hash & (newCap - 1)] = e; else if (e instanceof TreeNode) // 如果已經(jīng)是紅黑樹的節(jié)點(diǎn)，那就對(duì)其重新劃分 ((TreeNode<K,V>)e).split(this, newTab, j, oldCap); else { // preserve order // loHead: 下標(biāo)不變情況下的鏈表頭 // loTail: 下標(biāo)不變情況下的鏈表尾 // hiHead: 下標(biāo)改變情況下的鏈表頭 // hiTail: 下標(biāo)改變情況下的鏈表尾 // 如果 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如果與原來(lái)的值與計(jì)算之后如果值為0，就說(shuō)明是使用原來(lái)的index // 尾插法插入元素e if (loTail == null) loHead = e; else loTail.next = e; loTail = e; } else { // 與運(yùn)算不等于0則說(shuō)明使用新的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; }正常情況下，計(jì)算節(jié)點(diǎn)在table中的下標(biāo)的方法是：hash&(oldTable.length-1)，擴(kuò)容之后，table長(zhǎng)度翻倍，計(jì)算table下標(biāo)的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我們有了這樣的結(jié)論：這新舊兩次計(jì)算下標(biāo)的結(jié)果，要不然就相同，要不然就是新下標(biāo)等于舊下標(biāo)加上舊數(shù)組的長(zhǎng)度。
數(shù)組長(zhǎng)度為16時(shí)，有兩個(gè)keyA和keyB。
KeyA：n-1: 0000 0000 0000 0000 0000 0000 0000 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&結(jié)果: 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&結(jié)果: 0000 0000 0000 0000 0000 0000 0000 0101 = 5在數(shù)組長(zhǎng)度為16的時(shí)候，他們兩個(gè)hash值沖突會(huì)使用拉鏈發(fā)解決沖突。
當(dāng)數(shù)組長(zhǎng)度擴(kuò)容到32之后，需要重新對(duì)每個(gè)hash值進(jìn)行尋址，也就是每個(gè)hash值跟新的數(shù)組length-1 進(jìn)行操作。
KeyA：n-1: 0000 0000 0000 0000 0000 0000 000*1* 1111hash1: 1111 1111 1111 1111 0000 1111 0000 0101&結(jié)果: 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&結(jié)果: 0000 0000 0000 0000 0000 000*1* 0000 0101 = 21判斷二進(jìn)制結(jié)果是否多出一個(gè)bit的1，如果沒有多，那就用原來(lái)的index，如果多出來(lái)了那就用index+oldCap，通過(guò)這個(gè)方式，避免了rehash的時(shí)候，用每個(gè)hash對(duì)新數(shù)組的length取模，取模性能不高，位運(yùn)算性能比較高。
本文鏈接：http://m.rrqrq.com/showinfo-26-10459-0.html深度！HashMap的底層數(shù)據(jù)結(jié)構(gòu)
聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com
上一篇： Spring Cloud Gateway提供的簡(jiǎn)易網(wǎng)關(guān)實(shí)現(xiàn)方式，你使用過(guò)嗎？
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請(qǐng)聯(lián)系：2376512515@qq.com 津ICP備18001702號(hào)
津公網(wǎng)安備 12010102000574號(hào)