Les objets de carte JavaScript sont-ils indexés pour optimiser map.get?

Oui, comme vous l'attendiez d'un tel type de données, une Map utilise une table de hachage sous le capot. En fait, Map est une sous-classe d' Object .

Preuve par source:

Comme toujours, la preuve est dans la source:

Extrait du fichier source 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); }; 

Comme nous pouvons le voir, JSMap étend JSCollection .

Maintenant, si nous examinons la déclaration pour JSCollection :

Extrait du fichier source 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); }; 

Ici, nous pouvons voir qu'il utilise une table de hachage, avec un bon commentaire pour le clarifier. Et comme je l'ai déjà mentionné, cela étend à son tour le JSObject régulier.

Il y avait une question quant à savoir si cette table hash se réfère uniquement aux propriétés de l'objet, et non à la méthode get . Comme nous pouvons, du code source à Map.prototype.get , une carte de hash est utilisée.

Extrait du fichier source 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); } 

Extrait du fichier source 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; } 

Preuve par benchmarking:

Il existe une autre façon de tester s'il utilise une carte de hash. Créez de nombreuses entrées et testez ce que sont les temps de recherche les plus longs et les plus courts. Quelque chose comme ça:

 '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); 

Après quelques secondes, j'ai la sortie suivante:

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

De tels temps de recherche rapprochés ne seraient certainement pas possibles si l'on faisait la boucle dans toutes les entrées.