What exactly are sparse arrays in JavaScript?

JavaScript is full of suprises every now and then. The more of these surprises that you know, the better you can stand as a JavaScript developer, capable of debugging a given program effectively.

The surprise that I'm interested in discussing with you in this article is related to working with arrays — that is, sparse arrays. We shall also discuss a bit about the internals of JavaScript engines in the end (although I'll keep that fairly short because such discussion can become unwieldy quickly).

What are sparse arrays?

Let's start by considering the Array() constructor when it's given an integer argument:

new Array(10) // Create an array of 10 elements

To be precise, Array(n), where n is an integer, creates an array with n empty slots — sometimes also referred to as holes. These slots are completely non-existent; don't make the mistake of thinking that they're undefined.

Logging the array makes this apparent:

let arr = new Array(10);
console.log(arr); // [empty x 10]

The console typically shows something like empty for an empty slot.

Speaking of which, these empty slots make the array a sparse array. Also known as a holey array, it is simply an array where elements don't exist at contiguous positions; instead the elements exist sparsely in the array.

The opposite of sparse arrays are called dense arrays. All the elements in a dense array are tightly packed with one another — there are no holes in between. For this reason, they are also known as packed arrays.

Now, new Array(n) isn't the only way of getting a sparse array; there are others too, as discussed up next.

Getting sparse arrays

There are five ways of getting sparse arrays in JavaScript:

• Calling new Array(n), where n is an integer.
• Omitting elements in array literals.
• Removing an array element using delete.
• Assigning to an out-of-bounds index.
• Manually increasing the value of the array's length.

You've already seen the first one, i.e. new Array(n), above, hence I won't be discussing it here again. Let's go over the others.

Omitting elements in array literals

Suppose that while typing out an array literal, you mistakenly add an extra comma between two elements:

[1,, 2]

Congrats! You just created a sparse array. The second element which you didn't mention is taken as an empty slot.

let arr = [1,, 2];
console.log(arr); // [1, empty, 2]

Removing an element using delete

The reason why it's recommended to avoid using delete for removing array elements is because of its production of a sparse array (and because it doesn't update the array's length).

Following is a quick example:

let arr = [1, 2, 3];
delete arr[1];

console.log(arr); // [1, empty, 3]

Calling delete arr[1] removes the second element from the array but introduces an empty hole in place of it.

Assigning to an out-of-bounds index

