Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Javascript data structure for fast lookup and ordered looping?

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?

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.

Is there a common way to solve this in Javascript?

Thanks for any hints.

like image 818
Haes Avatar asked Aug 23 '10 17:08

Haes


People also ask

Which data structure has fast lookup?

With a hash table, you can access objects by the key, so this structure is high-speed for lookups. Hash tables are faster than the arrays for lookups.

Which data structure is best for lookup?

Looking at complexity analysis, Hashtables seem to be the most efficient for lookups.

Does JavaScript use data structures?

JavaScript has primitive (built in) and non-primitive (not built in) data structures. Primitive data structures come by default with the programming language and you can implement them out of the box (like arrays and objects).

What are the four basic data structures in JavaScript?

The four types of basic data structures supported by JavaScript are: array lists, maps, records and JSON tables.


3 Answers

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

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

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

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

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

like image 115
Anurag Avatar answered Sep 29 '22 20:09

Anurag


The only instance in which Chrome doesn't maintain the order of keys in an object literal seems to be if the keys are numeric.

  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());
  }

In Chrome, the above produces: "1,9,342,damsonplum,banana,apple,cherry".

In other browsers, it produces "damsonplum,9,banana,1,apple,cherry,342".

So unless your keys are numeric, I think even in Chrome, you're safe. And if your keys are numeric, maybe just prepend them with a string.

like image 23
jhurshman Avatar answered Sep 29 '22 20:09

jhurshman


As has been noted, if your keys are numeric you can prepend them with a string to preserve order.

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

Example

like image 2
Zombo Avatar answered Sep 29 '22 20:09

Zombo