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

Question

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

是的,现在我使用对象文字存储我的数据,但我发现Chrome在循环遍历属性名称时没有维护顺序.

有没有一种常见的方法来解决这个问题？

谢谢你的任何提示.

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];
};

Traversal将被订购,可以使用任何一种方法.当需要有序遍历时,创建一个包含对象的数组(仅限值)并返回它.作为一个数组,它不支持键控访问.另一个选项是要求客户端提供应该应用于数组中每个对象的回调函数.

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 在Closure Library中对LinkedMap的实现,以获取此类的文档和来源.