ES6 Maps and Sets:如何有效地索引对象键? [英] ES6 Maps and Sets: how are object keys indexed efficiently?

问题描述

在ES6中，地图和集合"可以将对象"用作键.但是，由于ES6规范并未规定这些数据结构的基础实现，所以我想知道现代JS引擎如何存储密钥以保证O(1)或至少

In ES6, Maps and Sets can use Objects as keys. However since the ES6 specification does not dictate the underlying implementation of these datastructures, I was wondering how does the modern JS engines store the keys in order to guarantee O(1) or at least sublinear retrieval?

在Java之类的语言中，程序员可以显式提供一个(好的)hashCode方法，该方法将在密钥空间中均匀地对密钥进行哈希处理，以保证性能.但是，由于JS不具有这些功能，是否仍然可以假设它们在Maps and Sets实现中使用某种哈希值呢?

In a language like Java, the programmer can explicitly provide a (good) hashCode method which would hash the keys evenly in the key space in order to guarantee the performance. However since JS does not have such features, would it still be fair to still assume they use some sort of hashing in the Maps and Sets implementation?

任何信息将不胜感激！

Any information will be appreciated!

推荐答案

是的，该实现基于哈希，并具有(摊销的)恒定访问时间.

Yes, the implementation is based on hashing, and has (amortized) constant access times.

他们使用的对象标识"是一种简化；完整的故事是，ES Maps和Sets使用 SameValueZero 算法来确定相等性.

"they use object identity" is a simplification; the full story is that ES Maps and Sets use the SameValueZero algorithm for determining equality.

符合此规范，V8的实现为字符串和数字计算实"哈希，并为对象选择一个随机数作为哈希"，并将其存储为这些对象的私有(隐藏)属性，以供以后访问. (那不是很理想，并且将来可能会改变，但是现在是这样.)

In line with this specification, V8's implementation computes "real" hashes for strings and numbers, and chooses a random number as "hash" for objects, which it stores as a private (hidden) property on these objects for later accesses. (That's not quite ideal and might change in the future, but for now that's what it is.)

使用memoryAddress % keySpace无效，因为垃圾收集器会移动对象，并且每次可能移动任何对象时都要重新散列所有Maps和Set会变得异常复杂和昂贵.

Using memoryAddress % keySpace cannot work because the garbage collector moves objects around, and rehashing all Maps and Sets every time any object might have moved would be prohibitively complicated and expensive.

这篇关于ES6 Maps and Sets:如何有效地索引对象键?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！