Ben*_*tto 4 language-agnostic arrays hashtable list data-structures
考虑一个数组与一个哈希表,其中键只是列表的整数索引.
他们的平均情况插入,查找和删除big-O边界都是O(1)恒定时间.我知道你可以通过一个数组在缓存局部获得一些低级别的胜利,并且哈希表操作有一个边际(大部分是常量的)开销,但哈希表可以免费获得稀疏性,这在某些应用程序中是一个巨大的胜利.
我错过了哪些其他重要(或小)对比？
背景:我在采访编程候选人时有时会讨论这个问题.通常上下文是"如何在JS VM中实现Javascript数组类型？" 对于密集的数据,我支持原生阵列,但我希望有更好的推理而不是"看起来不像矫枉过正"的直觉.
数组是jsut哈希表的特例,其中哈希函数非常简单
f(x) := x;
并且使用的模数与数据字大小相同(因此也就是数组大小).
如果你不允许非唯一值,你不需要"下一个"指针和瞧,我们有一个数组.
由于缺少复杂的散列函数和模数计算,这非常快,但只有在数组可以保持较小时才适用(非常大的数组,其中有很多空的地方会浪费内存资源,并且可能会触发令人讨厌的事情,例如交换/删除磁盘).
| 归档时间： |
|
| 查看次数： |
969 次 |
| 最近记录： |