HashMap从入门到精通，原创好文，值得收藏！ - InfoQ 写作平台

大多数 JAVA 开发人员都在使用 Maps，尤其是 HashMaps。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 需要时计算哈希。

这是 JAVA 7 中 Entry 实现的一部分：

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

HashMap 将数据存储到多个单向链接的条目列表中（也称为 buckets 或 bins）。所有列表都注册在一个 Entry 数组（Entry<K,V>[] 数组）中，这个内部数组的默认容量是 16。

上图显示了一个带有可空条目数组的 HashMap 实例的内部存储。每个 Entry 可以链接到另一个 Entry 以形成一个链表。

所有具有相同哈希值的键都放在同一个链表（桶）中。具有不同散列值的键可以最终出现在同一个桶中。

当用户调用 put(K key, V value) 或 get(Object key) 时，该函数会计算 Entry 所在的桶的索引。然后，该函数遍历列表以查找具有相同键的条目（使用键的 equals() 函数）。

在 get() 的情况下，该函数返回与条目关联的值（如果条目存在）。

在 put(K key, V value) 的情况下，如果条目存在，则函数将其替换为新值，否则它会在单向链表的头部创建一个新条目（根据参数中的键和值）。

这个 bucket（链表）的索引是由 map 分 3 步生成的：

• 它首先获取密钥的哈希码。

• 它重新散列散列码以防止来自键的错误散列函数将所有数据放在内部数组的同一索引（存储桶）中

• 它采用重新散列的哈希码并用数组的长度（减 1）对其进行位掩码。此操作确保索引不能大于数组的大小。您可以将其视为经过计算优化的模函数。

这是处理索引的 JAVA 7 和 8 源代码：

// the "rehash" function in JAVA 7 that takes the hashcode of the keystatic int hash(int h) {    h ^= (h >>> 20) ^ (h >>> 12);    return h ^ (h >>> 7) ^ (h >>> 4);}// the "rehash" function in JAVA 8 that directly takes the keystatic final int hash(Object key) {    int h;    return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);    }// the function that returns the index from the rehashed hashstatic int indexFor(int h, int length) {    return h & (length-1);}

为了高效工作，内部数组的大小需要是 2 的幂，让我们看看为什么。

假设数组大小为 17，掩码值为 16（大小为 -1）。16 的二进制表示是 0…010000，因此对于任何哈希值 H，使用按位公式“H AND 16”生成的索引将是 16 或 0。这意味着大小为 17 的数组将仅用于 2 个桶：索引 0 的一个和索引 16 的一个，效率不高……

但是，如果您现在采用像 16 这样的 2 的幂的大小，则按位索引公式是“H AND 15”。15 的二进制表示为 0…001111，因此索引公式可以输出 0 到 15 的值，充分利用了大小为 16 的数组。例如：

• 如果 H = 952 ，其二进制表示为 0..0111011 1000，则相关索引为 0…0 1000 = 8

• 如果 H = 1576 其二进制表示为 0..01100010 1000，则相关索引为 0…0 1000 = 8

• 如果 H = 12356146，其二进制表示为 0..010111100100010100011 0010，则相关索引为 0…0 0010 = 2

• 如果 H = 59843，则其二进制表示为 0..0111010011100 0011，关联索引为 0…0 0011 = 3

这就是数组大小是 2 的幂的原因。这种机制对开发者来说是透明的：如果他选择了一个大小为 37 的 HashMap，则 Map 会自动选择 37（64）之后的下一个 2 的幂作为其内部数组的大小。

自动调整大小

获取索引后，函数（get、put 或 remove）访问/迭代关联的链表，以查看是否存在给定键的现有条目。如果不进行修改，此机制可能会导致性能问题，因为该函数需要遍历整个列表以查看条目是否存在。假设内部数组的大小是默认值 (16)，您需要存储 200 万个值。在最好的情况下，每个链表的大小为 125 000 个 entries （2/16 百万）。因此，每个 get()、remove() 和 put() 将导致 125 000 次迭代/操作。为了避免这种情况，HashMap 能够增加其内部数组以保持非常短的链表。

创建 HashMap 时，可以使用以下构造函数指定初始大小和 loadFactor：

public HashMap(int initialCapacity, float loadFactor)

如果不指定参数，则默认 initialCapacity 为 16，默认 loadFactor 为 0.75。initialCapacity 表示内部链表数组的大小。

每次使用 put(...) 在 Map 中添加新键/值时，该函数都会检查是否需要增加内部数组的容量。为此，map 存储了 2 个数据：

