用于快速查找和有序循环的 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);
    }
};

查看 Google 的 LinkedMap 实现从闭包库中获取此类的文档和源代码。