22

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

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

有没有一种通用的方法可以在 Javascript 中解决这个问题？

感谢您的任何提示。

4

3 回答 3

33

自己创建数据结构。将排序存储在结构内部的数组中。将键映射的对象存储在常规对象中。我们称它为它将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实现。

于 2010-08-23T17:57:22.233 回答
3

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 中，您也是安全的。如果你的键是数字的，也许只是在它们前面加上一个字符串。

于 2010-08-23T18:07:26.483 回答
2

如前所述 ，如果您的键是数字的，您可以在它们前面加上一个字符串以保持顺序。

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

例子

于 2014-08-10T03:38:33.970 回答