[转] Java HashMap 的工作原理

发表于 | 分类于 | | 阅读次数

本文转载自 ImportNew - miracle1919, 翻译自 javacodegeeks。

面试的时候经常会遇见诸如：“Java 中的 HashMap 是怎么工作的”，“HashMap 的 get 和 put 内部的工作原理”这样的问题。本文将用一个简单的例子来解释下 HashMap 内部的工作原理。首先我们从一个例子开始，而不仅仅是从理论上，这样，有助于更好地理解，然后，我们来看下 get 和 put 到底是怎样工作的。

我们来看个非常简单的例子。有一个“国家”（Country）类，我们将要用 Country 对象作为 key，它的首都的名字（String 类型）作为 value。下面的例子有助于我们理解 key-value 对在 HashMap 中是如何存储的。

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
44
45
46
47
48
49
50
51
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) {
        if(this == obj) {
            return true;
        }
        if(null == obj || !(obj instanceof Country)) {
            return false;
        }
        Country other = (Country) obj;
        if (name.equalsIgnoreCase((other.name)))
            return true;
        return false;
    }
}

HashMapStructure.java (main class)

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
import java.util.HashMap;
import java.util.Iterator;
public class HashMapStructure {
    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);
        }
    }
}

现在，在 Iterator… 这行设置一个断点，在项目上右击 -> 调试运行 -> java应用。程序会停在这行，然后在 countryCapitalMap 上右击，选择“查看”（watch）。将会看到如下的结构：

从上图可以观察到以下几点：

1、有一个叫做 table 大小是 16 的 Entry 数组。

2、这个 table 数组存储了 Entry 类的对象。HashMap 类有一个叫做 HashMapEntry 的内部类实现了 Entry 接口。这个 HashMapEntry 类包含了 key-value 作为实例变量。

我们看下 HashMapEntry 类的结构：

1
2
3
4
5
6
7
static class HashMapEntry<K, V> implements Entry<K, V> {
    final K key;
    V value;
    final int hash;
    HashMapEntry<K, V> next;
    ...//More code goes here
}

1、每当往 Hashmap 里面存放 key-value 对的时候，都会为它们实例化一个 Entry 对象，这个 Entry 对象就会存储在前面提到的 Entry 数组 table 中。现在你一定很想知道，上面创建的 Entry 对象将会存放在具体哪个位置（在 table 中的精确位置）。答案就是，根据 key 的 hashcode() 方法计算出来的 hash 值（来决定）。hash 值用来计算 key 在 Entry 数组的索引。

2、现在，如果你看上图数组的索引 10，它有个 HashMap$Entry 的 Entry 对象。

3、我们往 Hashmap 放了 4 个 key-value 对，但是看上去好像只有 2 个元素！！！这是因为，如果两个元素有相同的 hashcode，他们会被放在同一个索引上。它是以链表（LinkedList）的形式来存储的（逻辑上）。

所以上面的 Country 对象的 key-value 的 hashcode 值是如何计算出来的：

hashCode for Japan = 95，因为它的长度为奇数

hashCode for India = 95，因为它的长度为奇数

hashCode for Russia = 31，因为它的长度为偶数

hashCode for France = 31，因为它的长度为偶数

下面这图会清晰地从解释下链表：

所以，现在假如你已经很好地了解了 Hashmap 的结构，让我们看下 put 和 get 方法。

Put

让我们看下 put 方法的实现：

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
/**
 * Maps the specified key to the specified value.
 *
 * @param key
 *            the key.
 * @param value
 *            the value.
 * @return the value of any previous mapping with the specified key or
 *         {@code null} if there was no such mapping.
 */
