Arrays

An array is the one collection the language gives syntax to, and the one whose limitations people meet before they have the vocabulary for them. It is an object on the heap with a fixed length, it is covariant in a way generics deliberately are not, and it is still the right answer for a million numbers. This lesson is what an array is, what it costs, and the two behaviours — fixed length and covariance — that everything else follows from.

#Declaring one

int[] counts = new int[5];              // five zeroes
int[] primes = {2, 3, 5, 7, 11};        // literal, length inferred
String[] names = new String[3];         // three nulls
var grid = new int[3][4];               // see below — not a rectangle
 
int[] bad = new int[-1];                // compiles; NegativeArraySizeException at run time

int[] counts and int counts[] both compile; the first is the convention and the second reads as a C habit. The elements are initialised for you — zero, 0L, 0.0, the null character, false, or null — which is the difference between an array and a local variable, where the compiler refuses to let you read one you have not assigned.

#An array is an object

Every array is an object on the heap: it has a header, it is garbage collected, and grid is a reference like any other. What it has that no other object has is a length field — not a method, which is why it is arr.length and list.size() and str.length(), three spellings of one idea that nobody enjoys remembering.

new int[3][4] is not a rectangle. It is one array of three references, each pointing at a separate int[4] that was allocated on its own. Nothing requires the rows to match, which is why this is legal and ordinary rather than exotic:

int[][] ragged = new int[3][];      // three nulls
ragged[0] = new int[]{1, 2, 3};
ragged[1] = new int[]{4, 5};

The consequence is a performance one: iterating a 2-D array row by row follows one reference per row and reads contiguous memory inside it; iterating column by column jumps between separate objects and defeats the cache. For numerical work a flat int[rows * cols] with manual indexing is measurably faster, and that is why libraries do it.

#Length is fixed

length is a field set at allocation. There is no add. "Growing" an array means allocating a new one and copying:

int[] bigger = Arrays.copyOf(counts, counts.length * 2);

Which is exactly what ArrayList does internally — it holds an Object[], and add past capacity allocates a 1.5x array and copies. The list is not a different data structure; it is this operation, hidden, with the copy amortised so that appending is O(1) on average.

#The Arrays utilities

Everything useful about arrays lives in java.util.Arrays, because an array has no methods of its own.

Two of those rows are traps worth stating outright.

int[] a = {1, 2, 3};
int[] b = {1, 2, 3};
System.out.println(a.equals(b));
System.out.println(java.util.Arrays.equals(a, b));

An array inherits equals from Object, so it compares identity. It inherits hashCode the same way, which is why an array is a terrible HashMap key and why List<Integer> is what you want when the contents should decide.

Arrays.equals has the same trap one level down. On nested arrays, "element-wise" means == on the rows:

