Why does ArrayList use Object[] (instead of E[]) internally? [duplicate]

Question

ArrayList uses Object array internally:

private transient Object[] elementData;

and in E get(int) method it's cast to E type.

my question is: why ArrayList doesn't use E[] to store objects?

I understand that after compiler run, the type-erasure will transform E[] into Object[], but still need to cast to E in every get() call?

If use it E[] this code below isn't necessary

return (E) elementData[index];

The choice of use Object[] is for performance?

As type-erasure transforms E[] into Object[], java makes a cast internally to return correct type in generic methods?

EDITED

Let me to explain better what is the point of my doubt:

If ArrayList use E[] instead Object[], in method get(int) the cast isn't necessary. This will increase performance (apparently).

But, there is no magic, I think that use E[] JVM will cast object anyway, because type-erasure will transformed in Object. Correct?

ps: sorry for my bad english.

Answer 1

Update: this answer got way more attention and upvotes than I think it deserved for basically copy-pasting JDK source code, so I'm going to try to turn it into something worthy.

---

Java generics are designed to look and feel like true, reified, multi-instantiated, C++- or C#-style generics. That means that for a type like ArrayList<E>, we expect ArrayList<String> to behave like every occurrence of E has been replaced with String. In other words, this:

private Object[] elementData = new Object[size];

public E get(int i) {
    return (E) elementData[i];
}

String str = list.get(0);

ought to become this:

private Object[] elementData = new Object[size];

public String get(int i) {
    return (String) elementData[i];
}

String str = list.get(0);

Now, as you probably know, that's not actually how they work. For backwards-compatibilty reasons that are now (mostly) long behind us, Java generics are implemented via type erasure, where E is actually replaced with Object everywhere, and casts to String are inserted into the calling code where necessary. That means the code actually becomes something like this:

private Object[] elementData = new Object[size];

public Object get(int i) {
    return elementData[i];
}

String str = (String) list.get(0);

The cast to (E) has disappeared, and reappeared at the call site. If the call site had ignored the result, the cast would have vanished completely! This is why it gave an "unchecked" warning.

---

Now imagine if elementData had type E[] instead, as you suggest. That is, the code looked like this:

private E[] elementData = (E[]) new Object[size];

public E get(int i) {
    return elementData[i];
}

String str = list.get(0);

We know it gets transformed into the same thing as above, due to erasure. But if we had reified generics like we wish we did, it would look like this:

private String[] elementData = (String[]) new Object[size];
// ClassCastException: Object[] is not a String[]

Essentially we've written some code that should crash at runtime, and the only reason it works at all is that Java's generics implementation pretends to be better than it is. We've lied to the compiler to convince it to accept brittle code.

And it is brittle! We happen to avoid runtime crashes because the array never escapes the class. But if it did, it would cause ClassCastExceptions in hard-to-predict places. What if Java 9 introduced reified generics? The first implementation would keep working, but this one would break.

That's why most reasonable Java coding conventions require unchecked casts to be type-correct. (E) elementData[i] is type-correct because ArrayList makes sure only Es can be stored in elementData. (E[]) new Object[size] is never type-correct unless E is Object.

---

There are other benefits too. In Java 8, the elementData field can take on special sentinel values:

/**
 * Shared empty array instance used for empty instances.
 */
private static final Object[] EMPTY_ELEMENTDATA = {};

/**
 * Shared empty array instance used for default sized empty instances. We
 * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
 * first element is added.
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

/**
 * The array buffer into which the elements of the ArrayList are stored.
 * The capacity of the ArrayList is the length of this array buffer. Any
 * empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
 * will be expanded to DEFAULT_CAPACITY when the first element is added.
 */
transient Object[] elementData; // non-private to simplify nested class access