How are arrays and hash maps constant time in their access?

Question

Specifically: given a hash (or an array index), how does the machine get to the data in constant time?

It seems to me that even passing by all the other memory locations (or whatever) would take an amount of time equal to the number of locations passed (so linear time). A coworker has tried valiantly to explain this to me but had to give up when we got down to circuits.

Example:

my_array = new array(:size => 20)
my_array[20] = "foo"
my_array[20] # "foo"

Access of "foo" in position 20 is constant because we know which bucket "foo" is in. How did we magically get to that bucket without passing all the others on the way? To get to house #20 on a block you would still have to pass by the other 19...

Answer 1

How did we magically get to that bucket without passing all the others on the way?

"We" don't "go" to the bucket at all. The way RAM physically works is more like broadcasting the bucket's number on a channel on which all buckets listen, and the one whose number was called will send you its contents.

Calculations happen in the CPU. In theory, the CPU is the same "distance" from all memory locations (in practice it's not, because of caching, which can have a huge impact on performance).

If you want the gritty details, read "What every programmer should know about memory".

Answer 2

Then to understand you have to look at how memory is organized and accessed. You may have to look at the way an address decoder works. The thing is, you do NOT have to pass by all the other addresses to get to the one you want in the memory. You can actually jump to the one you want. Otherwise our computers would be really really slow.

Answer 3

Unlike a turing machine, which would have to access memory sequentially, computers use random access memory, or RAM, which means if they know where the array starts and they know they want to access the 20th element of the array, they know what part of memory to look at.

It is less like driving down a street and more like picking the correct mail slot for your apartment in a shared mailbox.

Answer 4

2 things are important:

1. my_array has information about where in memory computer must jump to get this array.
2. index * sizeof type gets offset from beginning of array.

1 + 2 = O(1) where data can be found