为什么使用数组来实现“列表”而不是哈希表？

Question

考虑一个数组和一个哈希表，其中键只是列表的整数索引。它们的平均情况下插入、查找和删除大O边界都是O(1)常量时间。我知道你可能会在数组中获得一些低级别的缓存优势，并且哈希表操作有一些微小的（大多是常量）开销，但哈希表可以免费为您提供稀疏性，在某些应用程序中这是一个巨大的优势。

我错过了哪些其他重要的（或小的）对比呢？

背景：有时我会与面试编程候选人讨论这个问题。通常情况下，背景是“如何在JS VM内部实现Javascript数组类型？”对于密集包装的数据，我支持本地数组，但我希望有更好的理由，而不仅仅是“它似乎不那么过度”。

- Ben Zotto

Answer 1

一个数组就是哈希表的一种特殊情况，其中哈希函数非常简单。

f(x) := x;

取模运算所使用的值与数据字大小（因此也是数组大小）相同。

如果您不允许非唯一值，则不需要“next”指针，那么我们就有了一个数组。

由于缺少复杂的哈希函数和模数计算，这种方法非常快，但仅适用于可以保持较小的数组（具有大量空位的非常大的数组会浪费内存资源，并可能触发像交换/磁盘垃圾回收之类的不良操作）。

- Ritsaert Hornstra

---

看待问题的方式很有趣。谢谢。好的，基本上，在我看来没有进一步明显的区别——实际上，在这种情况下，哈希表就是一个带有更多开销和自由稀疏性的数组，以“它是否更适合您的数据/场景”为基础。 - Ben Zotto

Answer 2

当你从想要实现Javascript伪数组行为的角度考虑时，使用哈希表是更好的选择，特别是因为Javascript数组没有固定长度，并且需要能够容纳任何索引处的条目。在Javascript中，数组看起来像数组，但行为更像哈希表。

但在一种更接近机器的语言中，对于可以有效存储在数组中的数据使用真正的数组的性能和空间优势非常值得注意，特别是因为使用哈希表的好处对于稀疏数组而言相当有限，而这不是您应该使用数组的情况。这实际上最好使用具有整数键的哈希表来完成。

在所有情况下，数组的插入、查找和删除也都是O(1)，但比哈希表具有更低的常数O（这不仅仅是因为缓存局部性）。并且数组每个条目所需的空间更少。如果您想以使其后续条目的索引相应地更改的方式删除和插入条目，则n为需要移动的条目数，则其时间复杂度将为O(n)，但哈希表执行此操作的时间复杂度也为O(n)，而且开销更大。这是最好使用链表的操作。增加数组的大小的成本也比增加可能需要重新哈希其所有条目的哈希表要小。

所有不同的集合类型都有其特定的优缺点。这就是为什么有这么多不同的集合类型在使用中的原因。

- x4u

Answer 3

因为列表通常是有序的，而哈希表则不是。在你将元素添加到列表中并期望顺序保持一致的情况下，哈希表不能保证你得到的顺序与添加时相同，而数组则保留了顺序。

- tvanfosson

---

谢谢tvanfosson。我更新了问题 - 我意识到最初我表述不清：我假设表中的键只是“列表”的整数索引，这意味着如果您通过整数“索引”访问对象，则“顺序被保留”。 - Ben Zotto

我从未听说过任何高效哈希表会出现这种情况，这是不正确的。 - bmargulies

@bmargulies：当然，如果是通过哈希桶进行抽象枚举，你是正确的。但是，如果我的所有键都代表列表中的索引，我可以编写一个for循环来遍历我已知的“键”范围，并从我放置它们的索引中获取正确的值。 - Ben Zotto

@Ben - 也许我有些问题没明白，但是要实现这个功能，难道不需要为每个整数分配一个存储桶吗？如果有多个整数哈希到同一个存储桶，就无法保持顺序。如果确实每个存储桶只有一个整数，那与稀疏数组有什么区别呢？ - tvanfosson

假设桶的数量和哈希算法是实现特定的。但是，假设您有一些“put（key，obj）”操作和一个“get（key）”操作，您可以使用递增索引遍历索引以及使用get操作来获取键（key）。（答案可能只是，“所有这个实现特定部分的魔力都在这里。”） - Ben Zotto

Answer 4

因为哈希函数不是免费的。线性因素很重要。最坏情况下的时间很重要。计算指令。

对于你提到的特定情况，也就是Javascript的基本实现，可能有太多其他开销来消除这些问题。但是，如果有人尝试使用简单数字键大量操作数组，那么数组肯定更好。

- bmargulies