在幕后，在 V8 中，JavaScript-Map-object 的键是否以某种优化 map.get 方法的方式进行了索引？还是 map.get() 只是简单地遍历整个 map ，直到它发现一个键匹配？
我对 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?
是的，正如您对这种数据类型的期望，Map 确实在底层利用了哈希表。
来源证明:
一如既往，证明在源中:
// 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 的声明:
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，正在使用 HashMap 。
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);
}
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;
}
基准测试证明:
还有另一种方法可以测试它是否使用 HashMap 。做很多条目，并测试最长和最短的查找时间是多少。像这样:
'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
如果循环遍历每个条目，那么这样近的查找时间肯定是不可能的。