用于快速查找和有序循环的Javascript数据结构？ [英] Javascript data structure for fast lookup and ordered looping?

问题描述

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

is there a data structure or a pattern in Javascript that can be used for both fast lookup (by key, as with associative arrays) and for ordered looping?

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

Right, now I am using object literals to store my data but I just disovered that Chrome does not maintain the order when looping over the property names.

是否有一种常见的方式在Javascript中解决这个问题？

Is there a common way to solve this in Javascript?

感谢任何提示。

推荐答案

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

Create a data structure yourselves. Store the ordering in an array that is internal to the structure. Store the objects mapped by a key in a regular object. Let's call it OrderedMap which will have a map, an array, and four basic methods.

OrderedMap
    map
    _array

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

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

插入元素时，将其添加到所需位置的数组中至于对象。按索引或在末尾插入是O（1）。

When inserting an element, add it to the array at the desired position as well as to the object. Insertion by index or at the end is in 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），因为您可以直接访问数组和对象中的值。

When deleting an object, remove it from the array and the object. If deleting by a key or a value, complexity is O(n) since you will need to traverse the internal array that maintains ordering. When deleting by index, complexity is O(1) since you have direct access to the value in both the array and the object.

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）中。通过关联数组（对象）中的键检索值。

Lookups will be in O(1). Retrieve the value by key from the associative array (object).

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

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

Traversal will be ordered and can use either of the approaches. When ordered traversal is required, create an array with the objects (values only) and return it. Being an array, it would not support keyed access. The other option is to ask the client to provide a callback function that should be applied to each object in the array.

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 ，以获取此类的文档和来源。

See Google's implementation of a LinkedMap from the Closure Library for documentation and source for such a class.

这篇关于用于快速查找和有序循环的Javascript数据结构？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！