How Exactly Does Indexing Work in Arrays?

algorithmsarrayhashtablejava

I only know that index is faster but don't know why is it faster.

Suppose I have an array int[] a = {2,3,6,7}. Then I will try to find the element at a[3] and the speed of this will be O(1). Why? How it will know that 3 is placed after 2 boxes? So for more clarification of my question here is the structure of array I'm expecting.

index   values 
 [0] ->  [2]
 [1] ->  [3]
 [2] ->  [6]
 [3] ->  [7]

Why will a[3] go directly to 7?

HashTable

Same confusion I have for the HashTable:

 hash   values 
 [7nsh] ->  [2]
 [j2ns] ->  [3]
 [9sjm] ->  [6]
 [an5k] ->  [7]

If I search for the value from a hash function getValue(6), it will generate the same key 9sjm but how it knows that the key is placed on third number? Same how it could be O(1)?

Best Answer

Forget hashing, it is much simpler than that. Arrays will always be laid out in memory using consecutive storage locations. The compiler knows the array to start at memory cell x. When it needs to get to a[123], it adds 123 to x and uses that number to address the memory to get to the element.

It is actually 123 * elementSize but you get the point. It always takes one multiplication, one add operation and one fetch of an element from a know location.

Related Topic