一加Ace2 Pro真機揭曉 鈦空灰配色質(zhì)感拉滿
終于，在經(jīng)過了幾波預(yù)熱之后，一加Ace2 Pro的外觀真機圖在網(wǎng)上出現(xiàn)了。還是博主數(shù)碼閑聊站曝光的，這次的外觀設(shè)計還是延續(xù)了一加11的方案，只是細(xì)節(jié)上有了調(diào)整，例如新加入了鈦空灰
hashMap在java1.7和java1.8版本中有做一些調(diào)整，我們本篇只說java1.7的hashMap。
hashMap的數(shù)據(jù)結(jié)構(gòu)是由數(shù)組和鏈表組成，table是一個存放Entry對象的數(shù)組，每個Entry對象由4個屬性組成，分別是key、value、next、hash，key和value是我們熟知的鍵值對，不需要過多解釋，next是當(dāng)前元素在鏈表中指向下一個元素的引用，hash是計算出來的hashcode，hashMap中的hsah是通過對key.hashcode()進行一定操作得出的，并不是直接使用key.hashcode()方法計算數(shù)來的值。
先來了解下hashMap中一些重要的屬性：
//Hashmap的初始化大小，初始化的值為16,1往右移4位為16static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; //HashMap是動態(tài)擴容的，就是容量大小不能大于 1<<30static final int MAXIMUM_CAPACITY = 1 << 30;//默認(rèn)的擴容因子，這個值可以通過構(gòu)造修改static final float DEFAULT_LOAD_FACTOR = 0.75f;//空數(shù)據(jù)，默認(rèn)構(gòu)造的時候賦值為空的Entry數(shù)組，在添加元素的時候//會判斷table=EMPTY_TABLE ，然后就擴容static final Entry<?,?>[] EMPTY_TABLE = {};//表示一個空的Hashmaptransient Entry<K,V>[] table = (Entry<K,V>[]) EMPTY_TABLE;//Hashmap的大小transient int size;//threshold表示當(dāng)HashMap的size大于threshold時會執(zhí)行resize操作。DEFAULT_INITIAL_CAPACITY=16//擴容的閾值int threshold;//擴容因子，沒有傳入就使用默認(rèn)的DEFAULT_LOAD_FACTOR = 0.75ffinal float loadFactor;//數(shù)據(jù)操作次數(shù)，用于迭代檢查修改異常transient int modCount;static final int ALTERNATIVE_HASHING_THRESHOLD_DEFAULT = Integer.MAX_VALUE;步驟：
接下來我們對每一步驟分別展開討論。
private void inflateTable(int toSize) { // 找到大于等于指定數(shù)組長度的2的n次方 int capacity = roundUpToPowerOf2(toSize); // 擴容閾值，數(shù)組長度*負(fù)載因子 threshold = (int) Math.min(capacity * loadFactor, MAXIMUM_CAPACITY + 1); // 創(chuàng)建數(shù)組 table = new Entry[capacity]; // 是否重新賦值hashSeed initHashSeedAsNeeded(capacity);}private static int roundUpToPowerOf2(int number) { // 使用Integer的highestOneBit方法找到大于等于指定數(shù)組長度的2的n次方 return number >= MAXIMUM_CAPACITY ? MAXIMUM_CAPACITY : (number > 1) ? Integer.highestOneBit((number - 1) << 1) : 1;}數(shù)組初始化其實就三個步驟：計算數(shù)組容量，創(chuàng)建數(shù)組，判斷是否重hash。
(1)「數(shù)組容量」： 如果指定數(shù)組長度值大于MAXIMUM_CAPACITY(最大數(shù)組容量:2的30次方)，就用最大值;如果指定數(shù)組長度值小于等于1，就用1；如果指定數(shù)組長度值大于1，就用下面的方法得到大于等于指定數(shù)組長度的第一個2的n次方的值。
Integer.highestOneBit((number - 1) << 1)public static int highestOneBit(int i) { // HD, Figure 3-1 i |= (i >> 1); i |= (i >> 2); i |= (i >> 4); i |= (i >> 8); i |= (i >> 16); return i - (i >>> 1); }這個方法內(nèi)部是通過位移和亦或操作得到的值，感興趣的可以直接看下源碼。
(2) 「創(chuàng)建數(shù)組」：直接用計算出來的數(shù)組長度創(chuàng)建Entry數(shù)組table，元素類型為Entry。
(3) 「判斷是否重hash」：
重hash就是對同個key重新計算hash值，那么為什么要重新計算hash值，實際上只是為了讓hsah值更復(fù)雜，在計算下標(biāo)的時候就會更加散列,減少hash沖突。
那么什么樣的條件下才會重hash呢，從源碼可以看出switching為true表示需要重hash，影響switching取值的是下面這段代碼：
final boolean initHashSeedAsNeeded(int capacity) { // hashSeed 初始值為0，false boolean currentAltHashing = hashSeed != 0; // 數(shù)組長度是否 >= 2^31-1 boolean useAltHashing = sun.misc.VM.isBooted() && (capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD); // 使用異或，currentAltHashing 為false，只有數(shù)組長度>= 2^31-1時返回true boolean switching = currentAltHashing ^ useAltHashing; //switching為true，則hashSeed重新賦值（一般不會出現(xiàn)） if (switching) { hashSeed = useAltHashing ? sun.misc.Hashing.randomHashSeed(this) : 0; } return switching;}initHashSeedAsNeeded方法用來判斷是否進行重hash，如果需要重hash，會同步更新hash種子，最后返回boolean類型的值。
Holder.ALTERNATIVE_HASHING_THRESHOLD取的是環(huán)境變量jdk.map.althashing.threshold配置的值(程序員配置)，如果沒有配置就默認(rèn)取Integer.MAX_VALUE。
通過上面的分析可以知道是否進行重hash只會受到capacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD的影響。
「我們可以得出一個結(jié)論：」如果程序員不配置環(huán)境變量jdk.map.althashing.threshold，那么就永遠(yuǎn)不會進行重hash，因為數(shù)組長度capacity最大是2的30次方，而Integer.MAX_VALUE的值是2的31次方減1，即這個條件永遠(yuǎn)不會滿足，但是你可能會說擴容的時候傳入的capacity正好是最大值2的30次方的2倍，但是我會告訴你，如果數(shù)組成都達(dá)到2的30次方，是不允許擴容的。
所以說如果程序員不設(shè)置環(huán)境變量，initHashSeedAsNeeded方法實際上沒有意義的。
那為什么要更新hash種子呢？
這就要了解下hsah值是怎么生成的了：
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}hashMap的hsah值是由key調(diào)用自身的hashCode方法得到的值與hashSeed進行5次亦或操作4次位移運算得到的。
所以相同的key只有在hashSeed變化后才有生成不同的hash值，否則生成的永遠(yuǎn)是相同的hsah值，所以需要重hash的時候就必須改變hashSeed，否則重hash的結(jié)果會和原來一樣。
private V putForNullKey(V value) { // 當(dāng)key為null時，數(shù)組下標(biāo)指定為0 for (Entry<K,V> e = table[0]; e != null; e = e.next) { // 判斷現(xiàn)在有沒有key為null的Entry if (e.key == null) { //value替換為新值，返回舊的value V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } //修改次數(shù)+1 modCount++; // table[0]中沒有值或沒有匹配到null的key，創(chuàng)建一個Entry放入table[0] addEntry(0, null, value, 0); return null;}上面這段代碼是對key為null的情況的處理，同時也說明hashmap是允許key為null的，通過上面可以看出hashMap中key為null的元素只會存儲在數(shù)組下標(biāo)為0的桶中，如果桶中有多個，就遍歷鏈表找到key為null的元素進行覆蓋更新，如果桶中無元素，就調(diào)用addEntry方法插入元素，這里只需要知道調(diào)用addEntry方法的結(jié)果是將數(shù)據(jù)插入數(shù)組下標(biāo)為0的桶中，addEntry方法我們下面再具體看。
// 獲取key的hash值 int hash = hash(key); // 根據(jù)hash值和數(shù)組長度計算要放入的數(shù)組下標(biāo)位置 int i = indexFor(hash, table.length);計算下標(biāo)實際上分為兩步，計算hsah值和計算下標(biāo)，計算下標(biāo)的原理是用hash值除以數(shù)組容量，得到的余數(shù)就是下標(biāo)，用這種方式可以保證不同的key一定會放在數(shù)組中的某個桶中，不會越界，而hash值可以讓不同的key在數(shù)組中的分部足夠分散，減少hsah沖突。
final int hash(Object k) { int h = hashSeed; if (0 != h && k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^= k.hashCode(); h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4);}上面已將說過hash方法，這里再來說一次，我們知道java中每個類都默認(rèn)由hashcode方法生成hashcode，但是hashMap中并沒有直接用此方法生成的hashcode，而是對其生成的hahshcode與hash種子進行亦或和位移操作，1.7的hashMap在計算hsah的時候進行了5次亦或操作和4次位移運算，這樣做的目的就是使得不同的key計算出來的hash更加分散，更加能減少hash沖突。
static int indexFor(int h, int length) { // 計算數(shù)組下標(biāo)位置，數(shù)組長度必須為2的n次方 return h & (length-1);}我們上面說了hash除以數(shù)組容量得到數(shù)組下標(biāo)，但是這種做法在java中太慢了，而和此做法同效的一種方式就是h & (length-1)，就是數(shù)組容量減去1，再與hash做&操作。這種方式在java中是非常高效的。
運行到這里，數(shù)組已經(jīng)有了，key對應(yīng)的下標(biāo)也有了，接下來就是插入操作，插入之前會先查看下標(biāo)對應(yīng)的桶中是否為空桶，如果不為空桶就要先遍歷查找是否有相同key。
for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 判斷key的值是否相等 if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { // key的值相等則寫入新的value值，將舊value返回 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 修改次數(shù)+1 modCount++; // 下標(biāo)位置為空或沒有能夠匹配的key值，創(chuàng)建Entry放入鏈表 addEntry(hash, key, value, i);因為hashMap是由數(shù)組和鏈表組成，數(shù)組的每個桶中都由鏈表組成，所以需要遍歷鏈表查找相同的key，如果存在相同的key就更新覆蓋，如果沒有，就調(diào)用addEntry方法進行插入。
//addEntry方法void addEntry(int hash, K key, V value, int bucketIndex) { // 如果當(dāng)前數(shù)組長度>=擴容閾值 并且 當(dāng)前數(shù)組下標(biāo)位置不為null if ((size >= threshold) && (null != table[bucketIndex])) { // 數(shù)組擴容為當(dāng)前長度*2 resize(2 * table.length); // key是否為null，不為null計算hash值，null則直接hash值為0 hash = (null != key) ? hash(key) : 0; // 根據(jù)hash值和新數(shù)組長度計算下標(biāo)位置 bucketIndex = indexFor(hash, table.length); } //創(chuàng)建Entry放入table中 createEntry(hash, key, value, bucketIndex);}可以看到在正式添加元素之前會先判斷是否需要擴容，如果需要則先進行擴容。
從上面的源碼可以知道擴容需要滿足兩個條件：
如果滿足條件則進入resize方法進行擴容：
void resize(int newCapacity) { // 原數(shù)組 Entry[] oldTable = table; // 原數(shù)組長度 int oldCapacity = oldTable.length; // 如果原數(shù)組長度為2^30，不進行擴容，把擴容閾值修改為2^31-1 if (oldCapacity == MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return; } // 根據(jù)新的數(shù)組長度，創(chuàng)建數(shù)組 Entry[] newTable = new Entry[newCapacity]; // 轉(zhuǎn)移數(shù)組數(shù)據(jù) // 調(diào)用initHashSeedAsNeeded方法，根據(jù)新數(shù)組的長度判斷是否會hashSeed重新賦值 transfer(newTable, initHashSeedAsNeeded(newCapacity)); // table指向新數(shù)組 table = newTable; // 計算新的擴容閾值 threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);}// transfer方法void transfer(Entry[] newTable, boolean rehash) { // 新數(shù)組長度 int newCapacity = newTable.length; // 遍歷原數(shù)組的Entry for (Entry<K,V> e : table) { // Entry不為null while(null != e) { // 先找到鏈表中下一個要轉(zhuǎn)移的Entry Entry<K,V> next = e.next; // 如果hashSeed變了，重新進行hash計算 if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } // 重新計算數(shù)組下標(biāo)，結(jié)果分兩種：1.與原下標(biāo)一直 2.原下標(biāo)+本次擴容了多長 int i = indexFor(e.hash, newCapacity); /*原數(shù)組統(tǒng)一鏈表中的數(shù)據(jù)轉(zhuǎn)移到新數(shù)組中時，所處鏈表順序顛倒，因此多線程的情況下可能會出現(xiàn)環(huán)形鏈表問題*/ // Entry的next指向新數(shù)組的鏈表頭 e.next = newTable[i]; // Entry放入新數(shù)組的鏈表中 newTable[i] = e; // 下一次進行操作的就是原數(shù)組鏈表的下一個 e = next; } }}擴容步驟：
transfer方法進行具體的擴容處理：
實際上就是遍歷舊數(shù)組，從舊數(shù)組的第一個桶中拿到鏈表，從鏈表頭部開始遍歷，一個一個的取出計算新的下標(biāo)(如果需要重hash就會用新的hsah種子計算hsah值，如果不需要重hash就用原來的hsah值，最終用hsah值和新數(shù)組容量計算下標(biāo))，然后頭插法插到新的數(shù)組中。
你會發(fā)現(xiàn)兩個規(guī)律：
我們通過一個例子來分析一下第二條規(guī)律。
假設(shè)table.length=16，現(xiàn)在有兩個key,key1對應(yīng)的hash值為68,key2對應(yīng)hash值為84,根據(jù)公式h & (length-1)計算，&運算規(guī)則是遇0為0，結(jié)果如下：
68 key1 0100 0100 & 0000 1111 =0000 0100 =4 84 key2 0101 0100 & 0000 1111 =0000 0100 =4可見兩個值都落在table[4]這個桶中。
擴容一次后table.length=32，再根據(jù)公式h & (length-1)計算結(jié)果如下：
68 key1 0100 0100 & 0001 1111 =0000 0100 =4 84 key2 0101 0100 & 0001 1111 =0001 0100 =20可見68依然被放在新數(shù)組的table[4],而84被放在table[20]。
再擴容一次后table.length=64，再根據(jù)公式h & (length-1)計算結(jié)果如下：
68 key1 0100 0100 & 0011 1111 =0000 0100 =4 84 key2 0101 0100 & 0011 1111 =0001 0100 =20可見兩個值還在原來的數(shù)組下標(biāo)對應(yīng)的桶中。
結(jié)論：同一個桶中的鏈表中的數(shù)據(jù)，擴容后，在新數(shù)組中的下標(biāo)要么和原數(shù)組相同，要么是原數(shù)組下標(biāo)加擴容的長度。
這個規(guī)律是怎么形成的呢？
這得益于數(shù)組的容量都為2的n次方，數(shù)組每次擴容的后結(jié)果都是原來數(shù)組容量的兩倍，例如：16，32,64...，length-1的結(jié)果分別是15,31,63，而對應(yīng)的二進制如下：
0000 11110001 11110011 1111可以看的出，每次擴容都是高位加1，就導(dǎo)致在計算的時候只需要看hash值中與高位對應(yīng)的那個位上是0還是1，也就導(dǎo)致新數(shù)組中的下標(biāo)只有兩種可能：如果是0下標(biāo)不變，如果是1下標(biāo)就會變化。
這個規(guī)律有什么好處呢？
這個規(guī)律可以使原來在同個桶中的數(shù)據(jù)可以分散到其他桶中，使得數(shù)組分部更加均勻，減少hash沖突，擴容的時候同個桶中的數(shù)據(jù)將會被分部到新數(shù)組中的哪個桶中，可以通過只判斷高位就能確定，所以可以以此來優(yōu)化擴容效率。
// createEntry方法void createEntry(int hash, K key, V value, int bucketIndex) { // 獲取當(dāng)前數(shù)組下標(biāo)位置的鏈表頭 Entry<K,V> e = table[bucketIndex]; // 在鏈表頭位置創(chuàng)建新的Entry，next指向原鏈表頭（頭插法） table[bucketIndex] = new Entry<>(hash, key, value, e); // 數(shù)組長度+1 size++;}頭插法的源碼就很簡單了，就是新建一個Entry對象，新建Entry對象的next屬性指向當(dāng)前坐標(biāo)下的頭部Entry對象，再把新的Entry對象引用賦值給當(dāng)前數(shù)組下標(biāo)處。
這里的文字說明可能比自己看源碼更繞。自己看源碼應(yīng)該一目了然。
只有在數(shù)組長度為2的n次方時，數(shù)組長度-1轉(zhuǎn)換為2進制時才可以轉(zhuǎn)換為低位全部為1的二進制，和hash值進行&運算時才能等效于hash值除以數(shù)組容量求余的結(jié)果。
實際上無論是頭插法還是尾插法，都是需要遍歷鏈表的，如果在遍歷過程中找到key相同的，則更新覆蓋，這種情況不會有插入操作，所以無所謂頭插法和尾插法，但是如果沒有找到key相同的元素，那這時肯定已經(jīng)遍歷到鏈表的尾部了，所以但凡插入，不管是頭插法還是尾插法都不會在遍歷鏈表上節(jié)省時間，又因為鏈表的插入僅僅是更換next屬性的指針，所以兩種插入方式的效率是沒有區(qū)別的。
java1.7之所以使用頭插法應(yīng)該和自身的代碼結(jié)構(gòu)有關(guān)，因為插入方法是獨立的，如果用尾插法，就要在遍歷的時候記錄最后一個元素的值，而頭插法就不需要了，但是我覺得這個不是主要原因，個人覺得java開發(fā)者只不過是兩者選擇了一個而已，沒有什么特殊考慮，否則也不至于會有循環(huán)鏈表的問題了。
hashMap線程不安全主要表現(xiàn)在兩個方面：
(1)多線程插入數(shù)據(jù)的時候，數(shù)據(jù)丟失問題
void createEntry(int hash, K key, V value, int bucketIndex) { Entry<K,V> e = table[bucketIndex]; table[bucketIndex] = new Entry<>(hash, key, value, e); size++;}上面是頭插法的代碼邏輯，在多線程操作下，如果兩個線程同時走到方法內(nèi)第一行，那么獲取到的e是相同的，然后兩個線程分別創(chuàng)建Entry對象，并且Entry對象的next屬性賦值為e，這樣一來總會有一個線程的數(shù)據(jù)被丟掉了。
(2) 多線程情況下擴容的時候可能會發(fā)生循環(huán)鏈表
循環(huán)鏈表發(fā)生在多線程擴容的情況下，下面是擴容的部分代碼：
for (Entry<K,V> e : table) { while(null != e) { Entry<K,V> next = e.next; if (rehash) { e.hash = null == e.key ? 0 : hash(e.key); } int i = indexFor(e.hash, newCapacity); e.next = newTable[i]; newTable[i] = e; e = next; }這段代碼邏輯是把舊數(shù)組中的數(shù)據(jù)從鏈表頭部一個個利用頭插法插入到新數(shù)組中。
假設(shè)有兩個線程同時進行擴容，兩條線程都執(zhí)行到下面這行代碼：
Entry<K,V> next = e.next;此時第一條線程繼續(xù)執(zhí)行，第二條線程卡住，等到第一條線程整個循環(huán)執(zhí)行結(jié)束后，第二條線程才繼續(xù)執(zhí)行。
此時第一條線程擴容完成，鏈表的指向和原數(shù)組的順序相反。假設(shè)原數(shù)組的某個桶中鏈表方向是1>2>3>4,擴容后又恰好都落在同一個新的桶中，那么新的鏈表方向是4>3>2>1。
此時第二條線程開始執(zhí)行循環(huán)：
此時循環(huán)鏈表出現(xiàn)了。
本文鏈接：http://www.www897cc.com/showinfo-26-14005-0.html徹底搞懂hashMap底層原理
聲明：本網(wǎng)頁內(nèi)容旨在傳播知識，若有侵權(quán)等問題請及時與本網(wǎng)聯(lián)系，我們將在第一時間刪除處理。郵件：2376512515@qq.com
上一篇： 增強現(xiàn)實改變營銷的三種方式
下一篇： Java代碼手撕【數(shù)據(jù)結(jié)構(gòu)】| 隊列的實現(xiàn)與優(yōu)化指南
Copyright ? 2016-2023 天津谷騏科技有限公司 版權(quán)所有 sitemap.xml
違法及侵權(quán)請聯(lián)系：2376512515@qq.com 津ICP備18001702號
津公網(wǎng)安備 12010102000574號