哪位大神給解讀一下jdk裡面Map中put方法的一段源代碼？

12-29

主要解讀for循環裡面的語句(也包括條件)
public V put(K key, V value) { if (table == EMPTY_TABLE) { inflateTable(threshold); } if (key == null) return putForNullKey(value); int hash = hash(key); int i = indexFor(hash, table.length); for (Entry& e = table[i]; e != null; e = e.next) { Object k; if (e.hash == hash ((k = e.key) == key || key.equals(k))) { V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } }
modCount++; addEntry(hash, key, value, i); return null; }
我想再問一下，如果有兩個對象 p1 p2 我重寫了hashCode()，它們的hashCode一樣，但「==」和equals是false，那p1 p2作為key在HashMap中存儲數據將會怎樣的？

HashMap原理分析

HashMap最重要的兩個方法就是：（這裡先不考慮泛型）

put(Object key, Object value); Object get(Object key);

對於put方法，是這樣描述的：如果key已存在就更新其value，如果key不存在就添加key和value。

對於get方法，是這樣描述的：如果key已存在就返回其value，如果key不存在就返回null。

更關鍵的是對於這兩個方法，其時間複雜度應該近似於O(1)，而不能是O(N)。

那麼問題一：如何判斷key存在？Java的規定是調用下面這個方法，如果能有一個已存在的key返回 true，那麼表示這個key就已存在。

boolean equals(Object obj);

這個方法是Object類的方法，所以任何對象都有，但是顯然其默認實現可能並不符合我們的業務邏輯，有時需要覆蓋其默認實現。

那麼問題二：hashMap如何存儲數據呢？使用鏈表，使用數組，使用二叉樹？

a) 使用鏈表，那麼時間複雜度顯示是O(N)不符合要求。

b) 使用二叉樹，如果是一顆平衡的樹，最佳複雜度為O(log2N)，如果是極端不平衡的樹，最差複雜度為O(N)，也不符合要求。

c) 使用數組，如果是遍歷迭代那麼和鏈表沒有區別，除非我能從 Key 直接定位到某個確定下標，才有可能實現O(1)的時間複雜度。

那麼問題三：如何從Key獲取到固定的數組下標？

數組下標是個整數，Key的類型可能多種多樣，怎麼轉換？答案：藉助 hashCode() 方法。

hashCode的取值範圍是整個Int的取值範圍，數組下標的取值範圍是 0 到 arr.length - 1，所以還需要藉助一個方法，來將hashCode映射到數組下標的取值範圍中去，就是 indexFor() 方法。

int hashCode(); int indexFor(int hash, int length);

那麼問題四：數組下標有了，原位置可能沒有數據，有一個數據，有多個數據，如何處理？

a) 如果原位置沒有，那麼將key和value組成鍵值對直接方法該位置即可。（添加數據）

b) 如果原位置數據，且只有一個，那麼比較key是否相等，如果相等，更新數據。

如果不相等，添加數據。判斷方法為：先比較其hashCode，如果hashCode不相等，則直接判定不相等，如果hashCode相等，則再調用equals方法，根據其返回值判定是否相等。

c) 如果是更新數據，不用多提，只要更新鍵值對的 value 即可，如果是添加數據，且原位置已經有數據的話怎麼辦呢？答案是組成鏈表再放在該位置。（JDK8已經變更了實現，當同一位置的元素達到8個時，會觸發紅黑樹化操作，將鏈表改為紅黑樹，當元素數量降到6個時，會觸發去紅黑樹化操作，將紅黑樹改為鏈表。）

d) 這裡同時引出了一個問題，就是判斷 Key 是否存在時也需要沿著鏈表一個一個判斷，全部判斷完畢之後才確定的說這個 Key 不存在，可以添加數據了。

那麼問題五：既然有可能兩個 Key 映射到一個位置，還要組成鏈表，那麼還能說是O(1)的時間複雜度嗎？

這就牽扯到「碰撞」幾率的問題。兩個 Key 映射到一個位置，稱之為發生碰撞，顯然數組越大，碰撞幾率越小，元素添加的越多，碰撞幾率越大，這個有個比例，即已有元素除以數組大小，假設為P。根據經驗如果P&>0.75，那麼碰撞幾率就很大了，HashMap的性能有一定影響，如果P&<0.5，空間又比較浪費，JDK8以前的一個策略是，如果P超過了0.75，就將底層數組擴大一倍的容量。這個P的閥值是程序員可以根據需要自己指定的。

顯然如果完全沒有碰撞，那麼就是O(1)的複雜度，顯然沒有這麼樂觀，如果碰撞不嚴重的話還是可以期待其有較高的性能的（這就要求其 Key 的hashCode方法必須編寫好），就算有一些碰撞一般也認為其時間複雜度應該在O(logN)之下的。

那麼問題六：既然上面頻繁用到了equals方法和hashCode方法，那麼這兩個方法的編寫有沒有什麼要求？

如果你是使用JDK類庫的類作為Key，如String，Integer那麼不必考慮覆蓋這兩個方法，都是已經編寫好了的。如果是自定義類，但是業務邏輯上的判斷依據也是某個JDK的類，那麼編寫方法也很簡單，如這個User類。

