java - 在具有数百万个对象(具有不同键)的 HashMap 中以 O(1) 时间插入/删除？

Question

我知道使用 Java HashMap 插入/删除可以在 O(1) 时间内完成。

但是，如果我的 HashMap 中有超过一百万个对象(具有不同的键 - 即每个对象都有一个唯一的键)，它仍然是最快的数据结构吗？

Answer 1

TL;DR - 分析您的代码!

HashMap 插入和删除的平均性能为 O(1)(假设您在键上有一个健全的 hashCode() 方法^{1)直到你开始遇到二阶内存效应:}

• 堆越大，垃圾收集所需的时间就越长。一般来说，影响最大的因素是非垃圾对象的数量和大小。足够大的 HashMap 就可以做到这一点......
• 您的硬件的物理内存量有限。如果 JVM 的内存需求增长超过该限制，主机操作系统将在 RAM 和磁盘之间“交换”内存页面。足够大的 HashMap 就可以做到这一点......如果您的堆大小大于 JVM 进程可用的物理 RAM 量。
• 处理器的内存缓存大小和 TLB 缓存大小会产生内存影响。基本上，如果处理器读写内存的“需求”太大，内存系统就会成为瓶颈。大堆和高度非本地化的访问模式可能会加剧这些影响。 (并运行 GC!)

HashMap 的主哈希数组的大小也有大约 2^31 的限制。因此，如果您的条目数量超过 2^31/0.75，则当前 HashMap 实现的性能理论上为 O(N)。然而，我们谈论的是数十亿个条目，二阶内存效应将在此之前对性能产生影响。

<小时/>

^{1 - 如果您的 key 的 hashCode() 函数很差，那么您可能会发现很大一部分 key 散列到相同的代码。如果发生这种情况，这些键的查找、插入和删除性能将是 O(logN) 或 O(N) ...具体取决于键的类型和您的Java版本。在本例中，N 是表中的数字键，其哈希码与您要查找的哈希码相同，等等。}

<小时/>

HashMap 是适合您的用例的最快数据结构吗？

• 如果没有您的用例的更多详细信息，很难说。
• 如果不了解您准备投入多少时间和精力来解决这个问题，就很难说。 (如果您投入足够的编码精力，几乎肯定可以减少几个百分点。也许更多。HashMap 是通用目的。)
• 如果您(首先!)没有进行适当的性能分析，就很难说。

例如，您首先需要确定 HashMap 确实是导致性能问题的原因。当然，您>>认为<<是的，但是您是否真正分析过您的代码以找出答案？除非您这样做，否则您可能会浪费时间来优化不是瓶颈的东西。