面试的时候经常会遇见诸如:“java中的HashMap是怎么工作的”,“HashMap的get和put内部的工作原理”这样的问题。本文将用一个简单的例子来解释下HashMap内部的工作原理。首先我们从一个例子开始,而不仅仅是从理论上,这样,有助于更好地理解,然后,我们来看下get和put到底是怎样工作的。
我们来看个非常简单的例子。有一个”国家”(Country)类,我们将要用Country对象作为key,它的首都的名字(String类型)作为value。下面的例子有助于我们理解key-value对在HashMap中是如何存储的。
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);
- }
- }
- }
现在,在第23行设置一个断点,在项目上右击->调试运行(debug as)->java应用(java application)。程序会停在23行,然后在countryCapitalMap上右击,选择“查看”(watch)。将会看到如下的结构:
从上图可以观察到以下几点:
1. 有一个叫做table大小是16的Entry数组。
2. 这个table数组存储了Entry类的对象。HashMap类有一个叫做Entry的内部类。这个Entry类包含了key-value作为实例变量。我们来看下Entry类的结构。Entry类的结构:
- static
- class
- Entry
- implements
- Map
- .
- Entry
- {
- final
- K key;
- V value;
- Entry next;
- final
- int
- hash;
- ...
- //More code goes here
- } `
3. 每当往hashmap里面存放key-value对的时候,都会为它们实例化一个Entry对象,这个Entry对象就会存储在前面提到的Entry数组table中。现在你一定很想知道,上面创建的Entry对象将会存放在具体哪个位置(在table中的精确位置)。答案就是,根据key的hashcode()方法计算出来的hash值(来决定)。hash值用来计算key在Entry数组的索引。
4. 现在,如果你看下上图中数组的索引10,它有一个叫做HashMap$Entry的Entry对象。
5. 我们往hashmap放了4个key-value对,但是看上去好像只有2个元素!!!这是因为,如果两个元素有相同的hashcode,它们会被放在同一个索引上。问题出现了,该怎么放呢?原来它是以链表(LinkedList)的形式来存储的(逻辑上)。
上面的country对象的key-value的hash值是如何计算出来的。
- Japan的Hash值是95,它的长度是奇数。
India的Hash值是95,它的长度是奇数。
Russia的Hash值是31,它的长度是偶数。
France,它的长度是偶数。
下图会清晰的从概念上解释下链表。
所以,现在假如你已经很好地了解了hashmap的结构,让我们看下put和get方法。
Put :
让我们看下put方法的实现:
- /**
- * 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;
- }
现在我们一步一步来看下上面的代码。
Get:
现在我们来看下get方法的实现:
- /**
- * 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;
- }
当你理解了hashmap的put的工作原理,理解get的工作原理就非常简单了。当你传递一个key从hashmap总获取value的时候:
要牢记以下关键点:
来源: http://blog.csdn.net/qq_37267015/article/details/78730485