@Override public V put(K key, V value) {
    if (key == null) {
        return putValueForNullKey(value);
    }
    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    int index = hash & (tab.length - 1);
    for (HashMapEntry<K, V> e = tab[index]; e != null; e = e.next) {
        if (e.hash == hash && key.equals(e.key)) {
            preModify(e);
            V oldValue = e.value;
            e.value = value;
            return oldValue;
        }
    }
    // No entry for (non-null) key is present; create one
    modCount++;
    if (size++ > threshold) {
        tab = doubleCapacity();
        index = hash & (tab.length - 1);
    }
    addNewEntry(key, value, hash, index);
    return null;
}
1
2
3
4
5
6
7
8
9
/**
 * Creates a new entry for the given key, value, hash, and index and
 * inserts it into the hash table. This method is called by put
 * (and indirectly, putAll), and overridden by LinkedHashMap. The hash
 * must incorporate the secondary hash function.
 */
void addNewEntry(K key, V value, int hash, int index) {
    table[index] = new HashMapEntry<K, V>(key, value, hash, table[index]);
}

现在我们一步一步来看上面的代码。

  1. 对 key 做 null 检查。如果 key 是 null，会被存储到 table[0]，因为 null 的 hash 值总是 0。

  2. key 的 hashCode() 方法会被调用，然后二次计算 hash 值。hash 值用来找到存储 Entry 对象的数组的索引。有时候 hash 函数可能写的很不好，所以 JDK 的设计者添加了另外一个叫做 hash() 的方法，它接收刚才计算的 hash 值作为参数。如果你想了解更多关于 hash() 函数的东西，可以参考：Hashmap 中的 hash 和 indexFor 方法

  3. 然后 for 循环用来寻找有没 hash 值相同且 key 也 equals 的对象，如果有就会用当前 Entry 的 value 来替换之前 value。

  4. 如果这时 Hashmap 的 size 已经慢，就会将自身容量变为 2 倍

  5. 从 addNewEntry 方法中观察，它是先把当前的 key-value 对创建一个 HashMapEntry，其中 next 指向原来的 table[index]，在重新赋值给 table[index]，这样两个 hash 值相同的 key 就以链表的形式存储起来了。

Get

现在我们看下 get 方法的实现：

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
/**
 * Returns the value of the mapping with the specified key.
 *
 * @param key
 *            the key.
 * @return the value of the mapping with the specified key, or {@code null}
 *         if no mapping for the specified key is found.
 */
public V get(Object key) {
    if (key == null) {
        HashMapEntry<K, V> e = entryForNullKey;
        return e == null ? null : e.value;
    }
    int hash = Collections.secondaryHash(key);
    HashMapEntry<K, V>[] tab = table;
    for (HashMapEntry<K, V> e = tab[hash & (tab.length - 1)];
            e != null; e = e.next) {
        K eKey = e.key;
        if (eKey == key || (e.hash == hash && key.equals(eKey))) {
            return e.value;
        }
    }
    return null;
}

当你了解 Hashmap 的 put 的工作原理了，理解 get 的工作原理就非常简单了。

  1. 对 key 进行 null 检查。如果 key 是 null，那么将返回 table[0] 位置的元素。

  2. 根据 key 的 hashCode() 方法计算 hash 值。

  3. 然后根据 hash 值就确定在 table 数组的精确位置。

  4. 在确定索引之后，会迭代链表，判断 key 的引用是否相同，或者调用 equals 方法检查，如果为 true，则返回 Entry 对象的 value，否则，返回 null。

要牢记以下关键点：

1、HashMap 有一个叫做 HashMapEntry 的内部类，它用来存储 key-vallue 对。

2、上面的 HashMapEntry 对象是存储在一个叫做 table 的 Entry 数组中

3、table 的索引在逻辑上叫做”桶“（bucket），它存储了链表的第一个元素。

4、key 的 hashCode() 方法经过二次计算用来确定 HashMapEntry 对象所在的桶，即在 table 数组上的索引。

5、如果两个不同的 key 的 hash 值相同，它们会被放在 table 数组的同一个桶里。

6、key 的 equals 方法用来确保 key 的唯一性。

7、value 对象的 equals() 和 hashCode() 在 Hashmap 中没有用到。

END
Johnny Shieh wechat
我的公众号，不只有技术，还有咖啡和彩蛋！