Java HashMap的工作原理
来自: http://blog.csdn.net//chenleixing/article/details/44003753
面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下HashMap内部的工作原理。首先我们从一个例子开始,而不仅仅是从理论上,这样,有助于更好地理解,然后,我们来看下get和put到底是怎样工作的。
我们来看个非常简单的例子。有一个”国家”(Country)类,我们将要用Country对象作为key,它的首都的名字(String类型)作为value。下面的例子有助于我们理解key-value对在HashMap中是如何存储的。
1. Country.java
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 </td> | 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 ; } } | </tr> </tbody> </table> </div> </div>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 </td> | 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); } } } | </tr> </tbody> </table> </div> </div>
1 2 3 4 5 6 7 8 </td> | static class Entry implements Map.Entry { final K key; V value; Entry next; final int hash; ... //More code goes here } ` | </tr> </tbody> </table> </div> </div>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 </td> | /** * 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 ; } | </tr> </tbody> </table> </div> </div>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 </td> | /** * 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 ; } | </tr> </tbody> </table> </div> </div>