2

There are several questions that are similar to this one here on S.O., but they don't quite answer what the code implementation is. I've looked at

Why isn't there a java.lang.Array class? If a java array is an Object, shouldn't it extend Object?

and

How are arrays implemented in java?

and they don't answer what the concrete implementations are.

I've downloaded the java source from OpenJDK, and I really can't find what I'm looking for. (Perhaps that part of the code is proprietary?)

  1. How are append/inserts done?
  2. How is data retrieved? For example, if I invoke my_arr[500] what's the algorithm implemented to get the value at index 500?
  3. How are deletes done?

Thanks in advance!

Community
  • 1
  • 1
maximus
  • 2,417
  • 5
  • 40
  • 56

3 Answers3

6

There are no appends, inserts or deletes on arrays.

The address of my_arr[500] in a reasonable implementation would be the base address of the object, plus a small offset for the header, plus 500 times the size of the array element. Obviously you need to do range checking - the offsets needs to be non-negative and less than the length of the array (stored in the header).

Tom Hawtin - tackline
  • 145,806
  • 30
  • 211
  • 305
  • Could you please give an example ? Thank you. – cat916 Apr 23 '13 at 23:07
  • @minhcat_vo what kind of example? An example of the header, or an example of the accessor code? – John Dvorak Apr 23 '13 at 23:09
  • 1
    @minhcat_vo The header could be `{Obj **class, int length, Obj **elems[]}` (if references are implemented as pointers to a pointer). – John Dvorak Apr 23 '13 at 23:14
  • 1
    @minhcat_vo the array reader could be `if(index < 0 || index > length) throwNew("ArrayIndexOutOfBoundsException"); return elems[index]}` – John Dvorak Apr 23 '13 at 23:17
  • @JanDvorak Thanks for an example of header :). – cat916 Apr 23 '13 at 23:26
  • 1
    @minhcat_vo actually, my header is missing the garbage collection information. Let's hope it's inherited ;-) – John Dvorak Apr 23 '13 at 23:42
  • The header has got to do lots of stuff: Length of the array, obviously. A pointer to type information. Data related to the GC algorithm, such as a mark bit. The identity hash code. Also every object in Java is a lock (every Java object is actually mutable) which would typically be performance optimised (biased locking and the suchlike). / There are many tricks to bring that all down to something relatively compact, but it's not ideal. – Tom Hawtin - tackline Apr 24 '13 at 09:31
3

I will say its same as that of C or C++

when we do int a[10]; or Object obj[10]; compiler allocates the block of memory equal to 10*sizeOf(int) or 10*sizeOf(Object) the address of first location in memory block is stored in a. so basically a becomes pointer. Note Java internally uses Pointers.

then whenever we try to access a[5] address of location is calculated as pointer arithematic.

a+5*(sizeOf(int)) or obj+5*(sizeOf(Object)) and then read sizeOf(int) or sizeOf(Object) bytes as value

rahul maindargi
  • 5,359
  • 2
  • 16
  • 23
  • 1
    Thanks Rahul, this is a great answer. (Thanks for providing some code!) However, Tom also pointed out that arrays don't have insert/append/delete, so I will accept his answer, but upvoted yours as well. – maximus Apr 25 '13 at 05:55
0

  1. my_arr[1] = "whatevs"; this will set the first element in the array to whatevs.

  2. System.out.print(my_arr[500]);// my_arr[#] is the location in memory for element 500 in the array, call on it to get whatever information is stored there. (actually the actual 500 element would be out of bounds, the element you would be looking for is 499. as arrays always start at 0 and go to their set amount -1)

3.To delete information you would do what is done in one but set it to "null" or copy the array and simply leave out the parts you don't want to include.

You would use a method to do all of these things within a program to render another affect. What really needs to be understood that each element in an array can be an object or a primitive,i.e. a number value, like 10.

If all of this seems to basic to you then you need to be more precise with your question or simply explain what you are trying to do with arrays.

Dakuwan Locke
  • 67
  • 1
  • 5
  • It's not about how basic/advance. It's an algorithms question about how an array is implemented. A simple linked list retrieves an element in O(n) time, arrays do it in O(1), it's because they're fundamentally different. Thank you for the reply, and yes I know that arrays are 0-based. – maximus Apr 23 '13 at 23:20
  • 1
    `What really needs to be understood that each element in an array can be an object or a primitive` this is just wrong, in java only object references are stored in arrays, never objects itself. In C++ arrays of objects could generated, in java not!! if you have an array of objects, it would in reality be an array of object-references. each element is then pointing to a location in the heap where this object is located. – El Hocko Apr 23 '13 at 23:24