You might know that JavaScript allows you to assign a value to any arbitrary index in an array (something which I consider to be a bad design decision). With an assignment to an out-of-bounds index (an index which is beyond the array's length property), you get a sparse array:

let arr = [1, 2, 3];
arr[5] = 10;

console.log(arr); // [1, 2, 3, empty, empty, 10]

Frankly speaking, there isn't much utility, if at all, of such a kind of code. Why would anyone want to assign a value to an arbitrary index in an array beyond its length?

Increasing the value of the array's length property

The length property of arrays in JavaScript isn't read-only; you can actually assign an integer to it to shrink or expand the underlying array to the given length.

When you decrease the value of length, the array is reduced to that length, with extra elements removed from the end:

let arr = [1, 2, 3];
arr.length = 1;

console.log(arr); // [1]

But this isn't interesting for the current discussion. What's interesting is when you increase the value of length. In that case, the array is expanded to that length, but most importantly, this expansion introduces empty holes into the array and consequently makes it sparse:

let arr = [1, 2, 3];
arr.length = 4;

console.log(arr); // [1, 2, 3, empty]

Once again, there isn't much utility to manually increasing the value of an array's length property. We're better off sticking to the sensible approaches like push(), unshift(), or splice().

A note on length

The first definition of the length property that comes to mind is that it is the total number of elements in an array. Ideally, this really should've been the case but it's NOT.

Consider the following:

let arr = [1, 2, 3];

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

delete arr[2];

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

After calling delete arr[2], we expect the length of arr to go down to 2 but that's far from reality — the array's length stays at 3. Hence, if you take length to return the number of elements, this is a counterexample to that definition.

As another example, consider what happens when you increase the value of length (or maybe assign to a far-fetched index):

let arr = [1, 2, 3];

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

arr.length = 100;

console.log(arr.length); // 100

After the mutation of the length property, the array's length changes, however it still stores only three elements. Once again, length is, strictly speaking, NOT the total number of elements in the array.

Honestly, it's somewhat challenging to give a rigorous definition of the length property of arrays in JavaScript. Some resources claim that it's one greater than the last index of an array but in the case of new Array(n), where there is just no element and therefore no "last index," this does NOT hold.

For the sake of simplicity and its intended semantics, I still prefer to define length as representing the total number of elements of an array. This is because sparse arrays are the only place where this definition doesn't hold and it's generally NOT recommended to work with sparse arrays (for reasons which I'll discuss later).

Accessing an empty slot

What happens when you try to access an empty slot in an array? Well, you get undefined in return:

let arr = new Array(10);

console.log(arr[0]); // undefined
console.log(arr[9]); // undefined

It's superbly important to note that although accessing an empty slot returns undefined, undefined does NOT actually exist at the given position; an empty slot is... well... empty.

This means that if, for some weird reason, you need to determine whether a given index represents an empty slot or not, comparing the value of the element at that index to undefined is a wasted effort — you'll get undefined regardless of whether the index is out-of-bounds (beyond length), represents an empty slot, or represents an element with the value undefined.

The following code clearly demonstrates this:

let arr = [1, undefined,, 2];

// Accessing the `undefined` value
console.log(arr[1]); // undefined

// Accessing the empty slot
console.log(arr[2]); // undefined

// Accessing a truly non-existent index
console.log(arr[1000]); // undefined

arr[1] represents the undefined element, arr[2] represents an empty slot, and arr[100] represents an out-of-bounds access. However, each one yields back the same result — undefined. It's hard to distinguish between them.

The next section discusses how to reliably check for an empty slot (although I think there should never really be a need to).

Checking for an empty slot

If a given index of an array corresponds to an actual value — be that undefined — you can easily determine that with the help of the hasOwnProperty() method (or even the in operator).

Array indexes are also properties of the array at the end of the day — more specifically, its own properties (not the ones inherited from the prototype chain). Therefore, hasOwnProperty() can be used to check if an index really exists in an element, even if it holds undefined.

Here's a quick demonstration:

let arr = [1, undefined,, 2];

console.log(arr.hasOwnProperty(0)); // true
console.log(arr.hasOwnProperty(1)); // true
console.log(arr.hasOwnProperty(2)); // false

arr.hasOwnProperty(2) returns false since index 2 represents an empty slot (notice the two consecutive commas in the array literal; they implicitly cause the creation of an empty slot).

However, hasOwnProperty() can't differentiate between empty slots and out-of-bounds indexes. For example, take a look at this code:

let arr = [1, undefined,,];

console.log(arr.hasOwnProperty(2)); // false
console.log(arr.hasOwnProperty(100)); // false

arr.hasOwnProperty(100) returns false and so does the previous call to arr.hasOwnProperty(2). How do you distinguish between these? Well, one simple trick is to incorporate length into the mix as well.

That is, when an array doesn't have a property on it (as indicated by hasOwnProperty() returning false), you can further check if the given index is less than the array's length. If it really is, then the index represents an empty slot.

I've created the following helper function implementing this check:

function isEmptySlot(arr, index) {
   return !arr.hasOwnProperty(index) && index < arr.length;
}

The latter part, i.e. index < arr.length, is the crux of distinguishing between out-of-bounds indexes and indexes representing empty slots. Let's test this function:

function isEmptySlot(arr, index) {
   return !arr.hasOwnProperty(index) && index < arr.length;
}

let arr = [1, undefined,,];

console.log(isEmptySlot(arr, 1)); // false
console.log(isEmptySlot(arr, 2)); // true
console.log(isEmptySlot(arr, 100)); // false

What to learn from this?

So what should you take from this discussion of sparse arrays in JavaScript. Simple: Avoid sparse arrays completely! It can't get any simpler than that.

Do NOT do any of the five things listed above that result in a sparse array.

• When creating arrays, avoid new Array(n) to the extent you could (which is almost always).
• Double-check your array literals for any double commas; surprisingly enough JavaScript wouldn't complain (which it should).
• Refrain from using delete to remove array elements. Use pop(), shift(), or splice().
• Refrain from mutating length.
• Refrain from assigning to an arbitrary index (or at least check before doing so).