• map 的大小：表示 HashMap 中的条目数。每次添加或删除条目时都会更新此值。

• 阈值：它等于（内部数组的容量）* loadFactor，并且在每次调整内部数组大小后刷新

在添加新条目之前，put(...) 检查大小是否大于阈值，如果是，则重新创建一个大小翻倍的新数组。由于新数组的大小发生了变化，索引函数（返回按位运算“hash(key) AND (sizeOfArray-1)”）发生了变化。因此，调整数组大小会创建两倍多的桶（即链表）并将 所有现有条目重新分配到桶中（旧的和新创建的）。

此调整大小操作的目的是减小链表的大小，以便 put()、remove() 和 get() 方法的时间成本保持较低。调整大小后，所有键具有相同哈希值的条目将保留在同一个存储桶中。但是，之前在同一个存储桶中的具有不同哈希键的 2 个条目在转换后可能不在同一个存储桶中。

该图显示了调整内部数组大小之前和之后的表示。在增加之前，为了得到 Entry E，map 必须遍历一个包含 5 个元素的列表。调整大小后，相同的 get() 只是遍历 2 个元素的链表，调整大小后 get() 的速度提高了 2 倍！

注意：HashMap 只增加内部数组的大小，它没有提供减少它的方法。

如果您已经了解 HashMaps，您就知道它不是线程安全的，但为什么呢？例如，假设您有一个仅将新数据放入 Map 的 Writer 线程和一个从 Map 读取数据的 Reader 线程，为什么它不工作？

因为在自动调整大小机制期间，如果一个线程试图放置或获取一个对象，映射可能会使用旧的索引值并且不会找到条目所在的新存储桶。

最坏的情况是当 2 个线程同时放置数据并且 2 个 put() 调用同时调整 Map 的大小时。由于两个线程同时修改链表，因此 Map 最终可能会在其链表之一中出现内部循环。如果您尝试使用内部循环获取列表中的数据，则 get() 将永远不会结束。

该哈希表的实现是线程安全的实现，从这种情况下阻止。但是，由于所有 CRUD 方法都是同步的，所以这个实现非常慢。例如，如果线程 1 调用 get(key1)，线程 2 调用 get(key2)，线程 3 调用 get(key3)，则一次只有一个线程能够获取其值，而其中 3 个线程可以访问数据同时。

自 JAVA 5 以来，存在线程安全 HashMap 的更智能实现：ConcurrentHashMap。只有存储桶是同步的，因此如果不意味着访问同一个存储桶或调整内部数组的大小，则多个线程可以同时 get()、remove() 或 put() 数据。最好在多线程应用程序中使用此实现。

密钥不变性

为什么字符串和整数是 HashMap 键的一个很好的实现？主要是因为它们是不可变的！如果您选择创建自己的 Key 类并且不使其不可变，则可能会丢失 HashMap 中的数据。

看下面的用例：

• 您有一个内部值为“1”的键

• 你用这个键在 HashMap 中放置了一个对象

• HashMap 从 Key 的 hashcode 生成一个 hash（所以从“1”开始）

• Map 将此哈希存储 在新创建的 Entry 中

• 您将键的内部值修改为“2”

• key 的 hash 值被修改了但是 HashMap 不知道（因为存储了旧的 hash 值）

• 您尝试使用修改后的密钥获取对象

• 映射计算您的键的新散列（因此从“2”开始）以查找条目在哪个链表（存储桶）中

• 案例 1：由于您修改了您的密钥，因此地图尝试在错误的存储桶中查找条目，但未找到

• 情况 2：幸运的是，修改后的密钥生成与旧密钥相同的存储桶。然后映射遍历链表以找到具有相同键的条目。但是为了找到键，映射首先比较哈希值，然后调用 equals() 比较。由于您修改的键与旧的哈希值（存储在条目中）不具有相同的哈希值，因此映射不会在链表中找到该条目。

这是 Java 中的一个具体示例。我在我的 Map 中放置了 2 个键值对，我修改了第一个键，然后尝试获取这 2 个值。仅从映射返回第二个值，第一个值在 HashMap 中“丢失”：

