为什么是阵列。HashMap中未使用fill（）。清除（）了吗？

Question

我注意到HashMap.clear（）的实现有些奇怪。这是它在OpenJDK 7u40中的样子：

public void clear() {
    modCount++;
    Arrays.fill(table, null);
    size = 0;
}

这是OpenJDK 8u40的外观：

public void clear() {
    Node<K,V>[] tab;
    modCount++;
    if ((tab = table) != null && size > 0) {
        size = 0;
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

我知道现在table可以为空以清空map，因此需要在局部变量中进行额外的检查和缓存。但是为什么Arrays.fill（）被替换为for循环？

这项更改似乎是在这次提交中引入的。不幸的是，我没有找到解释为什么普通for循环可能比数组更好。填充（）。速度快吗？还是更安全？

Answer 1

匿名用户

我要在黑暗中拍摄...

我的猜测是，它可能已经被更改，以便为专门化（即泛型而非基本类型）奠定基础。也许（我坚持认为可能），如果专业化是JDK的一部分，那么这个更改旨在使向Java 10的转换更容易。

如果查看专门化文档的状态“语言限制”部分，它会显示以下内容：

由于任何类型变量都可以采用值类型和引用类型，因此涉及此类类型变量的类型检查规则（以下简称“avars”）。例如，对于avar T：

• 无法将null转换为类型为T的变量
• 无法将T与null进行比较
• 无法将T转换为对象
• 无法将T[]转换为对象[]

（重点是我的）。

在前面的Specializer转换部分中，它说：

当专门化任何泛型类时，专门化器将执行许多转换，大多数是本地化的，但有些转换需要类或方法的全局视图，包括：

后来，在文件的末尾，在进一步调查部分，它说：

虽然我们的实验已经证明这种方式的专业化是实用的，但还需要更多的研究。具体来说，我们需要针对任何核心JDK库，特别是集合和流，执行许多有针对性的实验。

现在，关于变化。。。

如果<代码>数组。fill（Object[]array，Object value）方法将被专门化，然后其签名应更改为数组。填充（T[]数组，T值）。然而，这种情况在（已经提到的）语言限制部分中有明确列出（它将违反强调的项目）。因此，可能有人认为最好不要在HashMap中使用它。clear（）方法，尤其是当值为空时。

Answer 2

因为速度快得多！

我对这两种方法的精简版本进行了一些彻底的基准测试：

void jdk7clear() {
    Arrays.fill(table, null);
}

void jdk8clear() {
    Object[] tab;
    if ((tab = table) != null) {
        for (int i = 0; i < tab.length; ++i)
            tab[i] = null;
    }
}

对包含随机值的各种大小的数组进行操作。以下是（典型的）结果：

Map size |  JDK 7 (sd)|  JDK 8 (sd)| JDK 8 vs 7
       16|   2267 (36)|   1521 (22)| 67%
       64|   3781 (63)|   1434 ( 8)| 38%
      256|   3092 (72)|   1620 (24)| 52%
     1024|   4009 (38)|   2182 (19)| 54%
     4096|   8622 (11)|   4732 (26)| 55%
    16384|  27478 ( 7)|  12186 ( 8)| 44%
    65536| 104587 ( 9)|  46158 ( 6)| 44%
   262144| 445302 ( 7)| 183970 ( 8)| 41%

下面是在充满null的数组上操作时的结果（这样就消除了垃圾收集问题）：

Map size |  JDK 7 (sd)|  JDK 8 (sd)| JDK 8 vs 7
       16|     75 (15)|     65 (10)|  87%
       64|    116 (34)|     90 (15)|  78%
      256|    246 (36)|    191 (20)|  78%
     1024|    751 (40)|    562 (20)|  75%
     4096|   2857 (44)|   2105 (21)|  74%
    16384|  13086 (51)|   8837 (19)|  68%
    65536|  52940 (53)|  html" target="_blank">36080 (16)|  68%
   262144| 225727 (48)| 155981 (12)|  69%

数字以纳秒为单位，（sd）为1均方差，表示为结果的百分比（仅供参考，“正态分布”总体的SD为68），vs是JDK 8相对于JDK 7的计时。

有趣的是，它不仅速度明显更快，而且偏差也略小，这意味着JDK 8实现提供了更一致的性能。

这些测试在jdk 1.8.0\u 45上运行了大量（数百万）次，在填充了随机<代码>整数 对象的数组上运行。为了消除虚假数字，在每组结果中，最快和最慢的3%的计时被丢弃。请求了垃圾收集，线程在运行方法的每次调用之前生成并Hibernate。JVM预热是在前20%的工作中完成的，这些结果被丢弃。

Answer 3

我将试图总结评论中提出的三个更不合理的版本。

@霍尔格说：

我想这是为了避免java类。util。此方法的副作用是数组正在加载。对于应用程序代码，这通常不是一个问题。

这是最容易测试的东西。让我们编译这样的程序：

public class HashMapTest {
    public static void main(String[] args) {
        new java.util.HashMap();
    }
}

使用java-verbose:class-HashMapTest运行它。这将在类加载事件发生时打印它们。使用JDK 1.8.0\u 60，我看到加载了400多个类：

... 155 lines skipped ...
[Loaded java.util.Set from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.AbstractSet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptySet from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$EmptyMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableCollection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.Collections$UnmodifiableRandomAccessList from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.Reflection from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.HashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.HashMap$Node from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$3 from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$ReflectionData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$Atomic from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.AbstractRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.GenericDeclRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.generics.repository.ClassRepository from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.Class$AnnotationData from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.annotation.AnnotationType from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.util.WeakHashMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.ClassValue$ClassValueMap from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.Modifier from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded sun.reflect.LangReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
[Loaded java.lang.reflect.ReflectAccess from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
**[Loaded java.util.Arrays from C:\Program Files\Java\jre1.8.0_60\lib\rt.jar]
...

如您所见，HashMap在应用程序代码之前加载很久，而Arrays在HashMap之后仅加载14个类。加载HashMap由sun触发。反映反射初始化，因为它具有静态字段。数组加载可能由实际具有数组的WeakHashMap加载触发。在清除方法中填写。WAKHASHMAP加载由java触发。lang.ClassValue$ClassValueMap，它扩展了WeakHashMap。每个java中都有ClassValueMap。lang.Class实例。因此，在我看来，如果没有数组类，JDK根本无法初始化。此外，静态初始化器非常短，它只初始化断言机制。这种机制在许多其他类中使用（例如，包括很早加载的java.lang.Throwable）。java中不执行其他静态初始化步骤。util。阵列。因此，霍尔格版本在我看来是不正确的。

在这里我们还发现了非常有趣的事情。WeakHashMap。clear（）仍使用数组。填充。当它出现在那里时很有趣，但不幸的是，这要追溯到史前时代（它已经存在于第一个公开的OpenJDK存储库中）。

接下来，@MarcoTopolnik说：

当然不会更安全，但如果填充调用没有内联并且选项卡很短，则可能会更快。在HotSpot上，循环和显式的fill调用都将产生一个快速的编译器内部（在欢乐日场景中）。

实际上，我很惊讶数组。填充不是直接内部化的（请参见@apangin生成的内部列表）。似乎JVM可以识别和向量化这样的循环，而无需显式的内部处理。因此，在非常特定的情况下（例如，如果达到了MaxInlineLevel限制），可以不内联额外的调用。另一方面，这种情况非常罕见，它只是一个调用，不是循环内的调用，而且是静态的，不是虚拟的/接口调用，因此性能改进可能只是微不足道的，而且仅在某些特定场景中。JVM开发人员通常并不关心这件事。

还应该注意的是，即使C1“客户端”编译器（第1-3层）也能够内联<代码>数组。例如，在WeakHashMap中调用fill。clear（），因为内联日志（-XX:UnlockDiagnosticVMOptions-XX:PrintCompilation-XX:PrintInline）显示：

36       3  java.util.WeakHashMap::clear (50 bytes)
     !m        @ 4   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 28   java.util.Arrays::fill (21 bytes)
     !m        @ 40   java.lang.ref.ReferenceQueue::poll (28 bytes)
                 @ 17   java.lang.ref.ReferenceQueue::reallyPoll (66 bytes)   callee is too large
               @ 1   java.util.AbstractMap::<init> (5 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
               @ 9   java.lang.ref.ReferenceQueue::<init> (27 bytes)   inline (hot)
                 @ 1   java.lang.Object::<init> (1 bytes)   inline (hot)
                 @ 10   java.lang.ref.ReferenceQueue$Lock::<init> (5 bytes)   unloaded signature classes
               @ 62   java.lang.Float::isNaN (12 bytes)   inline (hot)
               @ 112   java.util.WeakHashMap::newTable (8 bytes)   inline (hot)

当然，它也很容易被智能而强大的C2“服务器”编译器内联。因此我在这里没有看到任何问题。似乎@Marco版本也不正确。

最后，我们有一些来自@StuartMarks（他是JDK开发人员，因此是一些官方声音）的评论：

有趣的我的直觉是这是一个错误。此变更集的审阅线程位于此处，它引用了在此继续的早期线程。早期线程中的初始消息指向HashMap的原型。Doug Lea的CVS存储库中的java。我不知道这是从哪里来的。它似乎与OpenJDK历史中的任何内容都不匹配。

...无论如何，它可能是一些旧的快照；for循环在Clear（）方法中已经存在很多年了。Arrays.fill（）调用是由这个变更集引入的，所以它在树中只存在了几个月。还要注意，这个变更集引入的基于Integer.highestOneBit（）的二次方计算也同时消失了，尽管这一点在审查期间被注意到但被驳回了。嗯。

事实上，HashMap.clear（）包含循环多年，在2013年4月10日被Arrays.fill替换，并且在9月4日引入讨论的提交之前停留了不到半年。讨论的提交实际上是对HashMap内部结构的重大重写，以修复JDK-8023463问题。关于用具有重复哈希码的键毒害HashMap的可能性，这是一个很长的故事，将HashMap搜索速度降低到线性，使其容易受到DoS攻击。解决这个问题的尝试是在JDK-7中执行的，包括String hashCode的一些随机化。因此，HashMap实现似乎是从早期提交中分叉出来的，独立开发，然后合并到master分支中，覆盖了其间引入的几个更改。

我们可以支持这个假设执行差异。取删除Arrays.fill的版本（2013-09-04)并将其与以前的版本（2013-07-30)进行比较。diff-U0输出有4341行。现在让我们与添加Arrays.fill时的之前版本进行比较（2013-04-01)。现在diff-U0仅包含2680行。因此，较新的版本实际上更类似于较旧的版本而不是直接的父版本。

结论

最后，我同意斯图亚特·马克斯的观点。没有具体的理由删除数组。填充，这只是因为中间的更改被错误地覆盖了。使用数组。fill在JDK代码和用户应用程序中都非常好，例如在WeakHashMap中使用。在JDK初始化过程中，很早就加载了数组类，它有非常简单的静态初始值设定项和数组。即使客户端编译器也可以轻松地内联fill方法，所以不应注意性能缺陷。