Explaining the JavaScript Array: Sparse and Dense Arrays

The array is a popular concept across many programming languages. At first glance, arrays work in the same way, but the JavaScript array differs from languages like C++. The article explains the basics of how JavaScript arrays work under the hood. It includes what are indexes and what is a maximum size of an array. Aside from that, the article describes sparse and dense arrays.

JavaScript Array

Arrays are a way to store data in a list-like, ordered manner. Even though they might seem like a distinct data type, they really are not. JavaScript array is an object that inherits from the Array.prototype

If you would like to know more about prototypes, check out Prototype. The big bro behind ES6 class.

const animals = ['Dog', 'Cat'];
console.log(typeof animals); // object
console.log(Array.prototype.isPrototypeOf(animals)); true

You can go even further and change a regular object into an array!

const animals = {};
Object.setPrototypeOf(animals, Array.prototype);

animals.push('Dog');
animals.push('Cat');

console.log(animals[0], animals[1]); // Dog Cat

Not knowing that arrays are just objects can result in bugs. Imagine trying to check if a value is a regular object or an array.

if(typeof value === 'object') {
  console.log('The value is an object');
} else if (value instanceof Array) {
  console.log('The value is an array');
}

In the example above, we first check if a value is an object. The problem is that even if the value is an array, its type is still the object. To properly handle that, you need to check if it is an array first.

if(value instanceof Array) {
  console.log('The value is an array');
} else if (typeof value === 'object') {
  console.log('The value is a regular object');
}

Indexes

It might be surprising for you that array indexes are actually strings. This is because in JavaScript, objects property names are strings. When you access animals[0], the number is stringified. To be a proper array index, it has to be an unsigned 32-bit integer. This is because of the fact that the maximum length of an array is 2³² – 1.

new Array(Math.pow(2,32)) // Uncaught RangeError: Invalid array length

If you try to use a number bigger than 2³² – 1, it will also be stringified and treated as a regular property name for an object.

const animals = ['Dog', 'Cat'];
animals[Math.pow(2,32)] = 'Lizard';

console.log(animals.length); // 2
console.log(animals[Math.pow(2,32)]); // Lizard

Basic Ways to Create an Array

The most obvious way to create an array is to use the array literal.

const animals = ['Dog', 'Cat'];

It’s a shorthand that actually uses the Array constructor under the hood. You might as well do that:

const animals = new Array('Dog', 'Cat');

An interesting thing is that you can create an array with empty elements. We can use the fact that if you use the Array constructor with just one argument, it will be treated as a length of an array.

const arr = new Array(10);

When you iterate the array using the forEach function, they won’t show up. You can also create such an array using the array literal:

const animals = ['Dog', , 'Cat'];
console.log(animals.length); // 3

animals.forEach(animal => console.log(animal)) // Dog, Cat

Arrays that have such holes between elements are called sparse. There is an interesting trick to create dense arrays of a given size mentioned on the 2ality blog:

const arr = Array.apply(null, Array(5));

This line is equivalent to Array(undefined, undefined, undefined, undefined, undefined)

Such array is considered dense. All of its elements have a value, which is undefined and can be iterated.

Watch out for accidental sparse arrays. Their length does not match the actual amount of elements. You might create one by using delete.

const animals = ['Dog', 'Lizard', 'Cat'];
delete animals[1];

console.log(animals.length); // 3
console.log(animals); // ["Dog", empty, "Cat"]

If you wish to remove an element, don’t use the delete keyword.

Even if you delete the last element of an array, its length is still intact, therefore the array is sparse.

const animals = ['Dog', 'Lizard', 'Cat'];
delete animals[2];

console.log(animals.length); // 3

You can use functions like Array.prototype.slice or Array.prototype.pop.

With all that knowledge you might think of an idea of preallocating arrays.

const arrayLength = 1000000;

console.time('empty array');
const emptyArray = [];
for (let i = 0; i < arrayLength; ++i) {
    emptyArray[i] = i;
}
console.timeEnd('empty array');

console.time('preallocated array');
const preallocatedArray = new Array(arrayLength);
for (let i = 0; i < arrayLength; ++i) {
    preallocatedArray[i] = i;
}
console.timeEnd('preallocated array');

The performance boost (or decrease) that comes from the difference in the way that the engine handles such arrays depends on the engine implementation itself. This is because even though arrays are objects, the engine optimizes them as much as it can. Thanks to preallocating it, it is able to optimize it better. It might be a good idea to test the performance on a particular use case.

The length property

Let’s take a closer look at the length property.

const animals = ['Dog', 'Cat'];
Object.getOwnPropertyDescriptor(animals, 'length');

{
  'value': 2,
  'writable': true,
  'enumerable': false,
  'configurable': false
}

As you can see, it has no getter or a setter. Methods like push and splice actually update the length property.

If you add an element of a bigger index than the current length, the length will be updated.

const animals = ['Dog', 'Cat'];
animals[10] = 'Lizard';

console.log(animals.length); // 11

By that, you get a sparse array. You can also shorten an array by decreasing the length property.

const animals = ['Dog', 'Cat'];
animals.length = 1;
console.log(animals); // ['Dog']

animals.length = 2;
console.log(animals); // ['Dog', empty]

Summary

This article covers the basics of how JavaScript array work under the hood. It includes the JavaScript array being an actual object but treated a bit differently by the JavaScript engine when it has a chance. The article also explains what is the length of an array and that indexes are still strings, just like in regular objects. A thing to keep in mind about them is that they can’t be bigger than 2³² – 1. Having all that knowledge helps writing cleaner, better performing code.