快捷導(dǎo)航

深入理解Java中的HashMap的實(shí)現(xiàn)機(jī)制

更新時(shí)間：2015年07月12日 10:24:13 投稿：goldensun

這篇文章主要介紹了深入理解Java中的HashMap的實(shí)現(xiàn)機(jī)制,同時(shí)也有助于理解Java中對于哈希函數(shù)的相關(guān)處理方式,需要的朋友可以參考下

如果任何人讓我描述一下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ī)制來存儲(chǔ)這些鍵值對。使得，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類有屬性用來存儲(chǔ)鍵值對映射。key被final標(biāo)記，除了key和value ，我們還能看到兩個(gè)變量next和hash。接下來我們試著理解這些變量的含義。

put()方法實(shí)際上做了什么
再進(jìn)一步看put方法的實(shí)現(xiàn)之前，我們有必要看一看Entry實(shí)例在數(shù)組中的存儲(chǔ)， 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ì)算存儲(chǔ)Entry對象的數(shù)組中的位置。JDK的設(shè)計(jì)者假設(shè)會(huì)有一些人可能寫出非常差的hashCode()方法，會(huì)出現(xiàn)一些非常大或者非常小的hash值。為了解決這個(gè)問題，他們引入了另外一個(gè)hash函數(shù)，接受對象的hashCode()，并轉(zhuǎn)換到適合數(shù)組的容量大小。

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

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

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

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

get方法的工作機(jī)制
現(xiàn)在我們已經(jīng)了解了HashMap中存儲(chǔ)鍵值對的機(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)