考虑一个数组与哈希表，其中的键只是列表的整数索引。为什么使用数组来实现“列表”而不是哈希表？
他们的平均情况下插入，查找和删除大O界限都是不变的时间。我知道你可能会在数组中获得缓存局部性的低级别胜利，并且散列表操作有一个边际（大多数常量）的开销，但是hashtables让你免费获得稀疏性，在某些应用中这是一个巨大的胜利。
我错过了什么其他重要的（或小的）对比？
背景：在面试编程候选人时，有时会对此进行讨论。通常情况下，“你将如何在JS VM中实现Javascript数组类型？”对于数据密集的数据，我与本地数组并存，但我想有比直觉更好的推理，即“看起来不太像过度杀伤”。
数组是仅仅指刚一个哈希表的一个特殊情况，其中该散列函数是非常简单的
f(x) := x;
和所使用的模数是相同的数据字尺寸（以及因此的阵列大小）。
如果你不允许非唯一值，你不需要“下一个”指针，瞧，我们有一个数组。由于没有复杂的散列函数和模数计算，这是非常快速的，但只适用于数组可以保持很小的情况（非常大的数组有很多空位会浪费内存资源，并且可能触发令人讨厌的事情，比如交换/垃圾到磁盘）。
由于列表通常是有序的，而哈希表不是。在将元素添加到列表中并期望排序保持一致的上下文中，散列表不保证您在数组保留排序时返回的顺序。
谢谢tvanfosson。我更新了这个问题 - 我意识到我最初并不清楚：我假设表中的键只是“list”的整数索引，这意味着如果通过整数索引访问对象，则“顺序被保留”索引”。 – 2010-02-15 16:36:34
这并非我所听过的任何有效的散列表。 – bmargulies 2010-02-15 16:41:58
@bmargulies：当然你通过散列桶抽象枚举是正确的。但是，如果我所有的键都代表索引到列表中，我可以在我已知的“键”范围内编写一个'for'循环，并从我放入的索引中获取正确的值。 – 2010-02-15 16:47:32
因为散列函数不是免费的。线性因素很重要。最差的案件时间非常重要。计算说明。
对于您引用的特定情况，这是Javascript的底层实现，可能会有太多其他开销来清除这些问题。尽管如此，如果有人试图用简单的数字键来实现一个数组的真正命中数组，那么数组就会变得更好。
当你从一个想要实现Javascript的伪数组行为的角度来看待它时，你是对的，哈希表是更好的方法来做到这一点，特别是，因为Javascript数组没有固定的长度，并且需要能够适应任何索引处的条目。 JavaScript中的数组看起来像数组，但表现得更像哈希表。
但是在离机器有点近的语言中，使用真实数组存储数据的性能和空间优势非常值得关注，特别是因为使用哈希表的好处是相当有限的稀疏数组，这不是你会或应该使用数组。这实际上更好用具有整数键的哈希表完成。
在所有情况下插入，查找和删除对于数组也是O（1），但是与哈希表相比，它的常量O要低得多（这不仅仅是因为缓存局部性）。而且每个条目需要的数组空间更少。如果你想以下面的条目相应地改变它们的索引来删除和插入条目，它将是O（n），其中n是需要移动的条目的数量，但它也可以是O（n）哈希表可以做到这一点，并有更高的常数开销。这是您最好使用链接列表的那种操作。同样增长一个数组的成本低于生成可能需要重新哈希所有条目的散列表的成本。
所有不同的集合类型都有其特定的优点和缺点。这就是为什么有这么多人在使用。
这是正确的答案。 – slebetman 2010-02-16 16:53:57
看着它有趣的方式。谢谢。好吧，基本上，除了我认为的之外，没有其他显而易见的区别 - 实际上，这种情况下的散列表是一个具有更多开销和自由稀疏性的数组，可用于“更适合您的数据/场景”类型办法。 – 2010-02-17 03:30:58