如果任何人讓我描述一下HashMap的工作機(jī)制的話，我就簡單的回答：“基于Hash的規(guī)則”。這句話非常簡單，但是要理解這句話之前，首先我們得了解什么是哈希，不是么？

什么是哈希
哈希簡單的說就是對變量/對象的屬性應(yīng)用某種算法后得到的一個(gè)唯一的串，用這個(gè)串來確定變量/對象的唯一性。一個(gè)正確的哈希函數(shù)必須遵守這個(gè)準(zhǔn)則。

當(dāng)哈希函數(shù)應(yīng)用在相同的對象或者equal的對象的時(shí)候，每次執(zhí)行都應(yīng)該返回相同的值。換句話說，兩個(gè)相等的對象應(yīng)該有相同的hashcode。

注：所有Java對象都從Object類繼承了一個(gè)默認(rèn)的hashCode()方法。這個(gè)方法將對象在內(nèi)存中的地址作為整數(shù)返回，這是一個(gè)很好的hash實(shí)現(xiàn)，他確保了不同的對象擁有不同的hashcode。

關(guān)于Entry類的一點(diǎn)介紹
一個(gè)map的定義是：一個(gè)映射鍵（key）到值（value）的對象。非常簡單對吧。

所以，在HashMap中一定有一定的機(jī)制來存儲這些鍵值對。使得，HashMap有一個(gè) 內(nèi)部類Entry，看起來像這樣。
 

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

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

put()方法實(shí)際上做了什么
再進(jìn)一步看put方法的實(shí)現(xiàn)之前，我們有必要看一看Entry實(shí)例在數(shù)組中的存儲， HashMap中是這樣定義的：
 

/**
   * The table, resized as necessary. Length MUST Always be a power of two.
   */
  transient Entry[] table;
現(xiàn)在再來看put方法的實(shí)現(xiàn)。
 
/**
* 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
*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
 
<tt>null</tt> if there was no mapping for <tt>key</tt>.
*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; (A
 
<tt>null</tt> return can also indicate that the map
*&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; 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(key.hashCode());
int i = indexFor(hash, table.length);
for (Entry<K,V> 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;
}

讓我們一步一步的看
首先，檢查key是否為null，如果key是null值被存在table[0]的位置，因?yàn)閚ull 的hashcode始終為0
接下來，通過key的hashCode()方法計(jì)算了這個(gè)key的hash值，這個(gè)hash值被用來 計(jì)算存儲Entry對象的數(shù)組中的位置。JDK的設(shè)計(jì)者假設(shè)會有一些人可能寫出非常差的hashCode()方法，會出現(xiàn)一些 非常大或者非常小的hash值。為了解決這個(gè)問題，他們引入了另外一個(gè)hash函數(shù)，接受對象的hashCode()，并轉(zhuǎn)換 到適合數(shù)組的容量大小。

接著是indexFor(hash,table,length)方法，這個(gè)方法計(jì)算了entry對象存儲 的準(zhǔn)確位置。
接下來就是主要的部分，我們都知道兩個(gè)不相等的對象可能擁有過相同的 hashCode值，兩個(gè)不同的對象是怎么存儲在相同的位置[叫做bucket]呢？
答案是LinkedList。如果你記得，Entry類有一個(gè)next變量，這個(gè)變量總是指向 鏈中的下一個(gè)變量，這完全符合鏈表的特點(diǎn)。

所以，在發(fā)生碰撞的時(shí)候，entry對象會被以鏈表的形式存儲起來，當(dāng)一個(gè)Entry 對象需要被存儲的時(shí)候，hashmap檢查該位置是否已近有了一個(gè)entry對象，如果沒有就存在那里，如果有了就檢查 她的next屬性，如果是空，當(dāng)前的entry對象就作為已經(jīng)存儲的entry對象的下一個(gè)節(jié)點(diǎn)，依次類推。

如果我們給已經(jīng)存在的key存入另一個(gè)value會怎么樣的？邏輯上，舊的值將被替 換掉。在檢測了Entry對象的存儲位置后，hashmap將會遍歷那個(gè)位置的entry鏈表，對每一個(gè)entry調(diào)用equals方法 ，這個(gè)鏈表中的所有對象都具有相同的hashCode()而equals方法都不等。如果發(fā)現(xiàn)equals方法有相等的就執(zhí)行替換 。

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

get方法的工作機(jī)制
現(xiàn)在我們已經(jīng)了解了HashMap中存儲鍵值對的機(jī)制。下一個(gè)問題是：怎樣從一個(gè) HashMap中查詢結(jié)果。
其實(shí)邏輯跟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 :
* key.equals(k))}, then this method returns {@code v}; otherwise
* it returns {@code null}.&nbsp; (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; it's 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(key.hashCode());
for (Entry<K,V> e = table[indexFor(hash, table.length)];
e != null;
e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k)))
return e.value;
}
return null;
}

上面的代碼看起來跟put()方法很像，除了if (e.hash == hash && ((k = e.key) == key || key.equals(k)))。

注意點(diǎn)

•     存儲Entry對象的數(shù)據(jù)結(jié)構(gòu)是一個(gè)叫做Entry類型的table數(shù)組。
•     數(shù)組中一個(gè)特定的索引位置稱為bucket,因?yàn)樗梢匀菁{一個(gè)LinkedList 的第一個(gè)元素的對象。
•     Key對象的hashCode()需要用來計(jì)算Entry對象的存儲位置。
•     Key對象的equals()方法需要用來維持Map中對象的唯一性。
•     get()和put()方法跟Value對象的hashCode和equals方法無關(guān)。
•     null的hashCode總是0，這樣的Entry對象總是被存儲在數(shù)組的第一個(gè)位置

最新評論