Do associative arrays compose a hash table?

Question

So, imagine 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 this value:

 var blue = hashTable["blue"]; 

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

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

Does the implementation impact from browser to browser? I could not find anything related to this particular topic. Thanks.

Answer 1

It is implemented differently in different javascript engines, and currently, it seems, objects are not supported by data structures like a dictionary.

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

JavaScript is a dynamic programming language: properties can be added and removed from objects on the fly. This means that the properties of the object may change. Most JavaScript engines use a dictionary-like data structure as a repository for object properties — each access to properties requires a dynamic search to resolve the location of the property in memory. This approach makes accessing properties in JavaScript generally much slower than accessing instance variables in programming languages ​​such as Java and Smalltalk. In these languages, instance variables are located at fixed offsets defined by the compiler due to the layout of the fixed object defined by the object class. Access is simply a matter of loading or storing memory, often requiring only one instruction.

To reduce the time required to access JavaScript properties, V8 does not use dynamic search to access properties. Instead, V8 dynamically creates hidden classes behind the scenes. This basic idea is not new - a prototype-based programming language. Do-it-yourself cards to do something like this. In V8, an object changes its hidden class when a new property is added.

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

Dynamic languages ​​probably do not have any inherent optimization benefits, but they have interesting optimizations that static languages ​​do not have. For example, when you write JavaScript, objects are displayed to the user as hash tables, matching property names with values. If they were implemented in this way, they would be slow and use a lot of memory.

A good engine is able to internally group objects that look the same, for example, extracting an internal Java-like class from them. JIT can then process the object as having the actual type, generating super fast code that avoids the expensive search for properties.

Answer 2

Javascript really does not have "associative arrays." {} returns a javascript object which may have named properties as well as a prototype , which allows objects to inherit the properties of other objects.

Thus, the performance will not be the same as in the Hash table, since properties can be inherited from prototype objects and it may take a prototype tree to find the specified property by name before it is discovered.

This blog post may also give some insight:

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

Answer 3

The term associative array describes its use: it is a key-value container used to associate one thing with another. But the term hash table describes its implementation: it uses a hash function to find elements in the underlying array. In some implementations, there may be an associative array that uses mahogany or another data structure, but not a hash table.