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.
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