What are arrays?
In the standard definition of Array data structures in Computer Science, arrays are a collection of like elements where any member may be accessed by an index. That definition doesn’t sound very different from an Hash Table or it’s ilk, but the key distinctions here are that the elements of the array must take up the same size in memory, and that the array indexes need to be numeric so that the logical address of any individual element can be derived from that number.
Arrays are typically created from contiguous memory. This makes for a simple calculation, like if we know that an Array lives at memory address 1024 and that each element in the array holds a 32-bit reference to an object then we can look up any individual item with a simple computation:
element_address = (1024 + (32 * index))
You want the element at index 14? Here ya go, it’s the 32bits starting at address 1472!
What makes arrays important?
It’s important that indexes be numeric because it means we can compute the memory address of any element in the array in constant time. This makes for the fastest random access of any data structure – even in the worst case scenario. Hash Tables are great and all, but there is overhead associated with their hashing and collision handling.
Check out the Big-O Algorithm Complexity Cheat Sheet for a nice visual comparison.
So, back to our original question…
When is an array, not an array?
Sure, we can do all the normal array type operations. But we can also do weird stuff.
Here’s a simple array definition, but how much memory do you think is ultimately allocated by this operation?
var myArray = [0,1,2];
myArray = 100000; // JS is cool with this
myArray[-1] = -1.33333; // and this
myArray['mmm...need more coffee'] = 'go get it, lazy bones!'; // this too
The above examples show several crimes against nature. Exceeding the bounds of original declaration, negative indexes, non-numeric indexes, setting different value types…heinous crimes indeed. These operations are incompatible with the definition above.
So, what have we learned?
Thanks for reading, let me know what you think in the comments!
Like this post? It was a result of research for an upcoming podcast on data structures, so subscribe to Coding Blocks if you are interested in topics like this.