HashMap如何工作 - Java

简书 賈小強
转载请注明原创出处，谢谢！

大多数人应该会同意HashMap是现在面试最喜欢问的主题之一。我和同事常常进行讨论，并很有帮助。现在，我继续和大家讨论。

我假设你对HashMap的内部工作原理感兴趣，并且你已经知道基本的HashMap使用，所以我跳过这部分。但如果HashMap的概念你觉得很新，那么参考官方 Java docs。
在继续之前，我强烈建议你阅读我以前的帖子：使用hashCode()和equals()方法 - Java

本文包括如下内容：

• 一句话回答
• 什么是Hashing？
• 关于Entry类
• put()方法到底干了什么
• get()方法内部是如何工作的
• 注意事项
• [更新 ] Java8改进

一句话回答

如果有人问我“描述下HashMap怎么工作的？我会简单地回答：“按Hash原理”，如此简单而已。但要详细回答这个问题，那么你必须非常清楚地知道Hash的基本知识，对吗？？

什么是Hashing

最简单形式的散列（Hashing）是一种根据任何变量/对象对其属性，应用任何公式/算法后分配一个独特的数字的方法。一个真正的散列函数必须遵循以下规则：

当函数在相同或相等的对象上应用时，哈希函数应该每次返回相同的哈希码。换句话说，两个相等的对象必须一致地生成相同的哈希码。

所有Java中的对象都从Object类继承一个默认得hashCode()方法实现。这个函数通过将对象的内部地址转换成整数来产生哈希码，从而为所有不同的对象生成不同的哈希码。

关于Entry类

Map的定义是：“一个将key映射到value的对象”。很容易..对吗？
因此，必然在HashMap类中有一些机制存储键值对。回答是肯定的，HashMap有一个内部类Entry，它看起来像这样：

static class Entry<K ,V> implements Map.Entry<K ,V>
{
    final K key;
    V value;
    Entry<K ,V> next;
    final int hash;
    ...//More code goes here
}

Entry类具有key和value的映射，并作为字段存储。key已被标记为final，另外它还有两个别的字段：next和hash。在下面，我们将努力理解为什么需要这些字段。

put()方法到底干了什么

理解put()方法的实现之前，先需要知道Entry类型的对象存储在一个Entry类型数组中。HashMap类如下定义这个数组：

/**
 * The table, resized as necessary. Length MUST Always be a power of two.
 */
transient Entry[] table;

现在看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;
}

让我们逐一解释以上步骤：

1. 首先，检查key是否为null。如果key为null，则将value存储在table[0]。因为null的哈希码总是0。
2. 然后，通过调用key的hashCode()方法得到一个哈希码。此哈希码用于计算Entry对象存储在Entry[]数组中的索引。JDK的设计师认为，可能有一些写得不好的hashCode()函数可以返回非常高或低的哈希码。为了解决这个问题，他们推出了另一hash()函数，并通过将key对象的哈希码传给这个hash()函数，从而在数组索引的大小范围获得哈希码。
3. 现在，indexFor(hash, table.length)函数被用来计算存储Entry对象的准确索引位置。
4. 现在，来到for循环部分。正如我们所知道的，两个不等的对象可以有相同的哈希码，两个不同的对象如何存储在同一个数组位置（称为桶）。

答案是LinkedList。如果您记得，Entry类有一个属性“next”。这个属性总是指向链中的下一个对象。这正是链表的行为。

因此，在发生碰撞的时候，Entry对象以链表的形式存储。当一个Entry对象需要存储在特定的索引位置，HashMap检查是否已经有一个Entry了？如果没有存在，那么Entry对象存储在这个位置。

如果已经有一个Entry对象存储在所计算的索引位置上，那么它的next属性就被检查了。如果它为null，那么当这个Entry对象成为LinkedList的下一个节点。如果下一个变量不是null，则继续执行该过程，直到下一个位置的值为null为止。

如果我们增加一个key和value到和之前Entry对象相同的对象呢？从逻辑上说，它会取代旧value。它是怎么做的？好了，首先确定Entry对象的储存的索引位置后，对在链表中的每个对象，调用它们的equal()方法。LinkedList上的所有这些Entry对象将有类似的哈希码，但equals()方法将测试它们是否真的相等。如果key.equals(k)为真，则这两个键被视为同一个键对象。这将导致只替换Entry对象中的value对象。

也就说hashCode()方法在名叫table的Entry数组上找位置，equal()方法在桶链表上找位置

通过这样，HashMap保证了所有键的唯一性。

get()方法内部是如何工作的

现在我们知道了键值对(key-value pairs)怎么存储在HashMap中的。接下来的问题是：当一个对象被传递给HashMap的get方法发生了什么？值对象是如何确定返回的？

答案我们已经知道，正如在put()法中唯一键的确定的方式，同样的逻辑应用于get()方法中。HashMap根据传递的对象作作为键，精确匹配，它只是返回存储于当前Entry对象中的值。

如果没有发现匹配，get()方法返回null。

让我们看看代码：

/**
* 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;
}

注意事项

1. 存储Entry对象的数据结构是一个名为table的Entry类型数组。
2. 数组在特定位置的索引被称为桶，因为它可以保存一个Entry类型对象链表的第一个元素。
3. Key对象需要hashCode()方法，用于计算Entry对象的存放索引位置。
4. Key对象的equals()法用来确保key在Map中的唯一性。
5. Value对象的的hashCode()和equals()方法在HashMap的get()和put()方法中不会被使用。
6. null键的哈希代码总是0，而对应的Entry对象总是存储在Entry数组的零索引位置。

[更新]Java 8改进

作为JEP 180的一部分，有一个对HashMap的性能改进，假如key对象有许多碰撞，则使用平衡树而不是链表来存储Entry对象。其主要思想是，一旦哈希桶中的项目数量超出某个阈值时，该桶将从使用链接切换到使用平衡树。在hash高碰撞的情况下，这将把最坏情况下的性能从O（n）改善到O（log n）。

基本上，当一桶太大（目前：treeify_threshold = 8），HashMap用tree map动态替换它。这样就不再是O（n），到是更好的O（log n）。

我希望通过这篇文章我能正确地表达我的想法。如果您发现有任何差异或需要任何帮助，请发表评论。

Happy Learning !!