Arrays.equals(p, q)      -> false
Arrays.deepEquals(p, q)  -> true
Arrays.toString(p)       -> [[I@2a139a55, [I@15db9742]
Arrays.deepToString(p)   -> [[1, 2], [3]]

The toString / deepToString pair is the one everybody learns. The equals / deepEquals pair is the same lesson and the one that costs real bugs.

And "undefined" does not mean "fails". binarySearch on an unsorted array returns something, and often the right thing:

[5, 1, 4, 2, 3]   search 4 -> 2    (really at 2)   right, by luck
[3, 1, 2]         search 1 -> 1    (really at 1)   right, by luck
[9, 8, 7, 6, 5]   search 7 -> 2    (really at 2)   right, by luck
[1, 3, 2, 4]      search 2 -> -2   (really at 2)   WRONG
[2, 1]            search 1 -> -1   (really at 1)   WRONG

Three of five are correct. That is the danger: undefined behaviour that usually works passes the test you wrote and fails on the input you did not. It is the same shape as the Integer cache — never rely on it in either direction.

clone() is the idiomatic array copy and it is a real copy — but only one level deep. deep.clone() on an int[][] gives you a new outer array pointing at the same rows, so writing through the copy writes through the original.

And Arrays.asList returns a view backed by the original array: set writes through to it, add throws UnsupportedOperationException, and on an int[] it produces a List<int[]> of one element rather than the List<Integer> you expected — because autoboxing does not apply to the array itself.

#Under the hood: what an array costs

On a 64-bit JVM with compressed references:

So new int[10] is 16 + 40 = 56 bytes, and new Integer[10] is 16 + 40 for the references plus ten Integer objects at 16 bytes each — 216 bytes to hold the same ten numbers, and eleven objects for the collector to trace instead of one.

That ratio is the entire argument for primitive arrays in numeric code, and it is why IntStream exists alongside Stream<Integer>. A million int is 4 MB in one object; a million Integer is 20 MB in a million objects.

Bounds are checked on every access — ArrayIndexOutOfBoundsException is a guarantee, not a debug feature. The JIT removes the check where it can prove the index is in range, which is why a plain for (int i = 0; i < a.length; i++) is often faster than a cleverer loop: the shape is one the optimiser recognises.

#There is no two-dimensional array

new int[1000][1000] looks like a grid. It is not. Java has only one-dimensional arrays, so this is one outer array of 1,000 references, and 1,000 separate int[1000] objects — 1,001 objects, not one.

new int[1000][1000]   ->  3.83 MB, 1,001 objects
a flat int[1000000]   ->  3.81 MB, 1 object

The memory difference is almost nothing, and saying otherwise would be overclaiming. The cost is locality. The rows are allocated separately and are not adjacent in memory, so walking a column chases a thousand pointers into unrelated cache lines while walking a row reads straight through one. The same loop, transposed, can differ by an order of magnitude for that reason alone — and it is the reason numerical code flattens to a single int[rows * cols] and indexes by hand.

The figure at the top of this lesson is exactly this: three rows of different lengths, drawn as the separate objects they are. It is worth going back to now that you know why they have to be separate.

It also makes "an array is an object" concrete:

int[][] two = new int[3][4];
two.getClass().getName();     // "[[I"   — an array of int arrays
two[0].getClass().getName();  // "[I"    — an int array
two[0] == two[1];             // false   — genuinely separate objects

Because the rows are separate objects, they need not be the same length. new int[3][] allocates the outer array only and leaves every row null for you to fill — a jagged array, which is the general case and the reason the rectangular one costs 1,001 objects.

#Covariance, and the hole it leaves

This compiles:

Object[] objects = new String[2];      // legal: String[] IS-A Object[]
try {
    objects[0] = 42;                   // compiles fine
} catch (ArrayStoreException e) {
    System.out.println("Caught: " + e.getMessage());
}

Note which class the message names. ArrayStoreException reports what you tried to store, not what the array holds — the array's component type is the thing it was checked against, and the value is the thing that failed. Reading it the other way round is the usual first guess, and it sends people looking at the wrong end.

Arrays are covariant: String[] is a subtype of Object[]. That was a deliberate choice in Java 1.0, before generics existed, so that Arrays.sort(Object[]) could sort anything. The price is that the compiler cannot catch the assignment above, so every array write carries a run-time type check — the store above throws ArrayStoreException.

Generics went the other way. List<String> is not a List<Object>, which is why the same mistake does not compile:

List<Object> list = new ArrayList<String>();   // compile error

That is the trade: arrays check at run time and cost a check per write; generics check at compile time and cost nothing at run time, because erasure means there is nothing left to check. The two systems disagree, and that disagreement is why you cannot create a generic array — new T[10] is a compile error, and (T[]) new Object[10] is the unchecked cast every collection class contains.

#Walkthrough: the cache that got slower after the fix

A service kept a double[][] matrix of 2,000 by 2,000 and summed it column by column. A profiler showed the loop dominating. Somebody "fixed" it by switching to Double[][] so the values could be null for missing data.

Throughput halved again. Column-major iteration was already jumping between 2,000 separate row objects; the change added a Double object per cell — four million of them, 64 MB of boxes over 32 MB of data — and every read now dereferenced twice and could not use a SIMD path.

The fix that worked was the boring one: a flat double[4_000_000] with i * cols + j, and a separate long[] bitset for presence. Same data, one object, row-major access, and the profiler line disappeared.

#Try it yourself

int[][] a = new int[3][];
System.out.println(a.length);
System.out.println(a[0] == null);

List<Integer> nums = Arrays.asList(1, 2, 3);
nums.set(0, 9);      // works
nums.add(4);         // throws

List<String>[] a = new List<String>[10];     // 1
List<String>[] b = new List[10];             // 2
String[] c = new Object[10];                 // 3

#Misconceptions

• "length is a method." It is a field on the array object. length() is String, size() is Collection.
• "A 2-D array is a grid in memory." It is an array of references to separate arrays, each allocated independently and possibly a different length.
• "Arrays are faster than ArrayList." For primitives, yes, and by a lot. For objects an ArrayList holds the same Object[] and adds one indirection; the difference is usually noise against the boxing you avoided or did not.
• "Arrays.asList gives me a list." It gives a fixed-size view over the array, and on an int[] it gives a one-element List<int[]>.
• "Bounds checks cost me." The JIT removes them when it can prove the range, which the canonical counted loop lets it do.

#Going deeper

• The Java Language Specification section 10, Arrays — particularly 10.5 on the store check, which is the covariance rule written down.
• java.util.Arrays in the JDK source; ArrayList.grow for what "growing an array" really is.
• JEP 401, Value Classes and Objects — the long-term answer to Integer[] costing what it costs.