Nifty JavaScript Approach to Large Arrays

I figured this method out a while back in regards to storing things fast but also keeping flexibility of indexed arrays. I by no means am an expert in JS, and I learn more every day so if anyone has a better method, definitely let me know!

JavaScript natively has two types of arrays, a standard index array a[0], a[1], a[2], etc., and a key/value dictionary which uses a very similar syntax but with the difference being that you can use any string or number as your index value: a[0], a[5], a['hi'].

The problem is twofold. 1.) Storing large amounts of data in an index array means that you have to run through a loop when doing a look up. If you have less than a few hundred records this isn't so bad, but once you have a few thousand it presents a significant slowdown. And 2.) To loop through a dictionary array you need to use a for...in loop (JS version of a foreach/forall) which is *really* slow compared to a regular for loop.

Neither an index or a dictionary array are very good options for large amounts of data, or I should say specific types of large amounts of data as there are things which both do very well.

Therefore, I came up with a nice little method that has the flexibility of both. The solution is this, and it's a very simple one with the only drawback being a slight memory increase: Use both types of array at once.

In its simplest form it is the following class:

function List() {  
   this.Indexed = [];  
   this.Dictionary = [];
}

List.prototype.KeyValPair = function(Key, Value) {  
   this.Key = Key;  
   this.Value = Value;  
}

List.prototype.GetByKey = function(Key) {
   var i = this.Dictionary[Key];

   return this.Indexed[i].Value;
}

List.prototype.GetAtIndex = function(i) {
   return this.Indexed[i].Value;
}

List.prototype.Add = function(Key, Value) {
   var item = new this.KeyValPair(Key, Value);

   this.AddItem(item);
}

List.prototype.AddItem = function(KeyValPair) {
   this.Indexed.push(KeyValPair);
   this.Dictionary[KeyValPair.Key] = this.Indexed.length - 1;
}

List.prototype.AddRange = function(KeyValPairs) {
   for(var i = 0, len = KeyValPairs.length; i < len; ++i) {
      this.AddItem(KeyValPairs[i]);
   }
}

List.prototype.RemoveAtIndex = function(i) {
   if(undefined === this.Indexed[i]) {
      return;
   }

   var key = this.Indexed[i].Key;

   this.Indexed.splice(i, 1);
   this.Dictionary[key] = undefined;

   this.SyncList(i);
}

List.prototype.RemoveByKey = function(Key) {
   var i = this.Dictionary[Key];
   if(undefined === i) {
      return;
   }

   this.Indexed.splice(i, 1);
   this.Dictionary[Key] = undefined;

   this.SyncList(i);
}

List.prototype.RemoveIndexRange = function(From, To) {
   for(var i = From; i < To; ++i) {
      var key = this.Indexed[i].Key;

      this.Dictionary[key] = undefined;
   }

   this.Indexed.splice(From, To - From);

   this.SyncList(From);
}

List.prototype.RemoveKeyRange = function(Keys) {
   var minI = this.Indexed.length;

   for(var i = 0, len = Keys.length; i < len; ++i) {
      var key = Keys[i];
      var index = this.Dictionary[key];
      
      if(minI > index) {
         minI = index;
      }

      this.Dictionary[key] = undefined;
      this.Indexed.splice(index, 1);
   }

   this.SyncList(minI);
}

List.prototype.SyncList = function(From) {
   if(undefined === From) {
      From = 0;
   }

   for(var i = From, len = this.Indexed.length; i < len; ++i) {
      var keyValPair = this.Indexed[i];

      this.Dictionary[keyValPair.Key] = i;
   }
}

List.prototype.Clear = function() {
   this.Indexed.length = 0;
   this.Dictionary.length = 0;
}

I do have to apologize for any mistakes, I've written this from memory and not run it through any checking for errors. You can of course expand this to have AddRange and RemoveRange functionality fairly easily.

The greatest advantage of this approach is that it abstracts all need for looping to native code when it comes to doing a lookup. The only drawback is having to resync your list every time you remove an item.

I personally have used this method quite often and found it extremely useful for sifting through large amounts of data in JS.

Edit: I fleshed out the class a little bit... simply because I'm a code junky and couldn't help myself, so enjoy.