CODEWITHSUNDEEP
javaarrays
user1162715
user1162715

Reputation:

How does a program locate the index of an array?

I know array lookup has O(1) time, so it cannot be looping through. Does the program store the memory locations of the indices of the array, or how does it look the index instantaneously?

Upvotes: 6

Views: 106

Answers (4)

n0rmzzz
n0rmzzz

Reputation: 3848

Array elements are stored in a consecutive block, if they grow they need to be moved to a new place. The elements are then accessed using an offset from where the array begins.

In C you can access the element of index i in an array called a using two different methods:

  • int arrayElement = a[i];
  • int arrayElement = (int)(a + i * sizeof(int));

This is more or less how it is done in Java under the hood.

Upvotes: 0

Kumar Vivek Mitra
Kumar Vivek Mitra

Reputation: 33534

Try this,

1. Arrays are consecutive memory locations which are stored in Heap, as Arrays are objects in java.

2. Assume i have an Array of String as an instance variable

String[] arr = {1,2,3,4,5};

Now its like this

arr[0] = 1

arr[1] = 2

arr[2] = 3

arr[3] = 4

arr[4] = 5

{1,2,3,4,5} are stored over the heap, and Considering array "arr" as instance variable, will lives within the object on the heap.

Now arr will hold the address of the very first element of the Array that is 1. "arr" which is an object reference array variable, will be inside the object, and {1,2,3,4,5} outside somewhere on the heap.

Upvotes: 0

Sergey Kalinichenko
Sergey Kalinichenko

Reputation: 726599

Array elements are always spaced at equal distances in the memory, so finding an element given an index requires a multiplication by the size of the element and an addition of the array's base in memory. Both operations are often done within the space of a single instruction in hardware by employing an appropriate addressing mode.

Upvotes: 9

Keith Nicholas
Keith Nicholas

Reputation: 44298

underneath... its a memory address + (index postion * the size of the things in the array)

Upvotes: 3

Related Questions