An Array v's A Dictionary

[DSMan195276]

I'm imagining this would suggest a 2 dimensional array would have a serial lookup (ie if I want to find an entry it would go through the stored data one item at a time until it finds the search item) whereas the same Dictionary is more like a random access (ie it goes directly to the search item)

I probably confused you slightly here, arrays do have constant-time lookup. When you do `array(5)`, the location of entry `5` is calculated directly, so it's quite fast (a bit faster than a dictionary).

Insertions and removals are the big deal, if you have a `ReDim array(10)` and you need to add an 11th entry, you can do a `ReDim array(11)` but behind the scenes that will involve copying the entire contents of the array into a new memory location. If you then wanted to insert your new entry at entry 4 instead of at the end, you'll need to copy the existing entries 4 to 10 into spots 5 to 11 so that entry 4 is now unused. If you go the other way and want to remove entry 4, you have to copy entries 5 to 11 into spots 4 to 10 so that there isn't a hole at entry 5. There are ways to work around some of these issues, but overall there's a limit to how much you can do because of how arrays are implemented, they don't lend themselves to being cheaply resized.

A dictionary doesn't have those problems. You can do a theoretical `DictAdd 5, "bar"` and if entry 5 didn't already exist it can allocate space for it without needing to move/copy most of the data already in the dictionary. Same with a `DictRemove 5`, the removal doesn't involve copying the entire contents of the dictionary.

I might try creating a simple dictionary implementation later, looking at the internals might make the advantages/disadvantages a bit clearer. I do see @bplus's implementation but it appears to be based on a sorted list which means its performance is more similar to a regular array.