在 ES6 中,Maps 和 Sets 可以使用 Objects 作为键。然而,由于 ES6 规范没有规定这些数据结构的底层实现,我想知道现代 JS 引擎如何存储 key 以保证 O(1) 或至少 sublinear。检索?
在像 Java 这样的语言中,程序员可以显式提供一个(好的)hashCode 方法,该方法会在键空间中均匀散列键,以保证性能。然而,由于 JS 没有这样的功能,仍然假设他们在 Maps 和 Sets 实现中使用某种散列是否仍然公平?
任何信息将不胜感激!
最佳答案
是的,该实现基于散列,并且具有(摊销的)恒定访问时间。
“他们使用对象标识”是一种简化;完整的故事是 ES Maps 和 Sets 使用 SameValueZero确定相等性的算法。
根据此规范,V8 的实现计算字符串和数字的“真实”哈希值,并选择一个随机数作为对象的“哈希值”,并将其存储为这些对象的私有(private)(隐藏)属性以供以后访问。 (这不是很理想,将来可能会改变,但现在就是这样。)
使用 memoryAddress % keySpace
无法工作,因为垃圾收集器会四处移动对象,并且每次可能移动任何对象时都重新散列所有映射和集合将非常复杂和昂贵。
关于ecmascript-6 - ES6 映射和集合 : how are object keys indexed efficiently?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/44528826/