Java中HashMap的工作機制

　　現在很多的Java程序員都會把HashMap當作一個熱門話題今天我也來說一說Hashmap

　　我假設你對HashMap感興趣另外我認為你已經了解了HashMap的基礎這裡我就不再贅述HashMap是個什麼東東如果對於你來講HashMap還是一個新概念的話你可以去看看官方的javadoc

　　一句話回答

　　什麼是哈希

　　關於Entry類的一點介紹

　　put()方法實際上做了什麼

　　get()方法內部工作機制

　　注意點

　　一句話回答

　　如果任何人讓我描述一下HashMap的工作機制的話我就簡單的回答基於Hash的規則這句話非常簡單但是要理解這句話之前首先我們得了解什麼是哈希不是麼？

　　什麼是哈希

　　哈希簡單的說就是對變量/對象的屬性應用某種算法後得到的一個唯一的串用這個串來確定變量/對象的唯一性一個正確的哈希函數必須遵守這個准則

　　當哈希函數應用在相同的對象或者equal的對象的時候每次執行都應該返回相同的值換句話說兩個相等的對象應該有相同的hashcode

　　注所有Java對象都從Object類繼承了一個默認的hashCode()方法這個方法將對象在內存中的地址作為整數返回這是一個很好的hash實現他確保了不同的對象擁有不同的hashcode

　　關於Entry類的一點介紹

　　一個map的定義是一個映射鍵（key）到值（value）的對象非常簡單對吧

　　所以在HashMap中一定有一定的機制來存儲這些鍵值對使得HashMap有一個內部類Entry看起來像這樣

　　static class Entry<KV> implements MapEntry<KV>
   {
           final K key;
           V value;
           Entry<KV> next;
           final int hash;
           //More code goes here
   }

　　當然Entry類有屬性用來存儲鍵值對映射key被final標記除了key和value我們還能看到兩個變量next和hash接下來我們試著理解這些變量的含義

　　put()方法實際上做了什麼

　　再進一步看put方法的實現之前我們有必要看一看Entry實例在數組中的存儲HashMap中是這樣定義的

　　/**
        * The table resized as necessary Length MUST Always be a power of two
        */
       transient Entry[] table;

　　現在再來看put方法的實現

　　/**
   * Associates the specified value with the specified key in this map
   * If the map previously contained a mapping for the key the old
   * value is replaced
   *
   * @param key key with which the specified value is to be associated
   * @param value value to be associated with the specified key
   * @return the previous value associated with <tt>key</tt> or
   *         <tt>null</tt> if there was no mapping for <tt>key</tt>
   *         (A <tt>null</tt> return can also indicate that the map
   *         previously associated <tt>null</tt> with <tt>key</tt>)
   */
   public V put(K key V value) {
   if (key == null)
   return putForNullKey(value);
   int hash = hash(keyhashCode());
   int i = indexFor(hash tablelength);
   for (Entry<KV> e = table[i]; e != null; e = enext) {
   Object k;
   if (ehash == hash && ((k = ekey) == key || keyequals(k))) {
   V oldValue = evalue;
   evalue = value;
   erecordAccess(this);
   return oldValue;
   }
   }
   modCount++;
   addEntry(hash key value i);
   return null;
   }

　　讓我們一步一步的看

　　首先檢查key是否為null如果key是null值被存在table[]的位置因為null的hashcode始終為接下來通過key的hashCode()方法計算了這個key的hash值這個hash值被用來計算存儲Entry對象的數組中的位置JDK的設計者假設會有一些人可能寫出非常差的hashCode()方法會出現一些非常大或者非常小的hash值為了解決這個問題他們引入了另外一個hash函數接受對象的hashCode()並轉換到適合數組的容量大小

　　接著是indexFor(hashtablelength)方法這個方法計算了entry對象存儲的准確位置

　　接下來就是主要的部分我們都知道兩個不相等的對象可能擁有過相同的hashCode值兩個不同的對象是怎麼存儲在相同的位置[叫做bucket]呢？

　　答案是LinkedList如果你記得Entry類有一個next變量這個變量總是指向鏈中的下一個變量這完全符合鏈表的特點

　　所以在發生碰撞的時候entry對象會被以鏈表的形式存儲起來當一個Entry對象需要被存儲的時候hashmap檢查該位置是否已近有了一個entry對象如果沒有就存在那裡如果有了就檢查她的next屬性如果是空當前的entry對象就作為已經存儲的entry對象的下一個節點依次類推

　　如果我們給已經存在的key存入另一個value會怎麼樣的？邏輯上舊的值將被替換掉在檢測了Entry對象的存儲位置後hashmap將會遍歷那個位置的entry鏈表對每一個entry調用equals方法這個鏈表中的所有對象都具有相同的hashCode()而equals方法都不等如果發現equals方法有相等的就執行替換

　　在這種方式下HashMap就能保證key的唯一性

　　get方法的工作機制

　　現在我們已經了解了HashMap中存儲鍵值對的機制下一個問題是怎樣從一個HashMap中查詢結果

　　其實邏輯跟put是一樣的如果傳入的key有匹配就將該位置的value返回如果沒有就返回null

　　/**
   * Returns the value to which the specified key is mapped
   * or {@code null} if this map contains no mapping for the key
   *
   * <p>More formally if this map contains a mapping from a key
   * {@code k} to a value {@code v} such that {@code (key==null ? k==null :
   * keyequals(k))} then this method returns {@code v}; otherwise
   * it returns {@code null}  (There can be at most one such mapping)
   *
   * <p>A return value of {@code null} does not <i>necessarily</i>
   * indicate that the map contains no mapping for the key; its also
   * possible that the map explicitly maps the key to {@code null}
   * The {@link #containsKey containsKey} operation may be used to
   * distinguish these two cases
   *
   * @see #put(Object Object)
   */
   public V get(Object key) {
   if (key == null)
   return getForNullKey();
   int hash = hash(keyhashCode());
   for (Entry<KV> e = table[indexFor(hash tablelength)];
   e != null;
   e = enext) {
   Object k;
   if (ehash == hash && ((k = ekey) == key || keyequals(k)))
   return evalue;
   }
   return null;
   }

　　上面的代碼看起來跟put()方法很像除了if (ehash == hash && ((k = ekey) == key || keyequals(k)))

　　注意點

　　存儲Entry對象的數據結構是一個叫做Entry類型的table數組

　　數組中一個特定的索引位置稱為bucket因為它可以容納一個LinkedList的第一個元素的對象

　　Key對象的hashCode()需要用來計算Entry對象的存儲位置

　　Key對象的equals()方法需要用來維持Map中對象的唯一性

　　get()和put()方法跟Value對象的hashCode和equals方法無關

　　null的hashCode總是這樣的Entry對象總是被存儲在數組的第一個位置

From:http://tw.wingwit.com/Article/program/Java/hx/201311/26745.html