面試的時(shí)候經(jīng)常會(huì)遇見諸如:“java中的HashMap是怎么工作的”,“HashMap的get和put內(nèi)部的工作原理”這樣的問題。本文將用一個(gè)簡單的例子來解釋下HashMap內(nèi)部的工作原理。首先我們從一個(gè)例子開始,而不僅僅是從理論上,這樣,有助于更好地理解,然后,我們來看下get和put到底是怎樣工作的。
我們來看個(gè)非常簡單的例子。有一個(gè)”國家”(Country)類,我們將要用Country對象作為key,它的首都的名字(String類型)作為value。下面的例子有助于我們理解key-value對在HashMap中是如何存儲(chǔ)的。
1. Country.java
package org.arpit.javapostsforlearning;
public class Country {
String name;
long population;
public Country(String name, long population) {
super();
this.name = name;
this.population = population;
}
public String getName() {
return name;
}
public void setName(String name) {
this.name = name;
}
public long getPopulation() {
return population;
}
public void setPopulation(long population) {
this.population = population;
}
// If length of name in country object is even then return 31(any random number) and if odd then return 95(any random number).
// This is not a good practice to generate hashcode as below method but I am doing so to give better and easy understanding of hashmap.
@Override
public int hashCode() {
if(this.name.length()%2==0)
return 31;
else
return 95;
}
@Override
public boolean equals(Object obj) {
Country other = (Country) obj;
if (name.equalsIgnoreCase((other.name)))
return true;
return false;
}
}
2. HashMapStructure.java(main class)
import java.util.HashMap;
import java.util.Iterator;
public class HashMapStructure {
/**
* @author Arpit Mandliya
*/
public static void main(String[] args) {
Country india=new Country('India',1000);
Country japan=new Country('Japan',10000);
Country france=new Country('France',2000);
Country russia=new Country('Russia',20000);
HashMap<country,string> countryCapitalMap=new HashMap<country,string>();
countryCapitalMap.put(india,'Delhi');
countryCapitalMap.put(japan,'Tokyo');
countryCapitalMap.put(france,'Paris');
countryCapitalMap.put(russia,'Moscow');
Iterator<country> countryCapitalIter=countryCapitalMap.keySet().iterator();//put debug point at this line
while(countryCapitalIter.hasNext())
{
Country countryObj=countryCapitalIter.next();
String capital=countryCapitalMap.get(countryObj);
System.out.println(countryObj.getName() '----' capital);
}
}
}
現(xiàn)在,在第23行設(shè)置一個(gè)斷點(diǎn),在項(xiàng)目上右擊->調(diào)試運(yùn)行(debug as)->java應(yīng)用(java application)。程序會(huì)停在23行,然后在countryCapitalMap上右擊,選擇“查看”(watch)。將會(huì)看到如下的結(jié)構(gòu):
從上圖可以觀察到以下幾點(diǎn):
1. 有一個(gè)叫做table大小是16的Entry數(shù)組。
2. 這個(gè)table數(shù)組存儲(chǔ)了Entry類的對象。HashMap類有一個(gè)叫做Entry的內(nèi)部類。這個(gè)Entry類包含了key-value作為實(shí)例變量。我們來看下Entry類的結(jié)構(gòu)。Entry類的結(jié)構(gòu):
static class Entry implements Map.Entry
{
final K key;
V value;
Entry next;
final int hash;
...//More code goes here
}
3. 每當(dāng)往hashmap里面存放key-value對的時(shí)候,都會(huì)為它們實(shí)例化一個(gè)Entry對象,這個(gè)Entry對象就會(huì)存儲(chǔ)在前面提到的Entry數(shù)組table中?,F(xiàn)在你一定很想知道,上面創(chuàng)建的Entry對象將會(huì)存放在具體哪個(gè)位置(在table中的精確位置)。答案就是,根據(jù)key的hashcode()方法計(jì)算出來的hash值(來決定)。hash值用來計(jì)算key在Entry數(shù)組的索引。
4. 現(xiàn)在,如果你看下上圖中數(shù)組的索引10,它有一個(gè)叫做HashMap$Entry的Entry對象。
5. 我們往hashmap放了4個(gè)key-value對,但是看上去好像只有2個(gè)元素?。?!這是因?yàn)椋绻麅蓚€(gè)元素有相同的hashcode,它們會(huì)被放在同一個(gè)索引上。問題出現(xiàn)了,該怎么放呢?原來它是以鏈表(LinkedList)的形式來存儲(chǔ)的(邏輯上)。
上面的country對象的key-value的hash值是如何計(jì)算出來的。
<code>Japan的Hash值是95,它的長度是奇數(shù)。
India的Hash值是95,它的長度是奇數(shù)。
Russia的Hash值是31,它的長度是偶數(shù)。
France,它的長度是偶數(shù)。
</code>
下圖會(huì)清晰的從概念上解釋下鏈表。
所以,現(xiàn)在假如你已經(jīng)很好地了解了hashmap的結(jié)構(gòu),讓我們看下put和get方法。
Put :
讓我們看下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 <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(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;
}
現(xiàn)在我們一步一步來看下上面的代碼。
對key做null檢查。如果key是null,會(huì)被存儲(chǔ)到table[0],因?yàn)閚ull的hash值總是0。
key的hashcode()方法會(huì)被調(diào)用,然后計(jì)算hash值。hash值用來找到存儲(chǔ)Entry對象的數(shù)組的索引。有時(shí)候hash函數(shù)可能寫的很不好,所以JDK的設(shè)計(jì)者添加了另一個(gè)叫做hash()的方法,它接收剛才計(jì)算的hash值作為參數(shù)。
indexFor(hash,table.length)用來計(jì)算在table數(shù)組中存儲(chǔ)Entry對象的精確的索引。
在我們的例子中已經(jīng)看到,如果兩個(gè)key有相同的hash值(也叫沖突),他們會(huì)以鏈表的形式來存儲(chǔ)。所以,這里我們就迭代鏈表。
如果在剛才計(jì)算出來的索引位置沒有元素,直接把Entry對象放在那個(gè)索引上。
如果索引上有元素,然后會(huì)進(jìn)行迭代,一直到Entry->next是null。當(dāng)前的Entry對象變成鏈表的下一個(gè)節(jié)點(diǎn)。
如果我們再次放入同樣的key會(huì)怎樣呢?邏輯上,它應(yīng)該替換老的value。事實(shí)上,它確實(shí)是這么做的。在迭代的過程中,會(huì)調(diào)用equals()方法來檢查key的相等性(key.equals(k)),如果這個(gè)方法返回true,它就會(huì)用當(dāng)前Entry的value來替換之前的value。
Get:
現(xiàn)在我們來看下get方法的實(shí)現(xiàn):
/**
* 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}. (There can be at most one such mapping.)
*
* </p><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;
}
當(dāng)你理解了hashmap的put的工作原理,理解get的工作原理就非常簡單了。當(dāng)你傳遞一個(gè)key從hashmap總獲取value的時(shí)候:
對key進(jìn)行null檢查。如果key是null,table[0]這個(gè)位置的元素將被返回。
key的hashcode()方法被調(diào)用,然后計(jì)算hash值。
indexFor(hash,table.length)用來計(jì)算要獲取的Entry對象在table數(shù)組中的精確的位置,使用剛才計(jì)算的hash值。
在獲取了table數(shù)組的索引之后,會(huì)迭代鏈表,調(diào)用equals()方法檢查key的相等性,如果equals()方法返回true,get方法返回Entry對象的value,否則,返回null。
要牢記以下關(guān)鍵點(diǎn):
HashMap有一個(gè)叫做Entry的內(nèi)部類,它用來存儲(chǔ)key-value對。
上面的Entry對象是存儲(chǔ)在一個(gè)叫做table的Entry數(shù)組中。
table的索引在邏輯上叫做“桶”(bucket),它存儲(chǔ)了鏈表的第一個(gè)元素。
key的hashcode()方法用來找到Entry對象所在的桶。
如果兩個(gè)key有相同的hash值,他們會(huì)被放在table數(shù)組的同一個(gè)桶里面。
key的equals()方法用來確保key的唯一性。
value對象的equals()和hashcode()方法根本一點(diǎn)用也沒有。
Java團(tuán)長
微信號:javatuanzhang
每日分享Java技術(shù)干貨