public class MutableKeyTest {    public static void main(String[] args) {        class MyKey {            Integer i;            public void setI(Integer i) {                this.i = i;            }            public MyKey(Integer i) {                this.i = i;            }            @Override            public int hashCode() {                return i;            }            @Override            public boolean equals(Object obj) {                if (obj instanceof MyKey) {                    return i.equals(((MyKey) obj).i);                } else                    return false;            }        }        Map<MyKey, String> myMap = new HashMap<>();        MyKey key1 = new MyKey(1);        MyKey key2 = new MyKey(2);        myMap.put(key1, "test " + 1);        myMap.put(key2, "test " + 2);        // modifying key1        key1.setI(3);        String test1 = myMap.get(key1);        String test2 = myMap.get(key2);        System.out.println("test1= " + test1 + " test2=" + test2);    }}

输出为：“test1= null test2=test 2”。正如预期的那样，Map 无法使用修改后的键 1 检索字符串 1。

JAVA 8 改进

HashMap 的内部表示在 JAVA 8 中发生了很大变化。确实，JAVA 7 中的实现需要 1k 行代码，而 JAVA 8 中的实现需要 2k 行。除了条目的链接列表之外，我之前所说的大部分内容都是正确的。在 JAVA8 中，您仍然有一个数组，但它现在存储的节点包含与条目完全相同的信息，因此也是链表：

下面是 JAVA 8 中 Node 实现的一部分：

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

那么与 JAVA 7 有什么大的不同呢？节点可以扩展到树节点,TreeNode 是一种红黑树结构，它存储了更多的信息，以便它可以在 O(log(n)) 中添加、删除或获取元素。

仅供参考，这里是存储在 TreeNode 中的数据的详尽列表

static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {    final int hash; // inherited from Node<K,V>    final K key; // inherited from Node<K,V>    V value; // inherited from Node<K,V>    Node<K,V> next; // inherited from Node<K,V>    Entry<K,V> before, after;// inherited from LinkedHashMap.Entry<K,V>    TreeNode<K,V> parent;    TreeNode<K,V> left;    TreeNode<K,V> right;    TreeNode<K,V> prev;    boolean red;

红黑树是自平衡二叉搜索树。它们的内部机制确保它们的长度总是在 log(n) 中，尽管有新的节点添加或删除。使用这些树的主要优点是在许多数据位于内部表的同一索引（存储桶）中的情况下，树中的搜索将花费 O(log(n))而它将花费 O(n)带有链表。

如您所见，树确实比链表占用更多空间

通过继承，内表可以同时包含 Node（链表）和 TreeNode（红黑树）。Oracle 决定根据以下规则使用这两种数据结构：

• 如果对于内表中的给定索引（bucket）有超过 8 个节点，则链表被转换为红黑树

• 如果对于给定索引（bucket） ) 内表中的节点少于 6 个，将树转化为链表

此图显示了 JAVA 8 HashMap 的内部数组，其中包含树（在桶 0）和链表（在桶 1,2 和 3）。Bucket 0 是一棵树，因为它有 8 个以上的节点。

java7

使用 HashMap 会带来内存成本。在 JAVA 7 中，HashMap 将键值对包装在条目中。一个条目有：

• 对下一个条目的引用

• 预先计算的散列（整数）

• 对密钥的引用

• 对值的引用

此外，JAVA 7 HashMap 使用 Entry 的内部数组。假设一个 JAVA 7 HashMap 包含 N 个元素，其内部数组有一个容量 CAPACITY，额外的内存成本约为：

sizeOf(integer)* N + sizeOf(reference)* (3*N+C)

where：

• 整数的大小取决于等于 4 个字节

• 引用的大小取决于 JVM/OS/处理器，但通常为 4 个字节。

• 这意味着开销通常是 16 * N + 4 * CAPACITY 字节

提醒：在 Map 自动调整大小后，内部数组的 CAPACITY 等于 N 之后的下一个 2 的幂。

注意：从 JAVA 7 开始，HashMap 类有一个惰性初始化。这意味着即使您分配了一个 HashMap，条目的内部数组（花费 4 * CAPACITY 字节）也不会在内存中分配，直到第一次使用 put() 方法。

java8

使用 JAVA 8 实现，获取内存使用情况变得有点复杂，因为节点可以包含与条目相同的数据或相同的数据加上 6 个引用和一个布尔值（如果它是 TreeNode）。

如果所有节点都只有 Nodes，那么 JAVA 8 HashMap 的内存消耗和 JAVA 7 HashMap 是一样的。

如果所有节点都是 TreeNodes，一个 JAVA 8 HashMap 的内存消耗变为：

N * sizeOf(integer) + N * sizeOf(boolean) + sizeOf(reference)* (9*N+CAPACITY )

在大多数标准 JVM 中，它等于 44 * N + 4 * CAPACITY 字节

倾斜的 HashMap 与平衡良好的 HashMap

在最好的情况下，get() 和 put() 方法的时间复杂度为 O(1)。但是，如果您不注意键的散列函数，则可能会以非常慢的 put() 和 get() 调用结束。put() 和 get 的良好性能取决于将数据重新分区到内部数组（桶）的不同索引中。如果您的密钥的哈希函数设计不当，您将有一个偏斜的重新分区（无论内部数组的容量有多大）。所有使用最大条目链表的 put() 和 get() 都会很慢，因为它们需要迭代整个列表。在最坏的情况下（如果大多数数据都在同一个桶中），您最终可能会得到 O(n) 的时间复杂度。

这是一个视觉示例。第一张图显示倾斜的 HashMap，第二张图显示平衡良好的图。

在这种倾斜的 HashMap 的情况下，桶 0 上的 get()/put() 操作成本很高。获得条目 K 将花费 6 次迭代

在这种平衡良好的 HashMap 的情况下，获得 Entry K 将花费 3 次迭代。两个 HashMap 存储相同数量的数据并具有相同的内部数组大小。唯一的区别是散列（键的）函数，它在存储桶中分配条目。

这是 JAVA 中的一个极端示例，我创建了一个哈希函数，将所有数据放在同一个存储桶中，然后添加 200 万个元素。

public class Test {    public static void main(String[] args) {        class MyKey {            Integer i;            public MyKey(Integer i){                this.i =i;            }            @Override            public int hashCode() {                return 1;            }            @Override            public boolean equals(Object obj) {            …            }        }        Date begin = new Date();        Map <MyKey,String> myMap= new HashMap<>(2_500_000,1);        for (int i=0;i<2_000_000;i++){            myMap.put( new MyKey(i), "test "+i);        }        Date end = new Date();        System.out.println("Duration (ms) "+ (end.getTime()-begin.getTime()));    }}

在我的核心 i5-2500k @ 3.6Ghz 上，使用 java 8u40 需要超过 45 分钟（我在 45 分钟后停止了该过程）。

现在，如果我运行相同的代码，但这次我使用以下哈希函数

