我从证券交易所收到“订单更新”。每个订单 id 介于 1 到 100 000 000 之间，因此我可以使用 1 亿个数组来存储 1 亿个订单，当收到更新时，我可以非常快速地从数组中查找订单，只需通过 index 访问它arrray[orderId]。我将花费几 GB 的内存，但这没关系。
或者，我可以使用 hashmap，因为在任何时候“活动”订单的数量都是有限的（非常粗略地，100 000），查找也会非常快，但可能会比数组慢一点。
问题是 - hashmap 实际上会变慢吗？创建1亿个数组是否合理？
我需要延迟，没有别的，我完全不关心内存，我应该选择什么？
每当考虑性能问题时，一个实验值一千个专家意见。测试它！
也就是说，我会在黑暗中进行一次疯狂的尝试：如果您可以说服您的操作系统将您的数 GB 数组保留在物理内存中（这并不一定容易 - 考虑查看mlock和munlock系统调用），你会有相对更好的表现。您注意到的任何此类性能提升（如果存在）都可能是由于绕过了散列函数的成本，并避免了与您的散列图实现使用的任何冲突解决和内存分配策略相关的开销。
还值得提醒的是，许多哈希表实现对于某些操作具有非恒定的复杂性（例如，O(n)在最坏的情况下，单独的链接可能会降级）。鉴于您正在尝试优化延迟，向操作系统内存管理器（例如madvise和mlock）发出非常激进的信号的阵列可能会导致您可以轻松地在微处理器上获得最接近恒定延迟的查找。
虽然客观回答这个问题的唯一方法是进行性能测试，但我会主张使用 Hashtable Map。（缓存和内存访问可能充满惊喜；我没有专业知识来推测哪个会更快，什么时候更快。还要考虑到本地化的性能差异可能会被其他代码边缘化。）
我“最初选择”哈希的第一个原因是基于观察到有 100M 不同的键但只有0.1M 活动记录。这意味着如果使用数组，索引利用率将仅为 0.1% - 这是一个非常稀疏的数组。
如果数据作为值存储在数组中，那么它需要相对较小，否则数组大小会膨胀。如果数据未存储在数组中（例如，数组是指针），则数组中数据的局部性参数会部分减轻。无论哪种方式，简单的数组方法都需要大量未使用的空间。
由于所有的键已经是整数，分布（散列）函数可以有效地实现——不需要创建复杂类型/序列的散列，所以这个函数的“成本”应该接近于零。
所以，我提出的简单哈希：
虽然我已经为给定的情况提供了“优化”的专门哈希表规则，但我将从普通的 Map 实现（无论是哈希表还是树）开始并对其进行测试。如果标准实现工作得很好，为什么不使用它呢？
现在，在预期和极端负载下测试不同的候选人 - 并挑选获胜者。
这似乎取决于 ID 的聚类。
如果活动 ID 已经适当地聚集在一起，那么在没有散列的情况下，操作系统和/或 L2 缓存可以公平地保留好数据并保持低延迟。
如果它们是完全随机的，那么只要活动事务的数量超过可用缓存行的数量或这些事务的大小超过缓存的大小，您就会受到影响（目前尚不清楚哪种情况可能发生首先在你的情况下）。
但是，如果活动 ID 有一些不幸的模式导致高争用率（例如，它是不同属性的位包，并且频繁变化的属性会影响硬件），那么您可能受益于使用索引的 1:1 哈希返回随机情况，即使这通常被认为是一个非常糟糕的情况。
就压缩散列而言；注意到有些人担心哈希冲突的最坏情况回退行为，您可以简单地在连续内存中实现全尺寸表的缓存，因为它具有合理限制的最坏情况。只需将最繁忙的条目保留在地图中，然后在碰撞时回退到完整表格。如果另一个条目更活跃（如果您能找到合适的算法来决定这一点），则将其移动到地图中。
即便如此，还不清楚必要的哈希表大小是否足以将工作集减少到可缓存。你的订单有多大？
哈希图与数组的开销几乎为零。毫无疑问，我会在 100,000,000 个数组上打赌 100,000 条记录的哈希图。
还要记住，虽然你“不关心内存”，但这也意味着你最好有内存来备份它 - 一个 100,000,000 个整数的数组将占用 400mb，即使它们都是空的。您冒着数据被换出的风险。如果您的数据被换出，您将获得几个数量级的性能损失。
正如其他人所说，您应该测试和配置文件。不过，我在黑暗中随机刺伤：高负载因子哈希表将是这里的方法。一个巨大的阵列将花费您一次 TLB 未命中，然后每次访问都会导致最后一级缓存未命中。这是昂贵的。考虑到您提到的工作集大小，哈希表可能只会花费一些算术和 L1 未命中。
再次，在有代表性的例子上测试这两种选择。我们都只是在黑暗中刺伤。