为了优化map.get，索引了JavaScript Map Objects吗？ [英] Are JavaScript Map Objects Indexed to Optimize map.get?

问题描述

在v8的幕后，JavaScript-Map-object的密钥以某种方式进行索引，优化 map.get 方法？或者 map.get（）只需循环遍历整个地图，直到它发现一个关键的匹配？

我在500,000+个键/值对的较大映射上，对 map.get 的效率感兴趣。我有这么多的映射，我只想缓存在RAM中，而不是查询一个数据库，其中的密钥已经被索引以进行快速检索。在我看来，如果Map对象的键以某种方式索引到幕后，那么查询RAM而不是数据库会更快。

摘要：

  function randomUniqueThing（）
 {
 //返回（神奇地）一个唯一的随机：
 // string，number ，函数，数组或对象。 
} 
 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）; //将获得最后一个
 //事物的值比获取其他值需要更长的
 // 
  

解决方案

是的，正如你所期望的那样的数据类型， Map 确实利用了引擎盖下的哈希表。实际上， Map 是 Object 的子类。

证明来源：

一如以往，证明来源：

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

  / JSMap描述EcmaScript和声映射
类JSMap：public JSCollection {
 public：
 DECLARE_CAST（JSMap）
 
 static void Initialize（Handle< JSMap> map，Isolate *隔离）; 
 static void Clear（Handle< JSMap> map）; 
 
 //调度行为。 
 DECLARE_PRINTER（JSMap）
 DECLARE_VERIFIER（JSMap）
 
 private：
 DISALLOW_IMPLICIT_CONSTRUCTORS（JSMap）; 
}; 
  

我们可以看到， JSMap extends JSCollection 。

现在，如果我们来看看 JSCollection ：

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

  class JSCollection：public JSObject {
 public：
 // [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（表）; 
 var hash = GetExistingHash（key）; 
 if（IS_UNDEFINED（hash））return UNDEFINED; 
 var entry = MapFindEntry（table，numBuckets，key，hash）; 
 if（entry === NOT_FOUND）return UNDEFINED; 
返回ORDERED_HASH_MAP_VALUE_AT（表，条目，numBuckets）; 
} 
  

摘录V8源文件 src / js / collection.js a> 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（候选人））{
 return entry; 
} 
 entry = ORDERED_HASH_MAP_CHAIN_AT（表，条目，numBuckets）; 
 if（entry === NOT_FOUND）return entry; 
候选人= ORDERED_HASH_MAP_KEY_AT（表，条目，numBuckets）; 
 if（key === candidate）return entry; 
} 
 return NOT_FOUND; 
} 
  

通过基准测试证明：

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

 'use strict'; 
 
 let m = new Map（）; 
 let a = []; （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（'最短查找时间：'，lookupShortest）; 
  

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

  $ node test.js 
最长查找时间：1 
最短查找时间：0 
  pre> 
 
 
如果在每个条目循环的时候，这样仔细的查找时间肯定是不可能的。
 
Behind the scenes, in V8, are JavaScript-Map-object's keys indexed in some manner that optimizes the map.get method? Or does map.get() simply just loop through the entire map until it discovers a key match?

I'm interested in the efficiency of map.get on larger mappings of 500,000+ key/value pairs. I have this many mappings that I'd like to just cache in RAM, instead of querying a database where the keys are already indexed for fast value-retrieval. It seems to me, that querying RAM instead of a database would be faster if the Map object's keys are somehow indexed behind the scenes.

Abstract:
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?

解决方案
Yes, as you would expect from such a data type, a Map does utilize a hash-table under the hood. In fact, Map is a subclass of Object.

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. And as I mentioned before, this in turn extends the regular JSObject.



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.

Excerpt from V8 source file 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);
}


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.

                        
这篇关于为了优化map.get，索引了JavaScript Map Objects吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！