  @Override    public int hashCode() {        int key = 2097152-1;        return key+2097152*i;}

它需要 46 秒，这更好！这个散列函数比前一个具有更好的重新分区，因此 put() 调用更快。

如果我使用以下哈希函数运行相同的代码，该函数提供了更好的哈希重新分区

@Overridepublic int hashCode() {return i;}

现在需要 2 秒。

我希望你意识到哈希函数的重要性。如果在 JAVA 7 上运行相同的测试，第一种和第二种情况的结果会更糟（因为 put 的时间复杂度是 JAVA 7 中的 O(n) 与 JAVA 8 中的 O(log(n))）

使用 HashMap 时，您需要为您的键找到一个散列函数，将键分布到尽可能多的桶中。为此，您需要避免哈希冲突。String 对象是一个很好的键，因为它具有很好的散列函数。整数也很好，因为它们的哈希码是它们自己的值。

如果需要存储大量数据，则应创建初始容量接近预期容量的 HashMap。

如果不这样做，Map 将采用默认大小 16，factorLoad 为 0.75。第 11 个 put() 将非常快，但第 12 个 (16*0.75) 将重新创建一个新的内部数组（及其关联的链表/树），新容量为 32。第 13 到 23 将很快，但第 24 (32*0.75) 将重新创建（再次）一个昂贵的新表示，使内部数组的大小加倍。内部调整大小操作将出现在 put() 的第 48、96、192、... 调用处。在低音量下，内部阵列的完全重建很快，但在高音量下可能需要几秒钟到几分钟。通过最初设置您的预期大小，您可以避免这些 昂贵的操作。

但是有一个缺点：如果你设置了一个非常高的数组大小，比如 2^28 而你在你的数组中只使用 2^26 个桶，你将浪费大量内存（在这种情况下大约 2^30 个字节）。

对于简单的用例，您不需要知道 HashMaps 是如何工作的，因为您看不到 O(1) 和 O(n) 或 O(log(n)) 操作之间的区别。但是理解最常用的数据结构之一的底层机制总是更好。此外，对于 Java 开发人员职位，这是一个典型的面试问题。

在高容量情况下，了解它的工作原理和了解密钥散列函数的重要性变得很重要。

希望这篇文章能帮助你深入了解 HashMap 的实现。