Which is faster for finding element in javascript array?

Question

Hi, I'm a noob and wrote a whole program without knowing the easy way to find an element in an array...

my_array.indexOf("find this value");

Is indexOf a lot better than storing how many elements are in an array, and looping through the array until you find the element you want? I could have simplified my code alot.

I tried to make my lookups constant time by using multiple arrays, and storing the keys. It makes insertions/deletes slow because I have to update the keys though.

Should I have just used indexOf?

Thanks

Answer 1

The vast majority of the time you are much better off to use a native function that has been optimized over whatever solution you come up with. Aside from that, however, you said something about storing the amount of elements in the array. Not sure why you did that when arrays have a .length property.

Answer 2

You could use a hash table implementation in javascript to map values to array indices.

Answer 3

Javascript basically has two types of collections: Arrays and hashmaps. Both are a bit special. The hash map is just an object with named properties. The keys are strings that you use to access the values directly. Here's an example:

// create the hash map
var hashMap = {};
// add a value
var key = "John Dillinger";
hashMap[key] = "Criminal";
// retrieve the value
var stuff = hashMap[key];

Javascript arrays have a double functionality. They are of course arrays, but are also stacks. A stack follows the "last in - first out" rule. Here's an example of an array and a stack:

// Array example
var anArray = []; // or: var anArray = new Array();
anArray[0] = "some value";
alert(anArray[0]); // pops up "some value"
// Stack example
var stack = [];
stack.push("first");
stack.push("second");
alert(stack.pop()); // pop up "second"

Finally, for some problems a linked list could come in handy. For that you use an object. Something like this:

var linkedList = {value: "stuff"};
linkedList.next = {value: "other"};
linkedList.next.next = {value: "yet another value"};
// Traverse the list
var node = linkedList;
while(node) {
  alert(node.value)
  node = node.next;
}

Given the problem that you describe, I would use a hash map. Just remember to choose the correct collection type for any given problem.

Answer 4

It's probable that the implementation of the indexOf method just loops over the array until it finds the requested value because in the general case that's about all you can do. Using it would clean up your code but is unlikely to make it faster. (There are faster ways of searching arrays but they carry certain restrictions and/or up-front costs.)

You should use the right data structure for the job. Arrays are for situations where order is important. If you find yourself searching through them a lot you should probably be using a hash instead. Hashes are unordered but lookups happen in constant time (no searching).

Answer 5

Native functions should be faster since it would be the runtime-engine precompiled code.

However, indexOf wasn't implemented until version 1.6, meaning it doesn't work in jscript/IE afaik.

But I would just prototype a workaround for it in that case. native functions is usually your best option.

In your case however, it seems that you want a hashmap, which in js is just a regular object as Helgi pointed out.

Answer 6

I've implemented javascript HashMap which code can be obtained from http://github.com/lambder/HashMapJS/tree/master

Here is the code:

/*
 =====================================================================
 @license MIT
 @author Daniel Kwiecinski <[email protected]>
 @copyright 2009 Daniel Kwiecinski.
 @end
 =====================================================================
 */
var HashMap = function() {
  this.initialize();
}

HashMap.prototype = {
  hashkey_prefix: "<#HashMapHashkeyPerfix>",
  hashcode_field: "<#HashMapHashkeyPerfix>",

  initialize: function() {
    this.backing_hash = {};
    this.code = 0;
  },
  /*
   maps value to key returning previous assocciation
   */
  put: function(key, value) {
    var prev;
    if (key && value) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        prev = this.backing_hash[hashCode];
      } else {
        this.code += 1;
        hashCode = this.hashkey_prefix + this.code;
        key[this.hashcode_field] = hashCode;
      }
      this.backing_hash[hashCode] = value;
    }
    return prev;
  },
  /*
   returns value associated with given key
   */
  get: function(key) {
    var value;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        value = this.backing_hash[hashCode];
      }
    }
    return value;
  },
  /*
   deletes association by given key.
   Returns true if the assocciation existed, false otherwise
   */
  del: function(key) {
    var success = false;
    if (key) {
      var hashCode = key[this.hashcode_field];
      if (hashCode) {
        var prev = this.backing_hash[hashCode];
        this.backing_hash[hashCode] = undefined;
        if(prev !== undefined)
          success = true;
      }
    }
    return success;
  }
}

//// Usage

// creation

var my_map = new HashMap();

// insertion

var a_key = {};
var a_value = {struct: "structA"};
var b_key = {};
var b_value = {struct: "structB"};
var c_key = {};
var c_value = {struct: "structC"};

my_map.put(a_key, a_value);
my_map.put(b_key, b_value);
var prev_b = my_map.put(b_key, c_value);

// retrieval

if(my_map.get(a_key) !== a_value){
  throw("fail1")
}
if(my_map.get(b_key) !== c_value){
  throw("fail2")
}
if(prev_b !== b_value){
  throw("fail3")
}

// deletion

var a_existed = my_map.del(a_key);
var c_existed = my_map.del(c_key);
var a2_existed = my_map.del(a_key);

if(a_existed !== true){
  throw("fail4")
}
if(c_existed !== false){
  throw("fail5")
}
if(a2_existed !== false){
  throw("fail6")
}

Bon Appétit, Daniel Kwiecinski