HashMap在java中是怎么工作的

大多数人都会同意，HashMap是现在面试题目中最受欢迎的问题，我和我的同事讨论过几次，确实很有帮助，现在，我继续和大家讨论。

在讨论前我假设对HashMap的内在工作原理感兴趣，并且已经理解了基本的概念，所以我跳过了这部分，如果你对概念性的东西一无所知，那么请参照官方的java doc 。

一句话来总结这个答案

如果任何人问我描述一下：”HashMap是如何工作的？”我会简单的回答：“基于哈希的原则工作的”。现在在回答他之前，他必须知道一些基本的哈希概念，对吧！

什么是哈希

哈希在其最简单的形式，是应用任何公式算法之后为任何变量或对象生成独特代码的一种方法。一个真正的哈希函数必须遵循以下的规则： 1、当哈希函数应用在同一个或者相等的函数上的时候，它每次应该返回相同的哈希码。也就是说两个相同的对象必须产生一致的哈希码。 2、所有的java对象默认继承Object类的hashcode()的一个实现，这个函数通常将对象的内部地址转换为整数来产生哈希码，因此对于不同的对象产生了不同的哈希码。
这里有关于hashcode()和equals的介绍：资料

关于Entry Class的一点知识

一个map的定义是：一个对象通过key来找到它的值，很简单是不是？所以在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已经被标记为final，并且还有两个属性next和hash，在我们进行下一步之前，我们要尝试着这些属性的用途。

put()方法到底是什么

在谈到put()的方法实现之前，认识到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是否为空，如果为空的话，它的值存储在table[0]的位置，因为对于null的哈希码一直是0。 2、然后进行下一步，一个哈希值是通过HashCode()方法使用哈希码来计算的，这个哈希值用来计算在存储Entry的对象数组中的索引，JDK的设计者认为一些写的不好的hashcode()函数可能会返回非常高的或者是非常低的哈希值，为了解决这个问题，他们推出了另一个hash()函数，并且把对象的哈希码传递这个函数来产生在数组大小范围内的哈希值。 3、现在来看indexFor(hash, table.length)函数，它是被用来计算存储Entry对象的准确索引位置的。 4、现在这是主要的一个部分，正如我们了解的，两个不同的对象可以有同样的哈希码值，怎么将两个不同的对象存储在同一个数组位置中 [called bucket]，答案是链表，如果你还记得Entry类有一个属性next，这个属性一直指向链中的下一个对象，这正是链表的行为。所以在忧冲突的情况下，Entry对象存储在链表中，当一个Entry对象需要存储在一个特定的位置上的时候，HashMap需要检查这里是否已经有一个Entry，如果没有Entry，Entry对象就会存储在这个位置。如果已经有一个对象计算出来的索引的位置，它的next属性将会被检查，如果为空，则会变为LinkedList的下一个节点，如果下一个值不为空，上边过程将继续执行，直到next为空为止。如果我们增加和之前加入的对象有相同的key的对象该怎么办呢，逻辑上来讲，它应该替换旧值，这是怎么做的呢，在计算完Entry对象的索引位置后，在之前计算完成的索引中迭代，HashMap为每一个Entry对象根据key调用equals()方法，所有在LinkedList中的Entry对象有相似的哈希码，但是equals()方法需要真真正正的相等才行，如果key.equals(k)为真，那么他们将会被对待为同一个key对象。这仅仅会导致Entry对象内的值对象被替换。用这种方式，HashMap确保了keys的唯一性。

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

现在我们了解了键值对是如何存储在HashMap中的，下一个问题就是：当一个对象在HashMap的get方法中传递的时候会发生什么呢，这个值对象是怎么被决定的呢？答案是：我们已经知道了在put()方法中独特的key是如何被决定的，在get()方法中有同样的逻辑，HashMap唯一的确定key对象的时候，将它作为一个参数传递，返回当前存储在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;
}

上边的代码和put()的代码直到 if (e.hash == hash && ((k = e.key) == key || key.equals(k)))都是一样的，然后简单返回值对象

关键注意点

1、存储Entry对象的数据结构是一个类型为Entry的表数组。 2、在数组中特定位置的索引指的是桶，因为它可以保持第一个LinkedList中Entry对象。 3、key对象的hashCode()方法是用来计算Entry对象的索引位置的。 4、key对象的equals()方法是维持key的唯一性的。 5、值对象的hashCode()方法和equals()方法在HashMap的get()和put()方法中不使用。 6、对于null的哈希码一直为0，这样的Entry对象总是存储在Entry[]中的0的位置上。

在java8中的改进

对于HashMap对象有一个性能上的改进，就是当在keys上有大量的冲突的时候，使用平衡树而不是链表来存储map的Entrys。主要的想法就是：一旦一个哈希桶中的条目超过了一定的阙值，这个桶将从使用Entry的链表转为使用一个平衡树，这将最坏的性能由原来的O(n)提高到O(log n)。基本上，当一个桶变得太大的时候（现在是：TREEIFY_THRESHOLD =8），HashMap动态的用一个tree map的 ad-hoc实现替代它，通过这种方式我们是时间复杂度有原来的O(n)提高到O(log n)。树节点的箱（元素或节点）可能会交叉，并且被其他节点使用，但是这却在元素过于密集时提高查找的速度。然而，由于大部分的箱在使用时并不会过剩，这样的检查就可能会导致延迟的发生。树箱主要根据哈希码排序，但是当出现两个元素码值相同的情况时，使用compareTo方法排序。因为树节点的大小是普通节点大小的两倍，因此只有当箱中包含足够多的节点的时候我们才会使用，当他们变小的时候（由于删除等操作）他们要转为扁平的箱（现在是：UNTREEIFY_THRESHOLD=6），在使用均匀分布的用户中很少使用树箱（tree bins）
原文链接：http://fanyi.baidu.com/#en/zh/

秒客网