为什么要使用一个数组实现]清单＆QUOT;代替哈希表？ [英] Why use an array to implement a "list" instead of a hash table?

问题描述

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

Consider an array versus a hashtable where the keys are just the integral indexes of a list.

他们的平均情况插入，查找和删除大O边界都是 O（1）恒定的时间。我明白，你可能会在缓存当地一些低级别的胜利有一个数组，并有一个边际（主要是常数）开销的哈希表的操作，但哈希表让你稀疏的自由，这在某些应用中是一个巨大的胜利。

Their average-case insertion, lookup, and removal big-O bounds are all O(1) constant time. I understand that you may get some low-level wins in cache locality with an array, and there is a marginal (mostly-constant) overhead to the hashtable operations, but hashtables get you sparseness for free, which in some applications is a big win.

还有什么其他显著（或小）的对比我缺少什么？

What other significant (or small) contrasts am I missing?

上下文：我进入一个关于这个讨论面试考生编程时有时。通常情况下是你将如何实现JS VM内的JavaScript数组类型？对于密集打包的数据，我与本机阵列的一面，但我希望能有比直觉更好的理由是，似乎少有点小题大做。

Context: I get into a discussion about this sometimes when interviewing programming candidates. Usually the context is "how would you implement the Javascript array type inside of the JS VM?" For densely-packed data, I side with a native array, but I want to have better reasoning than the intuition that "it seems less like overkill".

推荐答案

这是数组仅仅指刚哈希表的特殊情况，其中散列函数是非常简单的。

An array is jsut a special case of a hash table where the hash function is very simple

f(x) := x;

和所使用的模数是一样的数据字尺寸（以及因此的阵列大小）。

and the modulo used is the same as the data word size (and thus the array size).

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

If you do not allow non unique values you do not need the "next" pointers and voila, we have an array.

由于没有复杂的散列函数和模数计算的，这是非常快的，但只适用于当阵列可以保持小的（非常大的阵列，空的地方很多的浪费内存资源，并可能会引发像交换讨厌的东西/捣毁到磁盘）。

Because of the absence of a complex hash function and modulo calculation, this is very fast, but only applicable when the array can be kept small (very large arrays with lot's of empty places waste memory resources and might trigger nasty things like swapping/trashing to disk).

这篇关于为什么要使用一个数组实现]清单＆QUOT;代替哈希表？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！