我知道插入/删除在 O(1) 时间内与 Java HashMap 一起工作。
但是，如果我的 HashMap 中有超过一百万个对象(具有不同的键 - 即每个对象都有一个唯一的键)，它仍然是最快的数据结构吗？
TL;DR - 分析您的代码！
HashMap插入和删除的平均性能按O(1)缩放(假设您在键1上有一个声音 hashCode() 方法)，直到您开始遇到二阶内存效应：
- 堆越大，垃圾回收所需的时间就越长。 通常，影响最大的因素是非垃圾对象的数量和大小。 一个足够大的
HashMap会做到这一点... - 硬件的物理内存量有限。 如果 JVM 的内存需求增长超过此值，主机操作系统将在 RAM 和磁盘之间"交换"内存页。 一个足够大的
HashMap会做到这一点...如果您的堆大小大于 JVM 进程可用的物理 RAM 量。 - 内存影响是由于处理器的内存缓存和 TLB 缓存大小造成的。 基本上，如果处理器在读写内存方面的"需求"太大，内存系统就会成为瓶颈。 大型堆和高度非本地化的访问模式可能会加剧这些影响。 (并运行 GC！
HashMap的主哈希数组的大小也有大约2^31的限制。 因此，如果您有超过 2^31/0.75 个条目，则当前HashMap实现的性能理论上O(N)。 然而，我们谈论的是数十亿个条目，在此之前，二阶记忆效应将影响性能。
1 - 如果您的密钥hashCode()功能不佳，那么您可能会发现您获得的密钥哈希到同一代码的很大一部分。 如果发生这种情况，这些键的查找、插入和删除性能将O(logN)或O(N)...具体取决于密钥的类型和您的 Java 版本。 在这种情况下，表中的数字键N与您正在查找的哈希码相同，依此类推。
HashMap您的用例中最快的数据结构吗？
- 如果没有用例的更多详细信息，很难说。
- 如果不了解您准备在这个问题上投入多少时间和精力，就很难说。 (如果你投入足够的编码努力，你几乎可以肯定地削减百分之几。 也许更多。
HashMap是通用的。 - 如果没有你(首先！)做适当的性能分析，很难说。
例如，您首先需要确保HashMap确实是性能问题的原因。 当然，你>>认为<<确实如此，但你是否真的分析了你的代码来找出答案？ 在你这样做之前，你可能会浪费时间优化不是瓶颈的东西。
因此，即使对于大量对象，HashMaps也会有一个O(1)插入/删除。大量数据的问题在于空间。对于一百万个条目，您可能在内存中很好。
Java 的默认加载系数为 .75 哈希映射，这意味着 HashMap 需要 133 万个插槽来支持此映射。如果你能在内存中支持这一点，那就没问题了。即使你不能把这一切保存在内存中，你可能仍然想使用HashMaps，也许是一个分布式HashMap。
就 Big-O 时间而言，这是指最坏的情况复杂性。Big-O时间的分析真正有用的唯一时间是数据大小越来越大。如果你处理的是一个非常小的数据集，O(5n+10)与O(n)不同。常量时间(O(1))时间如此有价值的原因是，这意味着时间不依赖于数据集的大小。因此，对于像您所描述的大型数据集，HashMap 将是一个很好的选择，因为它具有恒定的时间插入/删除。