Intro

In JavaScript, two major data structures are used to store key-value pairs: Objects and Maps. Both have their unique characteristics, benefits, and use cases, but they serve the same general purpose – to store data in a key-value format.

Objects are the fundamental blocks of JavaScript and have been around since its inception. They offer a straightforward way to create and manipulate named properties, which can be either simple values, other objects, or functions. Objects are ideal for scenarios when you know the keys in advance, as they provide a simple and efficient way to structure data.

On the other hand, Maps are a relatively newer feature introduced in ES6. They maintain the insertion order of elements, making them excellent for scenarios where data order matters. Maps also allow more key types than objects, broadening their usability.

Understanding the differences between these two data structures is crucial for effective JavaScript programming. It can greatly improve your code's performance and make it easier to manage and manipulate data.

So today, we'll talk about Object vs Map.

Brief history

Before ES6 introduced Maps, JavaScript Objects were the main choice for key-value storage. They were versatile, but had limitations. For example, they only accepted strings and symbols as keys, which limited their use. There are no methods for determining the map size for constant time, issues with iteration, and potential name collisions with object’s own properties.

const someMap = { a: 1, b: 2 };

// Object.keys takes O(n) time
const size = Object.keys(someMap).length;

// for .. in will return inherited properties
Object.prototype.someField = "some value";
const someOtherMap = { c: 3 };

for (const key in someOtherMap) {
    console.log(key); // 'c', 'someField'
}

// better to use Object.keys(), but again it requires O(n) time to create array with keys
for (const key of Object.keys(someOtherMap)) {
    console.log(key); // 'c'
}

// it's possible to accidently shadow method from prototype 
const methodsResultMap = { someMethod: true };
methodsResultMap["hasOwnProperty"] = false;

// Uncaught TypeError: methodsResultMap.hasOwnProperty is not a function
methodsResultMap.hasOwnProperty("someMethod");

Despite these drawbacks, Objects were often used for key-mapping storage because there were no other options. They provided a simple way to create and handle named properties. Plus, they've been part of JavaScript since the beginning, so developers were used to them. And so much accustomed to them, that now Map is still way underused.

const someMap = new Map([
    ['a', 1],
    ['b', 2]
]);

But how can we compare them in terms of performance? Is an Object still overall better than a Map, and are there valuable objections to using a Map? Let's find out.

Performance

Before taking any performance benchmarks, we need to answer the question: What should we benchmark?

So, I would choose the five main operations with a map: filling the map with values, checking if a value exists, retrieving a particular element by key, iterating through all elements, and clearing the map. At least, these are my general operations with map-like data structures.

Data preparation

To avoid any correlations between data and Object/Map instances, we need to ensure that we're using the same data for both implementations. For our benchmark scenarios, I'll prepare two different arrays: one for keys and one for values.

For keys, there will be two variants: strings of random lengths and fixed-size hash-like strings:

const keysDefault = ["aa", "aabbb", "aacb", ... ];
const keysHashes = ["c89efdaa54c0f20c7adf612882df0950f5a951637e0307cdcb4c672f298b8bc6", "ad7c5bef027816a800da1736444fb58a807ef4c9603b7848673f7e3a68eb14a5", ...];

For values, I'll also use two sets: random strings and objects with the same structure but with different property values (to simulate TypeScript scenarios like Map<String, SomeType>):

const valuesDefault = ["aa", "aabbb", "aacb", ... ];
const valuesObject = [
    {
        a: "aaa",
        b: "aabbb",
    },
    {
        a: "aacb",
        b: "bbbccc",
    },
    ...
]

As always, feel free to grab the sources and play with your scenarios.

Filling the map with values

As we decide to use arrays for keys and values in the case of an Object, the code will be as follows:

function fillObjectMap(keys, values) {
    const result = {};

    for (let i = 0; i < keys.length; i++) {
        result[keys[i]] = values[i];
    }

    return result;
}

And for Map:

function fillNativeMap(keys, values) {
    const result = new Map();

    for (let i = 0; i < keys.length; i++) {
        result.set(keys[i], values[i]);
    }

    return result;
}

Checking if a value exists or not

