JavaScript地图对象是否被索引来优化map.get？
在V8的幕后，JavaScript-Map-object的键以某种方式build立索引，以优化map.get方法？ 或者map.get()只是简单地遍历整个地图，直到发现一个关键匹配？
我对map.get的500,000个以上键/值对的较大映射的效率感兴趣。 我有这么多的映射，我只想caching在内存中，而不是查询数据库的密钥已经索引的快速检索。 在我看来，查询RAM而不是数据库会更快，如果Map对象的键在某种程度上在后台索引。
抽象：
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?
是的，正如你从这样的数据types中所期望的那样， Map不会利用哈希表中的哈希表。 实际上， Map是Object一个子类。
按来源certificate：
与往常一样，证据来源于：
摘录自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); };
正如我们所看到的， JSMap扩展了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); };
在这里我们可以看到它使用了一个哈希表，并有一个很好的评论来澄清它。 正如我之前提到的，这反过来又延伸了正规的JSObject 。
有一些问题，如果该哈希表只引用对象属性，而不是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; }
基准certificate：
还有另一种方法来testing它是否使用哈希映射。 做很多条目，并testing最长和最短的查找时间。 像这样的东西：
'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
如果循环访问每个条目，那么这种仔细的查找时间肯定是不可能的。