11
I have always read and heard that maps are much faster than search arrays. Until I decided to see how much and did a jsperf: http://jsperf.com/maps-vs-arrays/
What I’d like to do is understand which mechanisms make searching maps faster, and why.
Edit: in the jsperf above, the values on the map are an arbitrariness. What I’m really looking for are the keys.
13
To search for an element in an arbitrary vector it is necessary to traverse the elements of the vector one by one. In an array of N elements, this means that on average you will have to do N/2 tests to find the element of the vector, which may be enough if the vector is large.
On the other hand, the Javascript map is implemented using a hash table, which is a data structure specially designed so that the element search operation is fast. Generally, the number of operations required is constant or logarithmic in the number of elements, rather than directly proportional.
An interesting exercise is to make a graph showing the times of the two versions for different numbers of elements.
As for the vector, this data structure is optimized for quick access to an element, given an index. If you already know the index of an element, you can access it directly using vetor[i], without having to do an index.
Finally, if your vector is ordered with the elements in ascending order, it is possible to make a binary search, instead of linear scanning, which is much faster. It’s the difference between searching for a phone number in an alphabetically arranged phone book and searching the same list in a jumbled array.
10
The idea is that the method indexOf will traverse each element of the array checking if the value corresponds, in which case the cost of this function is O(N) (see here about this notation).
You can check here in the V8 code, the search is always incremental.
For Hash, the key is mapped to the value, that is, when searching what happens is that the value of the search is transformed into an index (using a function) that is used to fetch the value. Therefore the cost of accessing the value of a Hash is O(1).
See an example of Hash implementation, where the function used is module.
6
Maps or hashmaps have a hash which allows you to locate your elements in O(1). While in arrays you need to search for the element in order to execute.
Arrays perform better than maps since you know which element you want to access, because even though maps have a constant access arrays have instant access if called by their index.
I made a jsperf revision that shows precisely this behavior, will see that the Arrays 2 is the fastest to access the array elements directly.
Interesting that Arrays 2 is faster in Firefox, but not in Chrome. I believe it is because the hash function of Chrome should be absurdly faster than that of Firefox.
I ran the tests on IE10. Results similar to Firefox, but with Arrays 2 even faster than maps. Interesting.
@Yes I noticed that later, yes it seems that the hash of Chrome is much superior. But that the performance of standard arrays in Chrome leaves something to be desired by comparison.
"arrays have instant access if called by their index" that only would be true if the Javascript engine optimized arrays to be arrays anyway, just like in other languages. But by standard, arrays and objects are practically the same thing in Javascript. No difference, not even in the internal representation. The indexes of an array are strings, not integers.
6
There are some incorrect things in your test:
Leave the object definition and array out of the test, in the setup, so that the time of the declaration and assignment of value does not count in the test
Leave the loop to jsperf itself
Use the same key or value verification method (in your test, you checked if determined key existed in the object, but in the array checked if determined value existed in it).
Since in Javascript arrays are implemented as objects with small changes, a key search should be equivalent in both cases. And this is proven (in Chrome) by the following test: http://jsperf.com/maps-vs-arrays/5.
The values on the map are just an arbitrariness. The search I’m doing is for the keys.
So that’s it then :)
Browser other questions tagged javascript quest
You are not signed in. Login or sign up in order to post.
The answer is correct, but it is worth noting that in Javascript this "data structure optimized for quick access" does not exist: arrays and objects are implemented in the same way. See that answer for more details. Other languages (e.g.: C, Java) use arrays to represent arrays, and hashes for hashes, so it makes a difference. Javascript no.
– mgibsonbr
mgibsonbr: Although everything is semantically objects with strings keys, the most modern implementations use, yes, vectors when possible. Behind the cloths, they detect when there are consecutive numeric keys and use a vector for them and a hash table for the rest. In some cases it goes even further: for example, V8 has separate implementations for object vectors (pointers) and double vectors
– hugomg
Interesting to know, I always thought that - if the engine were to do some optimization - it would do it based on the prototype of the object (i.e. the type
Array), and not in your content. But that’s what you said - and the information contained in the link - makes perfect sense.– mgibsonbr