For checking values, I'll use an array with 50% of existing keys and 50% of random keys that don't exist.

For Object:

for (let i = 0; i < keysToCheck.length; i++) {
      result[i] = objectMap.hasOwnProperty(keysToCheck[i]);
}

For Map:

for (let i = 0; i < keysToCheck.length; i++) {
      result[i] = nativeMap.has(keysToCheck[i]);
}

Getting a particular element by key

For getting values the same array as for checking will be used.

For Object:

for (let i = 0; i < keysToGet.length; i++) {
      result[i] = objectMap[keysToGet[i]];
}

For Map:

for (let i = 0; i < keysToGet.length; i++) {
      result[i] = nativeMap.get(keysToGet[i]);
}

Iterating through all elements

Usually, in my daily work, I need to iterate through keys and values at the same time, so let's use the same pattern here.

For Object:

for (const [key, value] of Object.entries(objectMap)) {
    result.push([key, value]);
}

For Map:

for (const [key, value] of nativeMap.entries()) {
    result.push([key, value]);
}

Clearing the map

Since Object doesn't have methods to clear all keys, there is no reason to benchmark the clear method on Map. Instead, we'll compare the delete object[key] operator with the delete method.

Object:

for (let i = 0; i < keysToDelete.length; i++) {
      delete objectMap[keysToDelete[i]];
}

Map:

for (let i = 0; i < keysToDelete.length; i++) {
      nativeMap.delete(keysToDelete[i]);
}

Benchmarking

So, let's benchmark our cases to see which one, Object or Map, is faster.

As with the previous time, the approach is as follows:

• Generate input data;

• Do some warmup: run a couple of dozen loops to give the JS engine time to compile and optimize the methods;

• Run the benchmark: again, run a couple of dozen loops with the method calls, but now with time measurement;

• Check the results.

The source code for the benchmarking can be found here.

Results

Since we have a relatively large amount of data, to minimize variables such as GC, I'll conduct four iterations for each experiment (2 in the calling order of object → native, 2 – native → object to average GC times). We have a lot of data, so let's go through the numbers.

Filling the map with values

Let's start with the default variant, where the key and value are random strings with A-Za-z characters with a typical length ranging from 3 to 14.

Okay, it appears that the order of calls makes sense, albeit not entirely. We can also say that the relationship between size and time is almost linear, so our measurements seem logical because the insert operation cost in a map is O(1).

In general, Map is ~4.5-5 times faster for insertion. Let's examine the changes if we use a string with 256-bit hash as a key.

Still, on average, Map is around ~4 times faster, but now keys require much more memory and I suspect that degradation is related to GC work or other memory-related stuff. We'll examine memory consumption later. I won't add tables and charts for the case when values are objects, because there's nothing special there. Same trends. So, let's move on.

Checking if a value exists or not

Since existence check is also O(1) in a map, I don't expect any drastic difference in performance here.

From the values, we can see that on average, Map is only 7% faster. However, the larger the size, the smaller the difference, until eventually, for 500k, Object is faster. So, I would say that for checking Map and Object show the same performance in general. Hashed strings and objects-as-values don't change the overall behaviour, so I'll skip them.

Getting a particular element by key

Again getting an element is like existence check also O(1) in a map and we should get the same results.

Surprise, surprise! I thought we would get the same results as for the existence check, but Map outperforms Object here by approximately 2.8 times. If we take a look at Map times, we will notice that the has() and get() methods take almost the same time, while hasOwnProperty() is much faster than just object[key].

Iterating through all elements

It's expected that Map will be a clear winner here, because Object.entries takes O(n) time and we need to iterate through all elements – again O(n) time. Meanwhile, Map.prototype.entries() will return an iterator. But let's take a look at the numbers to prove our hypothesis.

Personally, I had hoped to see more linear characteristics of Object, but it is what it is. Map is ~12.8 times (!!!) faster. Even if O(n) + O(n) for Object is still O(n), the numbers don’t lie.

Clearing the map

Finally, the last operation - deletion. Again, it's algorithmic constant time. Should it be straightforward, or not?

