是否将JavaScript映射对象编入索引以优化map.get？

Question

在V8的幕后，是否以某种方式对JavaScript-Map-object的键进行了索引以优化map.get方法？还是map.get()只是遍历整个地图直到找到匹配的钥匙？

我map.get对500,000多个键/值对的较大映射的效率感兴趣。我有很多映射，我只想缓存在RAM中，而不是查询已经为快速取值而对索引进行索引的数据库。在我看来，如果以某种方式在后台索引了Map对象的键，则查询RAM而不是数据库的查询会更快。

抽象：

function randomUniqueThing()
{
   // returns (magically) a unique random: 
   //  string, number, function, array or object.
}
var objMap = new Map();
var count = 0;
var thing1,thing2;
while(count < 500000)
{
    thing1 = randomUniqueThing();
    thing2 = randomUniqueThing();
    objMap.set(thing1, thing2);
    count++;
}
var lastValue = objMap.get(thing1); // Will getting this last
                                    // thing's value take longer
                                    // than getting other values?

Answer 1

是的，正如您从这种数据类型所期望的那样，它Map确实在后台使用了哈希表。

来源证明：

与往常一样，证明在来源中：

摘录自V8源文件：src/objects.h class JSMap

// The JSMap describes EcmaScript Harmony maps
class JSMap : public JSCollection {
 public:
  DECLARE_CAST(JSMap)

  static void Initialize(Handle<JSMap> map, Isolate* isolate);
  static void Clear(Handle<JSMap> map);

  // Dispatched behavior.
  DECLARE_PRINTER(JSMap)
  DECLARE_VERIFIER(JSMap)

 private:
  DISALLOW_IMPLICIT_CONSTRUCTORS(JSMap);
};

如我们所见，JSMapextends JSCollection。

现在，让我们看一下以下内容的声明JSCollection：

摘录自V8源文件：src/objects.h class JSCollection

class JSCollection : public JSObject {
 public:
  // [table]: the backing hash table
  DECL_ACCESSORS(table, Object)

  static const int kTableOffset = JSObject::kHeaderSize;
  static const int kSize = kTableOffset + kPointerSize;

 private:
  DISALLOW_IMPLICIT_CONSTRUCTORS(JSCollection);
};

在这里，我们可以看到它使用哈希表，并带有漂亮的注释来阐明它。

关于该哈希表是否仅引用对象属性而不是get方法，存在一些问题。从源代码到Map.prototype.get，我们都可以使用哈希映射。

摘录自V8源文件：src/js/collection.js MapGet

function MapGet(key) {
  if (!IS_MAP(this)) {
    throw MakeTypeError(kIncompatibleMethodReceiver,
                        'Map.prototype.get', this);
  }
  var table = %_JSCollectionGetTable(this);
  var numBuckets = ORDERED_HASH_TABLE_BUCKET_COUNT(table);
  var hash = GetExistingHash(key);
  if (IS_UNDEFINED(hash)) return UNDEFINED;
  var entry = MapFindEntry(table, numBuckets, key, hash);
  if (entry === NOT_FOUND) return UNDEFINED;
  return ORDERED_HASH_MAP_VALUE_AT(table, entry, numBuckets);
}

摘录自V8源文件：src/js/collection.js MapFindEntry

function MapFindEntry(table, numBuckets, key, hash) {
  var entry = HashToEntry(table, hash, numBuckets);
  if (entry === NOT_FOUND) return entry;
  var candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
  if (key === candidate) return entry;
  var keyIsNaN = NumberIsNaN(key);
  while (true) {
    if (keyIsNaN && NumberIsNaN(candidate)) {
      return entry;
    }
    entry = ORDERED_HASH_MAP_CHAIN_AT(table, entry, numBuckets);
    if (entry === NOT_FOUND) return entry;
    candidate = ORDERED_HASH_MAP_KEY_AT(table, entry, numBuckets);
    if (key === candidate) return entry;
  }
  return NOT_FOUND;
}

通过基准测试证明：

还有另一种方法来测试它是否使用哈希映射。进行许多输入，并测试最长和最短的查找时间。像这样：

'use strict';

let m = new Map();
let a = [];

for (let i = 0; i < 10000000; i++) {
    let o = {};
    m.set(o, i);
    a.push(o);
}

let lookupLongest = null;
let lookupShortest = null;

a.forEach(function(item) {
    let dummy;
    let before = Date.now();
    dummy = m.get(item);
    let after = Date.now();
    let diff = after - before;
    if (diff > lookupLongest || lookupLongest === null) {
        lookupLongest = diff;
    }
    if (diff < lookupShortest || lookupShortest === null) {
        lookupShortest = diff;
    }
});
console.log('Longest Lookup Time:', lookupLongest);
console.log('Shortest Lookup Time:', lookupShortest);

几秒钟后，我得到以下输出：

$ node test.js
Longest Lookup Time: 1
Shortest Lookup Time: 0

如果每个条目都在其中循环，那么这样的紧密查找时间肯定是不可能的。