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.