No surprises this time. Map is faster by 22%. But again delete object[key] is a little bit faster, than Map.prototype.delete() for 500k elements.

Memory consumption

This time let’s compare memory consumption. As for key, I’ll use hashed string (to avoid key collisions) and as for values just a string like in tests above. Again, key-value pairs are the same for both Object and Map implementations. For each test there will be 1 iteration, since these are just memory allocations.

To explain why the numbers are so different, let's dive under the hood.

What’s under the hood?

Object

In the V8 JavaScript engine, an Object is a dynamic collection of properties. To optimize performance, V8 represents objects using hidden classes and inline caching. When an object is created, V8 assigns a hidden class to that object. As properties are added to the object, the hidden class transitions to new hidden classes to reflect the current state of the object.

For example, if we create an empty object:

const x = {};

V8 creates an initial hidden class (C0). If we then add a property to the object:

x.a = 1;

V8 transitions from the hidden class C0 to a new hidden class (C1), which represents an object with property a. This system allows V8 to use the hidden class of an object to quickly look up properties and improve the speed of property access.

However, this system isn't as efficient when properties are deleted from an object. When a property is deleted, V8 can't revert to the previous hidden class. Instead, it switches to a slower mode of operation where properties are accessed via a dictionary-like data structure. This is why deleting properties from an object is slower compared to other operations.

In addition, since Object is not specifically designed for use as a hash map, it does not have built-in methods for common map operations. As we've seen from our tests, workarounds for insufficient methods can drastically affect performance.

Who can tell more about hidden classes than the V8 developers? Here is a detailed article about the nature of hidden classes in V8.

Map

In contrast, Map uses a hash table data structure underneath. A hash table, also known as a hash map, is a data structure that implements an associative array abstract data type, a structure that can map keys to values. Hash tables use a hash function to compute an index into an array of buckets or slots, from which the desired value can be found. This makes it a fast and efficient data structure for finding, inserting, and deleting data.

Since a classic implementation of a hash map (with a hash function and buckets) doesn't support ordering, a deterministic hash table algorithm is used.

Talking about hash tables we need to mention rehashing. Rehashing is a technique used in hash tables to manage size and efficiency. It is triggered when the load factor (entries divided by buckets) exceeds a certain limit. The process involves:

1. Creating a larger hash table.

2. Computing the hash for each entry in the old table based on the new size.

3. Placing each entry in the new table at the position determined by its hash.

4. Deallocating memory for the old table.

This ensures efficient operations but temporarily increases memory usage and operation time.

It's interesting that, unlike languages such as Java or Python, the V8 map implementation can not only increase the bucket count on insertion, but it can also decrease the bucket count on deletion. So that, when we actively working with a lot of insertion and deletion we should always keep in mind the two following things:

• set() can take O(n) when hash table grows and doing rehashing

• delete() can take O(n) when hash table shrinks and doing rehashing

In terms of memory structure, unlike Object, V8 uses a more appropriate single fixed-size array with a header, hash table, and data table. The header stores metadata such as entry count, the hash table stores buckets, and the data table stores entries.

If you want to dive deeper, I’d recommend this article about map implementation.

Summary

To summarize the results of the performance testing, the following can be said:

• For insertion of values, Map is approximately 4.5-5 times faster than Object.

• For checking if a value exists, Map and Object show similar performance.

• For getting a particular element by key, Map outperforms Object by about 2.8 times.

• The map's has() and get() methods take almost the same amount of time, while Object.hasOwnProperty() is significantly faster than object[key].

• In terms of iterating through all elements, Map is approximately 12.8 times faster than Object.

• For deleting properties, Map is faster by 22%.

• In terms of memory consumption, both Map and Object use a significant amount of memory, but Map is more efficient.

Obviously, it's highly recommended to use Map for key-value storage in the new code, instead of Object, especially if you work a lot with entry iteration.

Do you need to refactor your Object code to use Map? If you don't use huge maps with a lot of iterations through entries – I'd say to consider a move. But in other cases, definitely not. Again, everything depends on the results of the profiling step.

That's it for today, thank you for your attention. Feel free to write a comment with your favourite JS constructions, and we'll sort out their performance.