The World of Sparse Arrays in JavaScript

Me: The length of an array is determined by the number of its elements, right?

JavaScript: Hmm, not really . . .

Ah, JavaScript arrays! 😊

At first glance, they seem so simple, just a linear collection of items, right? But dig a little deeper, and you'll find some surprises. Call them just another nod to the sometimes perplexing nature of JavaScript.

In this post I will talk about:
✅ what determines the length of an array
✅ the difference between sparse and dense arrays
✅ how to work with sparse arrays

The Case of the Mysterious Array Length

Remember the first time you thought you'd mastered arrays? Same. I thought the array length was determined by the number of defined elements. But alas, JavaScript had other plans.

Sparse Arrays

Let's create an empty array:

let arr = []  ✅

Looks harmless, right? Now let's put an element at index 2:

arr[2] = 5  ✅

What do you think arr.length would be? If you said 1, join the club of the fooled!

console.log(arr.length) -> 3  😱

Yes, arr.length is 3, not 1!

In JavaScript, arr.length = highest index + 1 (plus 1 because we start indexing at 0).

It's true, this is not your everyday array. It's what we call a sparse array. And if you're wondering what a sparse array is, try logging the array to the console:

console.log(arr) -> [ <2 empty items>, 5 ]  🤔

You'll notice that there are two empty spots preceding the value 5. These empty spots, called also holes, make the array sparse, as it contains gaps where no explicit values have been set.

Think of it like a parking lot where you decide to park your car in a spot marked #10. This implies that there are 9 other spots before it. Even if these preceding spots are empty, the parking lot is still considered to have a capacity of 10 spots.

JavaScript arrays operate on the same principle: marking a spot at index 2 means there are two other spots before it (at indices 0 and 1), making the array's length 3.

Dense Arrays

In contrast, you may be more accustomed to dense arrays, where every index corresponds to a value, even if it's set to undefined.

let dense = [ "dense", "arrays", "are", "boring"]  😉

In dense arrays, there are no gaps; each slot in the array is accounted for, whether it's holding a value or is explicitly undefined.

Sparse Array Meets map( )

A Surprise

So, you might wonder, what happens when you run the map() function on our sparse array?

const newArr = arr.map(x => x + 3)

console.log(newArr) -> [ <2 empty items>, 8 ]  😲

Expected to see NaN (ie "Not-a-Number")? So did I. But it turns out that map() just ignores the empty spots!

Think of a sparse array as a parking lot divided into two sections: free parking and paid parking. Free parking spaces are like the empty slots in our array. Our parking officer - the map() function - ignores them and walks right past them.

A Question

A fair question to ask: if the empty spots are ignored, why aren’t they just eliminated from the new array? Because after our parking officer finishes their rounds, the parking lot (our array) must remain the same size!

Similarly, JavaScript's map() method will always return a new array of the same length as the original. It doesn't eliminate empty spots; it keeps them as they are, ensuring that the length of the array remains consistent.

An Experiment

Now let's explicitly set the first element as undefined:

arr[0] = undefined
console.log(arr) -> [ undefined, <1 empty item>, 5 ]  ✅

const newArr = arr.map(x => x + 3)

console.log(newArr) -> [ NaN, <1 empty item>, 8 ]  😲

Notice how the first element of the new array is now NaN. Why?

When we use map() on an array in JavaScript, the function we provide as an argument is called on each index that has been assigned a value. We know it ignores the empty spots, but it does pay attention to every element with an assigned value. Even when that value is undefined!

So if we explicitly set an element to undefined, map() will indeed invoke the function on that element. In our specific example of arr.map(x => x + 3), the function is attempting to add 3 to undefined. In JavaScript, any arithmetic operation involving undefined will output NaN.

To exhaust our parking lot analogy: when an array element is explicitly set to undefined, it's like a metered but unoccupied spot in the paid parking section. Our parking officer (again, the map() function) walks by and makes note of it. In JavaScript terms, that means paying attention to that value and trying to work with it.

A Note

In the above example, we got lucky. JavaScript will automatically convert undefined to NaN when it tries to perform an arithmetic operation. The map() function will then continue to operate on the rest of the elements in the array.

It is different with strings. When map() encounters undefined and the function is trying to, let’s say, convert it to lowercase, you'll run into a TypeError because undefined is not a string and does not have a toLowerCase() method. The execution stops at that point.

const array = ['HELLO', 'WORLD', undefined]

const newArray = array.map(element => element.toLowerCase())  🚫
//TypeError: Cannot read properties of undefined 

To ensure your code runs smoothly, it's essential to handle undefined values before calling any methods on them: filter them out before applying map() or use a try-catch block. And of course, do not purposefully declare your elements as undefined! We did it here in the name of learning. 😊

Sparse Array Meets filter()

Shouldn't we just filter out the empty spots as well? Of course! You can filter out empty spots by using the filter() method. Remember how map() ignores them? Well, the empty slots are being treated as undefined for the purpose of filtering!

Let’s take our updated array and apply filter() to it. The array has undefined at first index, followed by an empty spot, and value 5 at index 2.

console.log(newArr) -> [ undefined, <1 empty item>, 5 ]

const filteredNewArr = newArr.filter(x => x !== undefined);

console.log(filteredNewArr) -> [5]  ✅

Ok, but what if, theoretically, you only want to remove the holes but keep the undefined? You can do something like:

const filteredNewArr = newArr.filter((item, index) =>         
                            arr.hasOwnProperty(index));

console.log(filteredNewArr) -> [ undefined, 5 ]  ✅

In this example, hasOwnProperty() checks if the array has an actual value, including undefined, at each index. Therefore, it will return true for all indices where a value exists and false for holes.

To Recap

✔️ Not all array are dense. Some have holes and we call them sparse.

✔️ For the purpose of finding the length, we must count the holes as well.

✔️ The map() method ignores the holes, but it does not remove them.

✔️ We can remove the holes with the filter() method.

Are We Ready to Conclude?

Is a sparse array a thing in real-world applications? I don’t have an answer yet, and promise to update the post if and when I do. But then, even if the answer is a resounding no, it does not matter. It would not make these quirky facets of JavaScript arrays any less captivating to explore. Long live quirkiness!

Keep exploring! ⛵

Resources

JavaScript: The Definitive Guide
7th Edition, by David Flanagan
O'Reilly Media, 2020


Blog post originally published on August 1, 2023 on corinamurg.dev.

Credit: Photo by Krzysztof Kotkowicz on Unsplash