Yes, as you would expect from such a data type, a Map does utilize a hash-table under the hood.
Proof by source:
As always, the proof is in the source:
Excerpt from V8 source file 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);
};
As we can see, JSMap extends JSCollection.
Now if we take a look at the declaration for JSCollection:
Excerpt from V8 source file 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);
};
Here we can see that it uses a hash table, with a nice comment to clarify it.
There was some question as to if that hash table refers only to object properties, and not to the get method. As we can from the source code to Map.prototype.get, a hash map is being used.
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);
}
Excerpt from V8 source file 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;
}
Proof by benchmarking:
There is another way to test if it uses a hash map. Make many entries, and test what the longest and shortest lookup times are. Something like this:
'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);
After a few seconds, I get the following output:
$ node test.js
Longest Lookup Time: 1
Shortest Lookup Time: 0
Such close lookup times would certainly not be possible if it where looping though every entry.