public class User {


    private String username;

    private String password;

    private String email;
    @Override

    public int hashCode() {

        HashCodeBuilder builder = new HashCodeBuilder();

        builder.append(username);

        return builder.toHashCode();

    }

@Override public boolean equals(Object obj) { if (obj == this) { return true; } if (obj == null || obj.getClass() != this.getClass()) { return false; } User other = (User) obj; EqualsBuilder builder = new EqualsBuilder(); builder.append(this.username, other.username); return builder.isEquals(); } }

假設你的業務邏輯要求是根據 username 判斷整個User是否相等，那麼就可以像上面那樣編寫。

如果你的業務邏輯比較複雜，那麼恐怕就不能簡單的編寫了，只能列出幾個原則：

①對於兩個相等的對象，其 equals 必須返回 ture，其 hashCode 必須相等。

②對於兩個不等的對象，其 equals 必須返回 false，其 hashCode 盡量不相等，但不強求。

③對於有規律變化的對象，其 hashCode 如果能返回無規律的變化，則說明混淆度高，一般來說混淆度越高越好（但不強求）。一個 int 是32個二進位位，如果這種變化能夠遍及所有的位，則更好（也不強求）。

PS：indexFor函數，如果能將 hashCode高低位的變化，無規律的給出下標值，那麼說明其混淆度夠高，也是越高越好，但這個函數是JDK已經寫好了的，所以我們不用處理。

那麼問題來了，這段代碼到底怎麼解讀：

public V put(K key, V value) { // 如果table是空talbe，就初始化之，不多解釋。 if (table == EMPTY_TABLE) { inflateTable(threshold); } // 如果key是null，就XXX，不是重點，不多解釋。 if (key == null) return putForNullKey(value); // 獲取hash值 int hash = hash(key); // 獲取下標值 int i = indexFor(hash, table.length); // table就是內部數組，table[i]就是位置。 // 顯然如果一開始位置為null，就直接進入添加數據的流程即可。 for (Entry& e = table[i]; e != null; e = e.next) { Object k; // e.hash 實際上就是e.key.hashCode()，是之前添加時緩存好的。 // 如果 hash 不一樣，顯然就不用接著判斷了，可以直接取鏈表下一個數據了。 // 如果 hash 一樣，就可以判斷 equals 了，這裡先用 == 比較了，是一種快速判斷的技巧，如果去掉也不影響結果，只是可能比較耗時。 if (e.hash == hash ((k = e.key) == key || key.equals(k))) { // 顯然這裡說明找到了 key，要執行更新數據的操作。 V oldValue = e.value; e.value = value; e.recordAccess(this); return oldValue; } } // 如果運行到這裡，說明沒找到 key，需要執行添加數據的操作。 modCount++; // 這個怎麼添加也有一點小技巧，就是考慮到最近添加往往可能更常用，所以將最近添加的放到鏈表前部，已有數據放到後部，具體請自行看代碼吧。 addEntry(hash, key, value, i); return null; }

顯然，只有發生碰撞的情況下，才會真的執行for循環，否則的話也只需要計算一個hash，調用一個indexFor，然後比較hash，調用equals方法即可。顯然時間花費為常數時間，是O(1)的。

如果極限碰撞的情況下，如所有的 Key 都映射到一個位置上了，其複雜度也會退化到O(N)，但除非是故意讓 hashCode 返回一樣的值，否則不太可能出現這種情況。

少量碰撞的情況下，平均複雜度應該在O(1)和O(logN)之間。

比較兩個key是否一致，首先hash要相等，其次要麼引用相等要麼equals函數（通常是被子類覆蓋的）告訴你相等。其中蘊含的前提有：

如果兩個key相等，那麼他們算出來的hash必須相等。

如果兩個key的引用相等，那麼equals必須返回相等。

至於for 循環的條件：

hashmap 中存儲數據的是元素為Entry& 的數組table[ ]。Entry&有next屬性，它指向與自己處於數組相同位置的下一個元素。以此類推。

具體結構見上圖。(註：圖片來自Java學習之HashMap: 源碼學習)

在存數據的時候，首先得到key 的hash值，然後根據hash值得到存入的數據是處於數組table[ ]的哪個位置上。遍歷這個位置上所有的元素(e = e.next).

至於update的部分：

如果符合相等的條件(hash值相等並且key相等或者key 的equals為true)，就用新值update老值，返回老值。

1.8開始,hashMap已經不用鏈表存儲,改用紅黑數了

不過基本原理也就是輪子哥說的那樣,所以自定義類里的equal和hashCode方法一定要同時重寫

CSDN的博文，HashMap源碼分析：http://blog.csdn.net/ns_code/article/details/36034955，找到你不明白的那段，如果看不懂就把整個原理詳細看一遍

首先要理解hashmap裡面，是運用了鏈表結構來存儲數據的。key的hash值如果發生碰撞，那麼就會在hash值上用鏈表將對象串起來。因此如果單純的比較key的hash值，是不準確的，得重寫equals方法，才能準確地拿到key對應的value，之後再用新value覆蓋掉舊value。