|
面試的時(shí)候經(jīng)常會(huì)遇見(jiàn)諸如：“java中的HashMap是怎么工作的”，“HashMap的get和put內(nèi)部的工作原理”這樣的問(wèn)題。本文將用一個(gè)簡(jiǎn)單的例子來(lái)解釋下HashMap內(nèi)部的工作原理。首先我們從一個(gè)例子開(kāi)始，而不僅僅是從理論上，這樣，有助于更好地理解，然后，我們來(lái)看下get和put到底是怎樣工作的。 我們來(lái)看個(gè)非常簡(jiǎn)單的例子。有一個(gè)”國(guó)家”(Country)類(lèi)，我們將要用Country對(duì)象作為key，它的首都的名字（String類(lèi)型）作為value。下面的例子有助于我們理解key-value對(duì)在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類(lèi)的對(duì)象。HashMap類(lèi)有一個(gè)叫做Entry的內(nèi)部類(lèi)。這個(gè)Entry類(lèi)包含了key-value作為實(shí)例變量。我們來(lái)看下Entry類(lèi)的結(jié)構(gòu)。Entry類(lèi)的結(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對(duì)的時(shí)候，都會(huì)為它們實(shí)例化一個(gè)Entry對(duì)象，這個(gè)Entry對(duì)象就會(huì)存儲(chǔ)在前面提到的Entry數(shù)組table中?，F(xiàn)在你一定很想知道，上面創(chuàng)建的Entry對(duì)象將會(huì)存放在具體哪個(gè)位置（在table中的精確位置）。答案就是，根據(jù)key的hashcode()方法計(jì)算出來(lái)的hash值（來(lái)決定）。hash值用來(lái)計(jì)算key在Entry數(shù)組的索引。 4. 現(xiàn)在，如果你看下上圖中數(shù)組的索引10，它有一個(gè)叫做HashMap$Entry的Entry對(duì)象。 5. 我們往hashmap放了4個(gè)key-value對(duì)，但是看上去好像只有2個(gè)元素?。?！這是因?yàn)椋绻麅蓚€(gè)元素有相同的hashcode，它們會(huì)被放在同一個(gè)索引上。問(wèn)題出現(xiàn)了，該怎么放呢？原來(lái)它是以鏈表(LinkedList)的形式來(lái)存儲(chǔ)的(邏輯上)。 上面的country對(duì)象的key-value的hash值是如何計(jì)算出來(lái)的。 <code>Japan的Hash值是95，它的長(zhǎng)度是奇數(shù)。 下圖會(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)在我們一步一步來(lái)看下上面的代碼。
Get: 現(xiàn)在我們來(lái)看下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的工作原理就非常簡(jiǎn)單了。當(dāng)你傳遞一個(gè)key從hashmap總獲取value的時(shí)候：
要牢記以下關(guān)鍵點(diǎn)：
 Java團(tuán)長(zhǎng) 微信號(hào)：javatuanzhang 每日分享Java技術(shù)干貨 |
|
|
來(lái)自： Levy_X > 《JAVAWEB學(xué)習(xí)資料》
