Java HashMap工作原理

大部分Java开发者都在使用Map,特别是HashMap。HashMap是一种简单但强大的方式去存储和获取数据。但有多少开发者知道HashMap内部如何工作呢?几天前,我阅读了java.util.HashMap的大量源代码(包括Java 7 和Java 8),来深入理解这个基础的数据结构。在这篇文章中,我会解释java.util.HashMap的实现,描述Java 8实现中添加的新特性,并讨论性能、内存以及使用HashMap时的一些已知问题。

内部存储

Java HashMap类实现了Map<K, V>接口。这个接口中的主要方法包括:

  • V put(K key, V value)
  • V get(Object key)
  • V remove(Object key)
  • Boolean containsKey(Object key)

HashMap使用了一个内部类Entry<K, V>来存储数据。这个内部类是一个简单的键值对,并带有额外两个数据:

  • 一个指向其他入口(译者注:引用对象)的引用,这样HashMap可以存储类似链接列表这样的对象。
  • 一个用来代表键的哈希值,存储这个值可以避免HashMap在每次需要时都重新生成键所对应的哈希值。

下面是Entry<K, V>在Java 7下的一部分代码:

static class Entry<K,V> implements Map.Entry<K,V> {
        final K key;
        V value;
        Entry<K,V> next;
        int hash;
…
}

HashMap将数据存储到多个单向Entry链表中(有时也被称为桶bucket或者容器orbins)。所有的列表都被注册到一个Entry数组中(Entry<K, V>[]数组),这个内部数组的默认长度是16。

下面这幅图描述了一个HashMap实例的内部存储,它包含一个nullable对象组成的数组。每个对象都连接到另外一个对象,这样就构成了一个链表。