JavaScript array random index insertion and deletion

I'm inserting some items into array with randomly created indexes, for example like this:

var myArray = new Array();开发者_运维百科
myArray[123] = "foo";
myArray[456] = "bar";
myArray[789] = "baz";
...

In other words array indexes do not start with zero and there will be "numeric gaps" between them. My questions are:

• Will these numeric gaps be somehow allocated (and therefore take some memory) even when they do not have assigned values?
• When I delete myArray[456] from upper example, would items below this item be relocated?

EDIT: Regarding my question/concern about relocation of items after insertion/deletion - I want to know what happens with the memory and not indexes. More information from wikipedia article:

Linked lists have several advantages over dynamic arrays. Insertion of an element at a specific point of a list is a constant-time operation, whereas insertion in a dynamic array at random locations will require moving half of the elements on average, and all the elements in the worst case. While one can "delete" an element from an array in constant time by somehow marking its slot as "vacant", this causes fragmentation that impedes the performance of iteration.

Will these numeric gaps be somehow allocated (and therefore take some memory) even when they do not have assigned values?

No. JavaScript arrays aren't really arrays at all (see below), and the unused indexes consume no memory.

When I delete myArray[456] from upper example, would items below this item be relocated?

If you're talking about array indexes, it depends on how you delete it: If you use the delete keyword, no. If you use the splice function or similar, yes. In terms of memory, no, other entries are not relocated (regardless), and any memory that was referenced by an entry that no longer exists (whether because of a delete or a splice or a pop or similar) becomes available to be reclaimed by the garbage collector. Linked lists have virtually no advantage in JavaScript over arrays or plain old objects, and you rarely see them. Adding to a JavaScript array (or object) is likely to be a near-constant-time operation (implementations will probably need to do hashing and possibly some traversal of B-tree structures or similar, but that's totally implementation-specific), as is deletion.

For what you're describing, as Zevon pointed out, you may not want an array at all. You really only need an array if you need a length property or one of the array functions that relies on it. Otherwise, you're better off with a plain old object:

var obj = {};
obj[123] = "foo";
obj[456] = "bar";
obj[789] = "baz";

That's perfectly valid JavaScript. The values you're using in brackets (123, etc.) are coerced to strings (whether you're dealing with an array or a plain object), and so the key is really "123", etc. (whether you're using an Array or an Object). You can even loop through them, with the for..in control structure (details here).

What do I mean by "...aren't really arrays at all"? Literally that. JavaScript objects are key->value maps, and JavaScript arrays are nothing more than objects that have keys and values and special handling for keys that are numeric strings, and a special length property. Although we conventionally write array "indexes" as numbers, like all property names they are strings — a[0] is converted to a["0"] (although implementations are free to optimize this as long as the behavior remains as per the spec). This is covered by Section 15.4 of the specification, which starts with this paragraph:

Array objects give special treatment to a certain class of property names. A property name P (in the form of a String value) is an array index if and only if ToString(ToUint32(P)) is equal to P and ToUint32(P) is not equal to 2^32−1. A property whose property name is an array index is also called an element. Every Array object has a length property whose value is always a nonnegative integer less than 2^32. The value of the length property is numerically greater than the name of every property whose name is an array index; whenever a property of an Array object is created or changed, other properties are adjusted as necessary to maintain this invariant. Specifically, whenever a property is added whose name is an array index, the length property is changed, if necessary, to be one more than the numeric value of that array index; and whenever the length property is changed, every property whose name is an array index whose value is not smaller than the new length is automatically deleted. This constraint applies only to own properties of an Array object and is unaffected by length or array index properties that may be inherited from its prototypes.

The "gaps" will not result in allocations, and no, there's no "shifting" of existing values from their indexes.

Will these numeric gaps be somehow allocated (and therefore take some memory) even when they do not have assigned values?

No, see the spec on Array's property setter.

When I delete myArray[456] from upper example, would items below this item be relocated?

No, if there were an item at 460 it will remain there after 456 is deleted. If you want the ones below to be properly shifted down, use the splice method like so:

myArray.splice(456, 1)