How exactly Java indexing works in arrays?

438    Asked by MurakamiTanaka in Java , Asked on Oct 11, 2022

 I only know that index is faster but don't know why it is 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 will it know that 3 is placed after 2 boxes? So for more clarification of my question here is the structure of the 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 does it know that the key is placed on the third number? Same as how it could be O(1)?


Forget hashing, Java indexing 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 known location.



Your Answer

Interviews

Parent Categories