I have always read and heard that maps are much faster than arrays for searches. Until I decided to see how much I did a jsperf: link
What I would like to understand is what mechanisms make mapping faster, and why.
edit: In jsperf above, the values on the map are arbitrary. What I'm really looking for are the keys.
The idea is that the indexOf method will scroll each element of the array by checking if the value matches, in which case the cost of that function is O (N) #
You can check here in the V8 code, that the search is always incremental.
Now for Hash, the key is mapped to the value, that is, when doing the search what happens is that the search value 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).
Here's an example of Hash implementation , where the function used is a module.
To search for an element in an arbitrary vector, we need to traverse the vector elements one by one. In a vector of N elements, this means that on average you will have to do N / 2 tests to find the element of the vector, which can be quite 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 for element to be fast. Generally, the number of operations required is constant or logarithmic in the number of elements, rather than being directly proportional.
An interesting exercise is to make a chart showing the times of the two versions for different numbers of elements.
As for the vector, this data structure is optimized for fast 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 indexOf.
Finally, if your vector is sorted with elements in ascending order, you can do a binary search , while instead of linear sweep, which is much faster. It's the difference between looking up a telephone number in an alphabetically organized phone book and doing the same search in a whole jumbled list.
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 to be able to execute.
Arrays have a better performance than maps since you know which element you want to access, as much as maps have constant access, arrays have instant access if called by their index.
I've done a review in jsperf that shows just this behavior, you'll see that Arrays 2 is the fastest way to access the array elements directly.
You have a few things wrong with your test:
Leave the definition of the object and array out of the test, in setup , so that the declaration time and value assignment does not count in the test
Leave the loop on jsperf's own behalf
Use the same key or value verification method (in your test, you checked to see if a given key existed on the object, but in the array it checked to see if a given value > existed in it).
http://jsperf.com/maps-vs-arrays/5 "> link .
