溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
首先我們先看源碼：
|
// 將“key-value”添加到HashMap中 public V put(K key, V value) { // 若“key為null”，則將該鍵值對添加到table[0]中。 if (key == null) return putForNullKey(value); // 若“key不為null”，則計算該key的哈希值，然后將其添加到該哈希值對應的鏈表中。 int hash = hash(key.hashCode()); // 計算key hash值在table數組中的位置 ------------ （1） int i = indexFor(hash, table.length); // 迭代e，從i處開始，找到key保存的位置 ------------ （2） for (Entry<K,V> e = table[i]; e != null; e = e.next) { Object k; // 若“該key”對應的鍵值對已經存在，則用新的value取代舊的value。然后退出！ if (e.hash == hash && ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 若“該key”對應的鍵值對不存在，則將“key-value”添加到table中 modCount++; //將key-value添加到table[i]處 addEntry(hash, key, value, i); return null; } |
通過源碼我們可以清晰看到HashMap保存數據的過程為：首先判斷key是否為null，若為null，則直接調用putForNullKey方法。若不為空則先計算key的hash值，然后根據hash值搜索在table數組中的索引位置，如果table數組在該位置處有元素，則通過比較是否存在相同的key，若存在則覆蓋原來key的value，否則將該元素保存在鏈頭（最先保存的元素放在鏈尾）。若table在該處沒有元素，則直接保存。
1、 先看迭代處。此處迭代原因就是為了防止存在相同的key值，若發現兩個hash值（key）相同時，HashMap的處理方式是用新value替換舊value，這里并沒有處理key，這就解釋了HashMap中沒有兩個相同的key。
2、 再看（1）、（2）處。這里是HashMap的精華所在。首先是hash方法，該方法為一個純粹的數學計算，就是計算h的hash值。
|
static int hash(int h) { return useNewHash ? newHash(h) : oldHash(h); } |
useNewHash聲明如下：
|
private static final boolean useNewHash; static { useNewHash = false; } |
|
private static int oldHash(int h) { h += ~(h << 9); h ^= (h >>> 14); h += (h << 4); h ^= (h >>> 10); return h; } private static int newHash(int h) { // This function ensures that hashCodes that differ only by // constant multiples at each bit position have a bounded // number of collisions (approximately 8 at default load factor). h ^= (h >>> 20) ^ (h >>> 12); return h ^ (h >>> 7) ^ (h >>> 4); } |
我們知道對于HashMap的table而言，數據分布需要均勻（最好每項都只有一個元素，這樣就可以直接找到），不能太緊也不能太松，太緊會導致查詢速度慢，太松則浪費空間。計算hash值后，怎么才能保證table元素分布均與呢？我們會想到取模，但是由于取模的消耗較大，HashMap是這樣處理的：調用indexFor方法。
|
static int indexFor(int h, int length) { return h & (length-1); } |
HashMap的底層數組長度總是2的n次方，在構造函數中存在：capacity <<= 1;這樣做總是能夠保證HashMap的底層數組長度為2的n次方。當length為2的n次方時，h&(length - 1)就相當于對length取模，而且速度比直接取模快得多，這是HashMap在速度上的一個優化。至于為什么是2的n次方下面解釋。
我們回到indexFor方法，該方法僅有一條語句：h&(length - 1) 作用：均勻分布table數據和充分利用空間。
這里我們假設length為16(2^n)和15，h為5、6、7。
| length = 16 | |||
| h | length - 1 | h & length -1 | |
| 5 | 15 | 0101 & 1111 = 00101 | 5 |
| 6 | 15 | 0110 & 1111 = 00110 | 6 |
| 7 | 15 | 0111 & 1111 = 00111 | 7 |
| length = 15 | |||
| 5 | 14 | 0101 & 1110 = 00101 | 5 |
| 6 | 14 | 0110 & 1110 = 00110 | 6 |
| 7 | 14 | 0111 & 1110 = 00110 | 6 |
當n=15時，6和7的結果一樣，這樣表示他們在table存儲的位置是相同的，也就是產生了碰撞，6、7就會在一個位置形成鏈表，這樣就會導致查詢速度降低。誠然這里只分析三個數字不是很多，那么我們就看0-15。
| h | length - 1 | h & length - 1 | |
| 0 | 14 | 0000 & 1110 = 0000 | 0 |
| 1 | 14 | 0001 & 1110 = 0000 | 0 |
| 2 | 14 | 0010 & 1110 = 0010 | 2 |
| 3 | 14 | 0011 & 1110 = 0010 | 2 |
| 4 | 14 | 0100 & 1110 = 0100 | 4 |
| 5 | 14 | 0101 & 1110 = 0100 | 4 |
| 6 | 14 | 0110 & 1110 = 0110 | 6 |
| 7 | 14 | 0111 & 1110 = 0110 | 6 |
| 8 | 14 | 1000 & 1110 = 1000 | 8 |
| 9 | 14 | 1001 & 1110 = 1000 | 8 |
| 10 | 14 | 1010 & 1110 = 1010 | 10 |
| 11 | 14 | 1011 & 1110 = 1010 | 10 |
| 12 | 14 | 1100 & 1110 = 1100 | 12 |
| 13 | 14 | 1101 & 1110 = 1100 | 12 |
| 14 | 14 | 1110 & 1110 = 1110 | 14 |
| 15 | 14 | 1111 & 1110 = 1110 | 14 |
從上面的圖表中我們看到總共發生了8此碰撞，同時發現浪費的空間非常大，有1、3、5、7、9、11、13、15處沒有記錄，也就是沒有存放數據。這是因為他們在與14進行&運算時，得到的結果最后一位永遠都是0，即0001、0011、0101、0111、1001、1011、1101、1111位置處是不可能存儲數據的，空間減少，進一步增加碰撞幾率，這樣就會導致查詢速度慢。而當length = 16時，length – 1 = 15 即1111，那么進行低位&運算時，值總是與原來hash值相同，而進行高位運算時，其值等于其低位值。所以說當length = 2^n時，不同的hash值發生碰撞的概率比較小，這樣就會使得數據在table數組中分布較均勻，查詢速度也較快。
這里我們再來復習put的流程：當我們想一個HashMap中添加一對key-value時，系統首先會計算key的hash值，然后根據hash值確認在table中存儲的位置。若該位置沒有元素，則直接插入。否則迭代該處元素鏈表并依此比較其key的hash值。如果兩個hash值相等且key值相等(e.hash == hash && ((k = e.key) == key || key.equals(k))),則用新的Entry的value覆蓋原來節點的value。如果兩個hash值相等但key值不等 ，則將該節點插入該鏈表的鏈頭。具體的實現過程見addEntry方法，如下：
|
void addEntry(int hash, K key, V value, int bucketIndex) { // 獲取bucketIndex處的Entry Entry<K,V> e = table[bucketIndex]; // 將新創建的 Entry 放入 bucketIndex 索引處，并讓新的 Entry 指向原來的 Entry table[bucketIndex] = new Entry<K,V>(hash, key, value, e); // 若HashMap中元素的個數超過極限了，則容量擴大兩倍 if (size++ >= threshold) resize(2 * table.length); } |
這個方法中有兩點需要注意：
一、鏈的產生。
系統總是將新的Entry對象添加到bucketIndex處。如果bucketIndex處已經有了對象，那么新添加的Entry對象將指向原有的Entry對象，形成一條Entry鏈，但是若bucketIndex處沒有Entry對象，也就是e==null,那么新添加的Entry對象指向null，也就不會產生Entry鏈了。
二、擴容問題。
隨著HashMap中元素的數量越來越多，發生碰撞的概率就越來越大，所產生的鏈表長度就會越來越長，這樣勢必會影響HashMap的速度，為了保證HashMap的效率，系統必須要在某個臨界點進行擴容處理。該臨界點在當HashMap中元素的數量等于table數組長度*加載因子。但是擴容是一個非常耗時的過程，因為它需要重新計算這些數據在新table數組中的位置并進行復制處理。所以如果我們已經預知HashMap中元素的個數，那么預設元素的個數能夠有效的提高HashMap的性能。
相對于HashMap的存而言，取就顯得比較簡單了。通過key的hash值找到在table數組中的索引處的Entry，然后返回該key對應的value即可。
|
// 獲取key對應的value public V get(Object key) { // 若為null，調用getForNullKey方法返回相對應的value if (key == null) // 根據該 key 的 hashCode 值計算它的 hash 碼 return getForNullKey(); // 獲取key的hash值 int hash = hash(key.hashCode()); // 取出 table 數組中指定索引處的值,在“該hash值對應的鏈表”上查找“鍵值等于key”的元素 for (Entry<K,V> e = table[indexFor(hash, table.length)]; e != null; e = e.next) { Object k; //判斷key是否相同,若key與查找的key相同，則返回相對應的value if (e.hash == hash && ((k = e.key) == key || key.equals(k))) return e.value; } //沒找到則返回null return null; } |
在這里能夠根據key快速的取到value除了和HashMap的數據結構密不可分外，還和Entry有莫大的關系，在前面就提到過，HashMap在存儲過程中并沒有將key，value分開來存儲，而是當做一個整體key-value來處理的，這個整體就是Entry對象。同時value也只相當于key的附屬而已。在存儲的過程中，系統根據key的hashcode來決定Entry在table數組中的存儲位置，在取的過程中同樣根據key的hashcode取出相對應的Entry對象。上海尚學堂java培訓原創，陸續java技術相關文章奉上，請多關注。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
