Do associative arrays perform like a hash table?

Question

So imagine that you have an associative array in JavaScript as such:

var hashTable = {};

hashTable["red"] = "ff0000";
hashTable["green"] = "00ff00";
hashTable["blue"] = "0000ff";

What happens when you retrieve a value like this:

var blue = hashTable["blue"];

Is the performance similar to that of a hashtable from another language? I mean, is there an actual hash function that is used to determine the location of the property or is there a looped search such as:

for (var color in hashTable) {
    if (hashTable.hasOwnProperty(color)) {
        //look for matching key
    }
}

Does the implementation vary from browser to browser? I couldn't find anything related to this specific topic. Thanks.

Answer 1

It's implemented differently in different javascript engines, and nowadays, it seems, objects aren't backed by "dictionary-like" data structures.

From https://developers.google.com/v8/design:

JavaScript is a dynamic programming language: properties can be added to, and deleted from, objects on the fly. This means an object's properties are likely to change. Most JavaScript engines use a dictionary-like data structure as storage for object properties - each property access requires a dynamic lookup to resolve the property's location in memory. This approach makes accessing properties in JavaScript typically much slower than accessing instance variables in programming languages like Java and Smalltalk. In these languages, instance variables are located at fixed offsets determined by the compiler due to the fixed object layout defined by the object's class. Access is simply a matter of a memory load or store, often requiring only a single instruction.

To reduce the time required to access JavaScript properties, V8 does not use dynamic lookup to access properties. Instead, V8 dynamically creates hidden classes behind the scenes. This basic idea is not new - the prototype-based programming language Self used maps to do something similar. In V8, an object changes its hidden class when a new property is added.

Firefox's IonMonkey does something similar. From an interview with a developer at Mozilla (http://www.infoq.com/news/2011/05/ionmonkey):

Dynamic languages probably don't have any inherent optimization advantages, but they do have interesting optimizations that static languages don't. For example, when you're writing JavaScript, objects appear to the user as hash tables, mapping property names to values. If they were actually implemented like that, they would be slow and use a lot of memory.

A good engine is able to internally group objects that look the same, sort of extracting an internal Java-like class out of them. The JIT can then treat the object as having an actual type, generating super fast code that avoids an expensive property lookup.

Answer 2

Javascript doesn't really have "associative arrays". {} returns a JavaScript object, which can have named properties and also a prototype which allows objects to inherit properties from other objects.

So performance will not be quite like that of a Hash table, since properties may be inherited from their prototype objects and searching for a given property by name may require traversing up the prototype tree before it is found.

This blog post may also provide some insight:

http://www.devthought.com/2012/01/18/an-object-is-not-a-hash/