JavaScript对象作为哈希? 复杂度是否大于O(1)?
对于我最近写的一些algorithm,我认为哈希值是非常好的。 我认为我可以只使用对象中的成员variables作为键值对。 我不确定这是否是最佳的,因为我不知道幕后发生了什么。 我还假设V8与其他环境不同。 不过,我想,查找成员variables会相当快(希望)?
这一切都说,我想知道是否运行时间复杂的写作,阅读,创build和删除JavaScript对象的成员variables都是O(1)。 如果环境有差异(v8 vs其他),它们是什么?
UPDATE
Chrome的删除现在真的很快; 然而,当你接近100万个密钥时,更新似乎会变慢。
好的,我有一些数据。 我要说的是浏览器之间是有区别的。 看来不同的环境关心不同的CRUD操作。 而且,由于在按键数量增加时性能不受影响,因此对象是引擎盖下的哈希。 如果3个testing之间没有性能差异(ops / sec),那么(我认为)就意味着它是一个散列,每个操作的复杂度是O(1),而不pipe它比其他操作快还是慢。 换句话说,如果随着密钥的增加,任何testing的操作/秒计数都有变化,那么它不是O(1)(情况并非如此)。
testing:
http://jsperf.com/objectsashashes/2(100键);
http://jsperf.com/objectsashashes/3(100k键);
http://jsperf.com/objectsashashes/(100万个键);
http://jsperf.com/objects-as-hashes-300-mil(10米键);
观察:
- 创build对的时间是通过10 mil密钥值对的线性关系。
- Chrome:针对读取进行了优化。 创build和更新有点慢。
- Safari:优化写入,但读取速度相当快。 似乎更慢的更新。
- IE9:没有任何的操作。 删除产量稍好一些。 注意:我用一台较旧的机器来testing。
- IE10:删除产量略好一些。 创build/更新比阅读慢。
- IE8:无法testing,但随着最新的Win7更新似乎IE9被自动安装。 不知道XP机器。
- Firefox:极其优化。 其他一切都差不多。
- Opera:所有操作都以相同的速度执行。
- 存储最大密钥的唯一限制似乎是基于内存(浏览器,环境或机器强制执行)
最后说明:
尽pipehash ['something']并不比hash.something慢,但如果需要连接以查找散列的名称,则会显着降低性能( http://jsperf.com/member-associative-array-syntax-vs -dot-syntax ),这就是为什么我在上面的性能testing之外caching这些值的原因。 如果可能,避免串联。 string在JS中是不可变的,结果每个连接创build3个对象/“原语”(string1,string2和连接的string)。
JavaScript对象是散列。 我无法想象任何理智的实现不会提供对象属性的恒定时间CRUD操作。
您是否看到这种方法的具体性能问题?