How do arrays generally work at a low level?

Question

How do they map an index directly to a value without having to iterate though the indices?

If it's quite complex where can I read more?

Answer 1

An array is just a contiguous chunk of memory, starting at some known address. So if the start address is p, and you want to access the i-th element, then you just need to calculate:

p + i * size

where size is the size (in bytes) of each element.

Crudely speaking, accessing an arbitrary memory address takes constant time.

Answer 2

Essentially, computer memory can be described as a series of addressed slots. To make an array, you set aside a continuous block of those. So, if you need fifty slots in your array, you set aside 50 slots from memory. In this example, let's say you set aside the slots from 1019 through 1068 for an array called A. Slot 0 in A is slot 1019 in memory. Slot 1 in A is slot 1020 in memory. Slot 2 in A is slot 1021 in memory, and so forth. So, in general, to get the nth slot in an array we would just do 1019+n. So all we need to do is to remember what the starting slot is and add to it appropriately.

If we want to make sure that we don't write to memory beyond the end of our array, we may also want to store the length of A and check our n against it. It's also the case that not all values we wish to keep track of are the same size, so we may have an array where each item in the array takes up more than one slot. In that case, if s is the size of each item, then we need to set aside s times the number of items in the array and when we fetch the nth item, we need to add s time n to the start rather than just n. But in practice, this is pretty easy to handle. The only restriction is that each item in the array be the same size.

Answer 3

Wikipedia explains this very well:

http://en.wikipedia.org/wiki/Array_data_structure

Basically, a memory base is chosen. Then the index is added to the base. Like so:

if base = 2000 and the size of each element is 5 bytes, then:
array[5] is at 2000 + 5*5.
array[i] is at 2000 + 5*i.

Two-dimensional arrays multiply this effect, like so:

base = 2000, size-of-each = 5 bytes
array[i][j] is at 2000 + 5*i*j

And if every index is of a different size, more calculation is necessary:

for each index
  slot-in-memory += size-of-element-at-index

So, in this case, it is almost impossible to map directly without iteration.