deepak deepak - 4 months ago 26
Java Question

How is a two-dimensional array represented in memory in java?

I am trying to implement a data structure with Key, Value pairs and was looking at array implementations.

One way of achieving this is to declare seperate 1-D arrays for Key and Values.

private int[] keys = new int[N];
private int[] values = new int[N];


But can the same be achieved by declaring a 2-D array as follows and not compromise on data locality?

private int[][] keysAndValues = new int[2][N];


It seems important here that Java implements multidimensional arrays in row-major order? Are there any performance advantages in declaring the array this way, or does this make the code less readable?

Answer

A 2D array in Java is actually an array of object references, each of which points to a 1D array. The 2D array, and each of the 1D arrays are all separate heap objects, and could (in theory) be anywhere in the heap.

(For a discussion of why, see: Why doesn't Java have true multidimensional arrays?)


But can the same be achieved by declaring a 2-D array as follows and not compromise on data locality?

Yes it can.

There is minimal difference in data locality between the two versions, especially if we can assume that N is large compared with 2. (And if we can't, then data locality is most likely irrelevant; i.e. the performance difference will be too small to be significant.)

It seems important here that Java implements multidimensional arrays in row-major order?

Is that a question? If yes, then I guess so. It is certainly relevant ... though if Java implemented them column-major, then you would simply flip the rows and columns and get an equivalent solution

Are there any performance advantages in declaring the array this way, or does this make the code less readable?

The performance issues are likely to be insignificant. But if it really, really matters then the best advice is to profile and optimize the code for yourself ... on REAL input datasets.

As for readability, that is up to you to judge. I can't predict what your code is going to look like.


If you really want to control the memory locality, then the best way is to use a single 1D array, and map the indexes in a way that gives you the best locality overall. (That will depend on your application and how it references the data in the array.)