Node.js Map中的最大条目数？

Question

我Map在Node.js v11.9.0 中制作了一个很大的内容并且它仍然失败了"致命错误:无效的表大小分配失败 - JavaScript堆内存不足".我的地图的键和值不应该接近Node的堆大小,所以我尝试制作一个地图并在其中插入数字键和值:

var N = Math.pow(2, 26);
var map = new Map();
for (var i = 0; i < N; i++) {
  map.set(i, i + 1);
  if (i % 1e5 === 0) { console.log(i / 1e6); }
}

在插入大约1660万个条目后,该程序崩溃了Node.这个数字看起来很可疑接近2 ^ 24,所以替换上面的日志if (i > 16777200) { console.log(i); },我看到程序在成功打印"16777215"后立即崩溃,这比一个小于2 ^ 24.

题.Node中的条目数是否有文件限制Map接近2 ^ 24？有没有办法提高这个限制？

(NB运行节点node --max-old-space-size=4096不会阻止崩溃,因为Node使用的RAM远远小于4 GB.)

(注意2.我不认为这是一个哈希冲突问题,因为在我的实际代码中,地图包含(short-ish)字符串而不是数字.)

(注意3.在Firefox的JavaScript控制台中运行上述程序不会导致Firefox-Firefox不断添加条目超过3000万.但是,Chrome会像Node一样崩溃.所以这很可能是V8的限制.)

Answer 1

V8开发人员在这里。我可以确认2 ^ 24是中的最大条目数Map。那不是错误，而只是实现定义的限制。

该限制取决于：

• 的FixedArray后备存储区的Map最大大小为1GB（与总堆大小限制无关）
• 在64位系统上，这意味着1GB / 8B = 2 ^ 30/2 ^ 3 = 2 ^ 27〜= 134M最大元素 FixedArray
• A Map每个条目需要3个元素（键，值，下一个存储桶链接），并且最大负载因子为50％（以避免由于许多存储桶冲突而导致的速度降低），并且其容量必须为2的幂。2 ^ 27 /（3 * 2）向下舍入到2的下一个幂是2 ^ 24，这是您观察到的极限。

FWIW对所有内容都有限制：除了最大堆大小之外，还有最大String长度，最大Array长度，最大ArrayBuffer长度，最大BigInt大小，最大堆栈大小等。这些限制中的任何一个都有可能引起争议，有时甚至是有争议的提高它们很有意义，但是这样的局限性仍然存在。我不知道要把这个特定限制提高两倍（例如），我也不知道，而且我也不知道达到两个因子是否足以满足您的期望。

Answer 2

我编写了允许超出该限制的 BigMap 和 BigSet 类，同时 100% 兼容，并建立在标准 Map 和 Set 上，当达到限制时，我只需创建新的 Maps（或 Sets）。

const kMaxSize = Math.pow(2, 24)

const BigMap = class {
  /*
    public api, compatible with "Map"
  */

  constructor (...parameters) {
    this.maps = [new Map(...parameters)]
  }

  set (key, value) {
    const map = this.maps[this.maps.length - 1]

    if (map.size === kMaxSize) {
      this.maps.push(new Map())
      return this.set(key, value)
    } else {
      return map.set(key, value)
    }
  }

  has (key) {
    return _mapForKey(this.maps, key) !== undefined
  }

  get (key) {
    return _valueForKey(this.maps, key)
  }

  delete (key) {
    const map = _mapForKey(this.maps, key)

    if (map !== undefined) {
      return map.delete(key)
    }

    return false
  }

  clear () {
    for (let map of this.maps) {
      map.clear()
    }
  }

  get size () {
    let size = 0

    for (let map of this.maps) {
      size += map.size
    }

    return size
  }

  forEach (callbackFn, thisArg) {
    if (thisArg) {
      for (let value of this) {
        callbackFn.call(thisArg, value)
      }
    } else {
      for (let value of this) {
        callbackFn(value)
      }
    }
  }

  entries () {
    return _iterator(this.maps, 'entries')
  }

  keys () {
    return _iterator(this.maps, 'keys')
  }

  values () {
    return _iterator(this.maps, 'values')
  }

  [Symbol.iterator] () {
    return _iterator(this.maps, Symbol.iterator)
  }
}

/*
  private function
*/

function _mapForKey (maps, key) {
  for (let index = maps.length - 1; index >= 0; index--) {
    const map = maps[index]

    if (map.has(key)) {
      return map
    }
  }
}

function _valueForKey (maps, key) {
  for (let index = maps.length - 1; index >= 0; index--) {
    const map = maps[index]
    const value = map.get(key)

    if (value !== undefined) {
      return value
    }
  }
}

function _iterator (items, name) {
  let index = 0

  var iterator = items[index][name]()

  return {
    next: () => {
      let result = iterator.next()

      if (result.done && index < (items.length - 1)) {
        index++
        iterator = items[index][name]()
        result = iterator.next()
      }

      return result
    },
    [Symbol.iterator]: function () {
      return this
    }
  }
}

BigMap.length = 0

/*
 Big Set
 */

const BigSet = class {
  /*
    public api, compatible with "Set"
  */

  constructor (...parameters) {
    this.sets = [new Set(...parameters)]
  }

  add (key) {
    const set = this.sets[this.sets.length - 1]

    if (set.size === kMaxSize) {
      this.sets.push(new Set())
      return this.add(key)
    } else {
      return set.add(key)
    }
  }

  has (key) {
    return _setForKey(this.sets, key) !== undefined
  }

  delete (key) {
    const set = _setForKey(this.sets, key)

    if (set !== undefined) {
      return set.delete(key)
    }

    return false
  }

  clear () {
    for (let set of this.sets) {
      set.clear()
    }
  }

  get size () {
    let size = 0

    for (let set of this.sets) {
      size += set.size
    }

    return size
  }

  forEach (callbackFn, thisArg) {
    if (thisArg) {
      for (let value of this) {
        callbackFn.call(thisArg, value)
      }
    } else {
      for (let value of this) {
        callbackFn(value)
      }
    }
  }

  entries () {
    return _iterator(this.sets, 'entries')
  }

  keys () {
    return _iterator(this.sets, 'keys')
  }

  values () {
    return _iterator(this.sets, 'values')
  }

  [Symbol.iterator] () {
    return _iterator(this.sets, Symbol.iterator)
  }
}

/*
  private function
*/

function _setForKey (sets, key) {
  for (let index = sets.length - 1; index >= 0; index--) {
    const set = sets[index]

    if (set.has(key)) {
      return set
    }
  }
}

function _iterator (items, name) {
  let index = 0

  var iterator = items[index][name]()

  return {
    next: () => {
      let result = iterator.next()

      if (result.done && index < (items.length - 1)) {
        index++
        iterator = items[index][name]()
        result = iterator.next()
      }

      return result
    },
    [Symbol.iterator]: function () {
      return this
    }
  }
}

BigSet.length = 0