如果大数组比哈希映射快查找？

Question

我从证券交易所收到"订单更新".每个订单ID介于1和100 000 000之间,因此我可以使用1亿个数组来存储1亿个订单,当收到更新时,我可以非常快速地从数组中查找订单,只需通过索引访问它arrray[orderId].我将花费几千兆字节的内存,但这没关系.

或者我可以使用hashmap,因为在任何时候"活动"命令的数量都是有限的(到,非常大致,100 000),查找也会非常快,但可能比数组慢一点.

问题是 - hashmap实际上会慢吗？是否合理地创造了1亿个阵列？

我需要延迟而没有别的,我完全不关心记忆,我应该选择什么？

Answer 1

每当考虑性能问题时,一个实验就值得一千个专家意见.测试一下!

也就是说,我会在黑暗中采取疯狂的措施:如果你可以说服你的操作系统让你的数字万亿字节阵列驻留在物理内存中(这不一定容易 - 考虑一下mlock和munlock系统调用),你会有相对更好的表现.您注意到(如果存在)任何此类性能增益可能是因为绕过散列函数的成本,并避免与您的散列图实现使用的任何冲突解决和内存分配策略相关的开销.

还值得注意的是,许多散列表实现对于某些操作具有非恒定的复杂性(例如,O(n)在最坏的情况下,单独的链接可能降级).鉴于您正在尝试优化延迟,具有非常积极的信号到OS内存管理器(例如,madvise和mlock)的阵列可能导致最接近恒定延迟的查找,您可以轻松地在微处理器上获得.

Answer 2

虽然客观地回答这个问题的唯一方法是性能测试,但我会争论使用Hashtable Map.(缓存和内存访问可能充满惊喜;我没有专业知识来推测哪一个会更快,何时更快.还要考虑其他代码可能会使本地化性能差异被边缘化.)

"最初选择"哈希的第一个原因是基于观察到有100M个不同的密钥但只有 0.1M的活动记录.这意味着如果使用数组,索引利用率将仅为0.1% - 这是一个非常稀疏的数组.

如果数据作为值存储在数组中,那么它需要相对较小或者数组大小会膨胀.如果数据未存储在数组中(例如,数组是指针),那么部分地减轻了数组中数据的局部性的参数.无论哪种方式,简单的数组方法都需要大量未使用的空间.

由于所有键都已经是整数,因此可以有效地实现分布(散列)函数 - 不需要创建复杂类型/序列的散列,因此该函数的"成本"应接近零.

所以,我简单的提议哈希:

• 使用由连续内存支持的线性探测.它很简单,具有良好的局部性(特别是在探测期间),并且避免了需要进行任何形式的动态分配.
• 选择合适的初始铲斗尺寸; 比方说,2x(或0.2M桶,准备好).甚至不给哈希一个调整大小的机会.请注意,这个建议的桶阵列大小仅为简单阵列方法大小的0.2%,并且可以进一步减小,因为可以调整大小与冲突率.
• 为哈希创建一个良好的分布函数.它还可以利用ID范围的知识.

虽然我已经针对给定的情况提出了"优化"的专用哈希表规则,但我会从正常的Map实现(无论是哈希表还是树)开始并测试它...如果标准实现工作得很好,为什么不使用它呢？

现在,在预期和极端负荷下测试不同的候选人 - 并挑选胜利者.