arrays - 为什么用数组来实现 "list"而不是哈希表？

Question

考虑一个数组与一个哈希表，其中键只是列表的整数索引。

它们的平均情况插入、查找和删除大 O 边界都是 O(1)恒定时间。我知道您可能会在使用数组的缓存局部性方面获得一些低级别的胜利，并且哈希表操作的开销很小(大部分是恒定的)，但是哈希表可以免费为您提供稀疏性，这在某些应用程序中是一个巨大的胜利.

我还缺少哪些其他显着(或小的)对比？

背景:我在面试编程候选人时有时会讨论这个问题。通常上下文是“您将如何在 JS VM 内实现 Javascript 数组类型？”对于密集打包的数据，我支持 native 数组，但我希望有比“它似乎不太像矫枉过正”的直觉更好的推理。

Answer 1

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

f(x) := x;

并且使用的模数与数据字大小(以及数组大小)相同。

如果您不允许非唯一值，则不需要“下一个”指针，瞧，我们有一个数组。

由于没有复杂的散列函数和模计算，这非常快，但仅适用于可以保持较小数组的情况(具有大量空位的非常大的数组会浪费内存资源，并且可能会触发诸如交换/垃圾桶之类的令人讨厌的事情)盘)。