用于快速查找和有序循环的 JavaScript 数据结构

Question

JavaScript 中是否有一种数据结构或模式可以用于快速查找（通过键，如关联数组）和有序循环？

是的，现在我使用对象文字来存储我的数据，但我刚刚发现 Chrome 在循环属性名称时不保持顺序。

JavaScript 有没有通用的方法来解决这个问题？

Answer 1

自己创建一个数据结构。将顺序存储在结构内部的数组中。将键映射的对象存储在常规对象中。我们将其称为 OrderedMap ，它将有一个映射、一个数组和四个基本方法。

OrderedMap
    map
    _array

    set(key, value)
    get(key)
    remove(key)
    forEach(fn)

function OrderedMap() {
    this.map = {};
    this._array = [];
}

插入元素时，将其添加到数组中所需的位置以及对象中。按索引插入或在末尾插入的时间复杂度为 O(1)。

OrderedMap.prototype.set = function(key, value) {
    // key already exists, replace value
    if(key in this.map) {
        this.map[key] = value;
    }
    // insert new key and value
    else {
        this._array.push(key);
        this.map[key] = value;
    }
};

删除对象时，将其从数组和对象中删除。如果按键或值删除，复杂度为 O(n)，因为您需要遍历维持排序的内部数组。按索引删除时，复杂度为 O(1)，因为您可以直接访问数组和对象中的值。

OrderedMap.prototype.remove = function(key) {
    var index = this._array.indexOf(key);
    if(index == -1) {
        throw new Error('key does not exist');
    }
    this._array.splice(index, 1);
    delete this.map[key];
};

查找的时间复杂度为 O(1)。通过键从关联数组（对象）中检索值。

OrderedMap.prototype.get = function(key) {
    return this.map[key];
};

遍历将是有序的并且可以使用任一方法。当需要有序遍历时，创建一个包含对象（仅值）的数组并返回它。作为一个数组，它不支持键控访问。另一种选择是要求客户端提供一个回调函数，该函数应应用于数组中的每个对象。

OrderedMap.prototype.forEach = function(f) {
    var key, value;
    for(var i = 0; i < this._array.length; i++) {
        key = this._array[i];
        value = this.map[key];
        f(key, value);
    }
};

请参阅 Closure 库中的 Google 实现 LinkedMap，了解相关文档和源代码这样的一堂课。

Answer 2

Chrome 不维护对象字面量中键的顺序的唯一情况似乎是键是数字。

  var properties = ["damsonplum", "9", "banana", "1", "apple", "cherry", "342"];
  var objLiteral = {
    damsonplum: new Date(),
    "9": "nine",
    banana: [1,2,3],
    "1": "one",
    apple: /.*/,
    cherry: {a: 3, b: true},
    "342": "three hundred forty-two"
  }
  function load() {
    var literalKeyOrder = [];
    for (var key in objLiteral) {
      literalKeyOrder.push(key);
    }

    var incremental = {};
    for (var i = 0, prop; prop = properties[i]; i++) {
      incremental[prop] = objLiteral[prop];
    }

    var incrementalKeyOrder = [];
    for (var key in incremental) {
      incrementalKeyOrder.push(key);
    }
    alert("Expected order: " + properties.join() +
          "\nKey order (literal): " + literalKeyOrder.join() +
          "\nKey order (incremental): " + incrementalKeyOrder.join());
  }

在 Chrome 中，上面的结果是：“1,9,342,damsonplum,banana,apple,cherry”。

在其他浏览器中，它会生成“damsonplum,9,banana,1,apple,cherry,342”。

因此，除非你的键是数字，否则我认为即使在 Chrome 中，你也是安全的。如果您的键是数字，也许只需在它们前面加上一个字符串即可。

Answer 3

作为
已注明（如果您的键是数字）
您可以在它们前面添加一个字符串以保持顺序。

var qy = {
  _141: '256k AAC',
   _22: '720p H.264 192k AAC',
   _84: '720p 3D 192k AAC',
  _140: '128k AAC'
};

示例