4.2
How Arrays Work
Constant-time indexed access, opaque references, bounds checks, and the implementation details Java deliberately hides.
Previously on
Section 4.1 established the observable rules. An array has a fixed length, its indexes run from 0 to length - 1, and assigning an array variable copies a reference.
This section separates those Java guarantees from diagrams that explain a common JVM implementation.
The problem
This program can read the first and last elements without scanning the values between them:
public class AccessDemo {
public static void main(String[] args) {
int[] values = {10, 20, 30, 40, 50};
System.out.println(values[0]);
System.out.println(values[4]);
}
}Output:
10
50How can indexed access be independent of the array length? What does an array variable contain? Which parts of the usual memory diagram are guarantees, and which parts are implementation choices?
The idea
Java guarantees random access for arrays. Accessing values[i] does not walk through earlier elements. The work is constant with respect to values.length.
A useful low-level model is:
element location = array data start + index * storage per elementThis model explains why zero is a natural first index. Element 0 has an offset of zero units from the data start. It also explains why fixed-width primitive elements are friendly to indexed access.
| Java guarantees | A JVM may choose | |
|---|---|---|
| Indexing | a[i] selects one element in constant time. | The machine instructions used to locate it. |
| Length | a.length is fixed after creation. | Where and how the length is stored. |
| Safety | Invalid indexes throw ArrayIndexOutOfBoundsException. | Which checks the JIT can prove redundant and remove. |
| References | A reference identifies an array object or is null. | Reference width, compression and physical representation. |
| Storage | Elements behave as one indexed sequence. | Headers, alignment, allocation region and relocation strategy. |
Under the hood
Going deeperReferences are opaque values
import java.util.Arrays;
public class ReferenceDemo {
public static void main(String[] args) {
int[] a = {1, 2, 3};
int[] b = a;
int[] c = Arrays.copyOf(a, a.length);
b[0] = 99;
System.out.println(a[0]);
System.out.println(a == b);
System.out.println(a == c);
}
}Output:
99
true
falsea and b hold equal reference values, so they designate one array. c designates a separate array with copied primitive elements.
The language permits a small set of reference operations. You can assign a reference, pass it, return it, compare it with ==, follow it to reach the object, or store null. You cannot convert it into a usable address or add an offset to it.
Stack
main locals
Heap
int[3]@1a2b
int[3]@283c
The stack and heap diagram is a teaching model
A normal HotSpot run manages arrays as garbage-collected objects. Method calls also have frames that hold execution state. It is useful to draw local variables in a stack frame and arrays in a heap region.
The Java language does not require every local value to occupy a stack slot. A JIT compiler can keep a value in a register, inline a method, or remove an allocation when the change cannot be observed. A garbage collector can move an array and update the references that reach it.
The stable fact is not an address. It is identity: references that designated the same array before a collection still designate the same array afterward.
Bounds are checked
For an array of length n, a valid index satisfies this invariant:
0 <= index && index < npublic class BoundsDemo {
public static void main(String[] args) {
int[] values = new int[3];
System.out.println(values[2]);
System.out.println(values[3]);
}
}The first line prints 0. The second throws ArrayIndexOutOfBoundsException because index 3 is outside the half-open range [0, 3).
The JVM must preserve that behaviour. A JIT may remove repeated checks only when it can prove the result would be unchanged.
Why fixed length matters
An array object never changes its length. Growth means creating another array and copying elements.
import java.util.Arrays;
public class GrowthDemo {
public static void main(String[] args) {
int[] oldValues = {2, 4, 6};
int[] grown = Arrays.copyOf(oldValues, 6);
grown[3] = 8;
System.out.println(Arrays.toString(oldValues));
System.out.println(Arrays.toString(grown));
}
}Output:
[2, 4, 6]
[2, 4, 6, 8, 0, 0]ArrayList uses the same broad strategy. It keeps an internal array. When capacity is exhausted, it allocates a larger backing array and copies the existing references. The exact growth factor is an implementation detail, not an API promise.
Locality is common, not an address contract
Mainstream JVMs usually lay primitive array elements in a compact region. Sequential traversal can then benefit from processor caches and hardware prefetching.
That observation supports a performance hypothesis. It does not prove a fixed address, and it does not make every array loop faster than every alternative. Element type, access pattern, JIT compilation, cache state and workload size all matter. Measure the real workload with a suitable benchmark before making a performance claim.
Arrays of arrays can be jagged
int[][] means an array whose elements are references to int[] arrays. Rows can have different lengths, and a row can be null.
public class JaggedDemo {
public static void main(String[] args) {
int[][] triangle = {
{1},
{2, 3},
{4, 5, 6}
};
for (int row = 0; row < triangle.length; row++) {
for (int col = 0; col < triangle[row].length; col++) {
System.out.print(triangle[row][col] + " ");
}
System.out.println();
}
}
}Output:
1
2 3
4 5 6Each inner loop uses triangle[row].length. A single column count is not valid for every jagged row.
What it costs
Arrays exchange flexibility for a compact indexed abstraction. Their length is fixed. Inserting into a logical middle requires moving elements. A separate copy is proportional to the number of elements copied.
Bounds checks provide a defined failure instead of an out-of-range memory access. The JIT can remove some checks, but Java code must not rely on that optimisation.
Reference opacity removes pointer arithmetic and prevents Java code from depending on addresses that a garbage collector may change. It also means a source-level diagram cannot settle a low-level performance question. Use a profiler or benchmark when the answer depends on a particular JVM and machine.
Check yourself
Answer from memory before opening the explanation. Then compare your rule with the answer and revisit the example if they differ.
What does Java guarantee about the time needed for `a[i]`, and what does it not guarantee about the array's physical address?
Show the answer
An indexed array access takes constant time with respect to the array length. Reaching element 5000 does not require visiting elements 0 through 4999.
Java does not expose a raw address, an element size, or a physical layout contract. A JVM may use compressed references, object headers, alignment and garbage collection strategies that differ from another JVM. A moving collector may relocate the array while preserving every Java reference to it.
Why is `int[] b = a;` not an array copy?
Show the answer
The value in an array variable is a reference. Assignment copies that reference. Both variables therefore designate the same array object, and a write through either name is visible through the other.
Use
a.clone(),Arrays.copyOf, or an explicit copy when you need a second array.Does `new int[8]` prove that the reference is on a stack and the array is at one fixed heap address?
Show the answer
No. The Java language specifies the values and behaviour, not those placements. A typical JVM manages array objects in garbage-collected heap storage, but the JIT may keep a local reference in a register or remove an allocation when that is unobservable.
Java references are opaque. Code can follow them, compare them with
==, assign them and set them tonull. It cannot read or calculate a raw address.
Exercises
Write each solution in VS Code, predict its result, and then run the checks. Reading an example does not replace implementing it.
3 exercises85 pointsabout 100 minutes
Model an Array Offset
ex-4-2-aWork with a simplified flat-layout model. The exercise calls its result an address because the method contract is already published, but the number is not a Java reference or an address Java code can obtain.
The model assigns convenient byte sizes to types. Those values are assumptions for the calculation. Java does not specify object headers, alignment, compressed references, or the storage size of boolean[] elements.
Use the model to compare element 9999 with element 0. Both need a fixed number of model operations, which illustrates why array access is constant-time with respect to array length. Do not claim this counts the exact machine instructions used by every JVM.
Finish by rewriting the model for one-based indexes. Explain how zero-based indexes match offsets directly, while recognising that language design also includes history and convention.
What to write
These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.
class Address {
static long addressOf(long start, int elementSize, int index)
static int sizeOf(String type)
static long lastAddress(long start, int elementSize, int length)
static long totalBytes(int elementSize, int length)
static boolean costDependsOnIndex()
}Treat start and elementSize as numbers supplied by a model. Java does not expose either value. The arithmetic must be done as longs so a large model offset does not overflow.
What your program must do
- Work out an offset-model location from a supplied start and element size
- Use the exercise's invented sizes for three element types
- State why the result models constant-time access but is not a Java raw address
- State that Java does not specify the byte size of a boolean array element
- Show why the model arithmetic has to be done as longs
public class Address {
// CONCEPTUAL MODEL ONLY: start + index * elementSize. Java does not expose
// an array's raw start address or promise this physical layout.
static long addressOf(long start, int elementSize, int index) { return 0; } // TODO
// Sizes chosen by this exercise's flat-layout model: byte and boolean 1,
// short and char 2, int and float 4, long and double 8.
// In particular, Java does NOT specify a boolean[] element size in bytes.
static int sizeOf(String type) { return -1; } // TODO
static long lastAddress(long start, int elementSize, int length) { return 0; } // TODO
static long totalBytes(int elementSize, int length) { return 0; } // TODO
// In this constant-time offset MODEL, does a later index need more steps?
static boolean costDependsOnIndex() { return true; } // TODO
public static void main(String[] args) {
// TODO: print model locations for three imaginary flat arrays
}
}
Hint 1
start + index * elementSize. Java guarantees indexed access without a walk, but it does not expose these numbers or require this exact physical formula.Hint 2
index * elementSize as ints can overflow once the model offset exceeds the int range.Hint 3almost the answer
Test a Locality Hypothesis
ex-4-2-bThe two methods do not perform equal work. sequentialSum visits every element. stridedSum(data, 16) visits indexes 0, 16, 32 and so on, so it performs about one sixteenth as many additions and usually produces a different sum.
Warm both methods, alternate their measurement order, and record several samples. Report the number of elements visited beside every time. Also calculate time per visited element.
One explanation to test is spatial locality. Processors commonly move a line of neighbouring bytes through the cache hierarchy. Mainstream JVMs commonly store primitive array elements compactly. A sequential pass can use more of each transferred line than a large-stride pass.
That explanation is an implementation and hardware hypothesis. Java does not guarantee a 64-byte line, expose the physical address, or promise one layout for every JVM. One timing cannot prove contiguity, and this exercise is not a substitute for JMH.
Run without warm-up once and record the difference. Compilation may explain part of it, but cache state and system noise can also contribute. State what you measured and which explanations remain assumptions.
What to write
These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.
class Cache {
static long sequentialSum(int[] data)
static long stridedSum(int[] data, int stride)
static long time(Runnable work)
static int elementsPerCacheLine(int elementSize)
}stridedSum visits every stride-th element, so stride 16 performs about one sixteenth as many additions as a sequential pass. elementsPerCacheLine uses an explicit 64-byte model assumption; Java does not expose or guarantee a cache-line size.
What your program must do
- Time a sequential walk and strided walks
- Warm both code paths before recording and take repeated samples
- Report that stride 16 visits about one sixteenth as many elements
- Compare time per visited element as well as total time
- Treat cache lines and compact primitive storage as hypotheses, not proof from one timing
public class Cache {
static long sequentialSum(int[] data) { return 0; } // TODO: every element
static long stridedSum(int[] data, int stride) { return 0; } // TODO: every stride-th
static long time(Runnable work) { return 0; } // TODO: milliseconds
// MODEL ASSUMPTION: a 64-byte cache line. Java does not guarantee this.
static int elementsPerCacheLine(int elementSize) { return 0; } // TODO
public static void main(String[] args) {
int size = 8_000_000;
int[] data = new int[size];
for (int i = 0; i < size; i++) data[i] = i;
// Warm both methods before measuring.
// TODO: run each measurement repeatedly and report all samples
// TODO: time sequential and strides 16 and 64
// TODO: report both elapsed time and visited element count
}
}
Hint 1
Hint 2
Hint 3almost the answer
Build a Growable Array Model
ex-4-2-cBuild a small array-backed list so that the main ArrayList ideas are familiar in Phase X.
An array cannot grow. Wrap one, track how many slots are used, and replace it with a larger copied array when capacity is exhausted. ArrayList uses this broad strategy, but its exact capacity and growth policy are implementation details.
Make get reject bad indexes properly. Notice that you have to check against size and not capacity, because the spare slots at the end hold zeros that were never added by anyone.
Compare this exercise’s doubling rule against growing by one slot each time. Count growth operations and copied elements. The result explains amortised growth, but it does not establish a universal performance result for every workload or JVM.
What to write
These exact signatures. The checks call them by name, so a different name or a different parameter type will not build.
class GrowableIntList {
public void add(int value)
public int get(int index)
public int size()
public int capacity()
public int growCount()
}This exercise requires starting at capacity 4 and doubling when full. That is the model's contract, not java.util.ArrayList's specified policy. get must reject any index outside 0 to size-1, including slots that exist in the array but hold nothing you added, and the message must name both the index and the size.
What your program must do
- Grow the array when it is full and keep the values
- Keep size and capacity as separate ideas
- Reject an index past size, even when the slot exists
- Compare doubling against adding one slot at a time, by grow count
import java.util.Arrays;
public class GrowableIntList {
private int[] items = new int[4]; // the real array underneath
private int size = 0; // how many slots are actually used
private int growCount = 0; // for the report at the end
public void add(int value) {
// TODO: if items is full, grow it, then store value and increase size
}
public int get(int index) {
// TODO: reject out of range indexes with a message naming the index AND the size
return 0;
}
public int size() { return size; }
public int capacity() { return items.length; }
public int growCount() { return growCount; }
public static void main(String[] args) {
GrowableIntList list = new GrowableIntList();
for (int i = 0; i < 100; i++) list.add(i);
// TODO: print size, capacity and how many times it grew
// TODO: try growing by ONE each time instead and compare the grow count
}
}
Hint 1
Arrays.copyOf(items, items.length * 2) makes the bigger array and copies everything across in one call.Hint 2
size is what you put in. capacity is what the array can hold. Asking for index 1 when size is 1 must fail, even though slot 1 exists and holds a zero.Hint 3almost the answer
After the credits
The distinction between a Java guarantee and a JVM implementation returns in Section 6.3. There you will trace object references without pretending that an arrow is a permanent machine address.
In Phase X, ArrayList adds resizable capacity around an array, while LinkedList follows links between nodes. Their performance depends on operations and workloads, so the memory model gives you hypotheses to measure rather than slogans to repeat.
Phase XIII covers runtime memory areas and garbage collection in detail, including why object movement does not invalidate Java references.
Threads you opened in this section
- The heapHow much space does an object really take. The answer surprises people.6.3 - Objects in Memory: Size, Copying, Passing
- The heapYoung space, old space, and how the collector cleans them.Phase XIII. Memory and the Garbage Collector
- Random accessThis one property is the whole ArrayList vs LinkedList argument.Phase X. The Collections Framework
- Random accessA Set gives up random access. That is the price of its speed.Phase X. The Collections Framework
The heap will return in 6.1 - Classes, Objects, and `new`