We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies.

We use cookies and other tracking technologies to improve your browsing experience on our site, analyze site traffic, and understand where our audience is coming from. To find out more, please read our privacy policy.

By choosing 'I Accept', you consent to our use of cookies and other tracking technologies. Less

We use cookies and other tracking technologies... More

Login or register
to apply for this job!

Login or register to start contributing with an article!

Login or register
to see more jobs from this company!

Login or register
to boost this post!

Show some love to the author of this blog by giving their post some rocket fuel 🚀.

Login or register to search for your ideal job!

Login or register to start working on this issue!

Engineers who find a new job through JavaScript Works average a 15% increase in salary 🚀

Blog hero image

Explaining the JavaScript Array: Sparse and Dense Arrays

Marcin Wanago 18 October, 2018 | 4 min read

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 232 – 1.

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

If you try to use a number bigger than 232 – 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

Screenshot-from-2018-10-14-16-29-35.png

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);

blog2.png

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));

blog3.png

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 232 – 1. Having all that knowledge helps writing cleaner, better performing code.

Originally published on wanago.io

Related Jobs

Related Issues

viebel / klipse-clj
viebel / klipse-clj
  • Open
  • 0
  • 0
  • Intermediate
  • Clojure
viebel / klipse
  • Open
  • 0
  • 0
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 1
  • Intermediate
  • Clojure
  • $100
viebel / klipse
  • 1
  • 0
  • Intermediate
  • Clojure
viebel / klipse
  • Open
  • 0
  • 0
  • Intermediate
  • Clojure
  • $80
viebel / klipse
  • Open
  • 0
  • 0
  • Advanced
  • Clojure
  • $80
viebel / klipse
  • Started
  • 0
  • 2
  • Advanced
  • Clojure
  • $180
viebel / klipse
  • Started
  • 0
  • 1
  • Intermediate
  • Clojure
viebel / klipse
  • Started
  • 0
  • 3
  • Intermediate
  • Clojure
  • $80

Get hired!

Sign up now and apply for roles at companies that interest you.

Engineers who find a new job through JavaScript Works average a 15% increase in salary.

Start with GithubStart with Stack OverflowStart with Email