Como os ArrayList são armazenados na memória? [resolvido]

O jeito mais fácil é olhar no fonte, oras bolas! Veja o arquivo src.zip que existe no JDK, e abra o arquivo /java/util/ArrayList.java.

De qualquer maneira, já vou dar uma dica: um ArrayList é um encapsulamento de um array. Ele contém um Object[] dentro de si, que é um pouco maior que o tamanho declarado para ele, até para ter algum espaço para poder acrescentar alguns elementos sem ter de fazer um System.arraycopy a cada vez que você adiciona (.add) um novo elemento.

Não saquei, oras bolas.

Acho que a questão é mais profunda.

Não dá pra saber de verdade o que acontece fisicamente. A JVM somente manda o SO armazenar memória. Se o SO vai fazer isso num bloco contínuo ou não, ele que sabe, ele irá abstrair essa operação para a gente, assim como a JVM faz para os programas.

Para os programas Java, mandamos a JVM criar um array e que ele devolva a referência, do que pensamos que é um estrutura em memória contínua.

Huuum, agora eu entendi. Na verdade, a JVM administra isso da maneira que ela achar melhor, e esse achar melhor depende do que ela está executando no momento. Isso mesmo?

OK, vamos lá.

List<Integer> lista = new ArrayList<Integer>();

==> isto cria um objeto ArrayList, que contém um campo "Object[]" com 16 posições, todas preenchidas inicialmente com "null", e um campo "int" com o valor 0 (que indica o tamanho do arraylist em elementos, ou seja, o retorno do método "size()".

lista.add (Integer.valueOf (1));

==> isto insere o elemento Integer.valueOf (1) (que é um Integer, que é um Object, e que pode ser copiado para a posição [0] do array Object[] que indicamos antes). Isso também incrementa o tamanho para 1.

lista.add (Integer.valueOf (2));

==> isto insere o elemento Integer.valueOf (2) (que é um Integer, que é um Object, e que pode ser copiado para a posição [1] do array Object[] que indicamos antes). Isso também incrementa o tamanho para 2.

lista.add (Integer.valueOf (928374));

==> isto insere o elemento Integer.valueOf (928374) (que é um Integer, que é um Object, e que pode ser copiado para a posição [2] do array Object[] que indicamos antes). Isso também incrementa o tamanho para 3.

… continuando a inserir elementos até que chegue ao tamanho 16…

lista.add (Integer.valueOf (290902));

==> Como o array teria de ter pelo menos 17 posições agora, então temos de ampliar o array. O que o código de ArrayList faz? Ele cria um novo Object[] com um tamanho maior (só lendo o fonte de ArrayList para saber que conta ele faz; digamos que seja para o dobro do tamanho, ou seja, 32). Aí ele copia os elementos do array antigo para o array novo (System.arraycopy) e depois despreza o array antigo. Só aí então copia-se o elemento Integer.valueOf (290902) para a posição [16] do array Object[]. Isso incrementa o tamanho para 17.

Mas você tem de se acostumar a fazer aquilo que um cara que é esperto faz: em caso de dúvidas, olhe o fonte.

Huuum, agora eu entendi. Na verdade, a JVM administra isso da maneira que ela achar melhor, e esse achar melhor depende do que ela está executando no momento. Isso mesmo?

Aí tem que perguntar para quem fez a JVM, há dezenas delas.

Se eu fizesse a minha, eu implementaria estruturas de memória continua como alocando memória contínua. Se não tivesse mais espaço, atiraria um OutOfMemoryError.

Outras JVMs podem pedir pro SO tentar limpar a memória um pouquinho para dar mais espaços. Outras ainda poderiam alocar a memória dinamicamente, fazendo com que vários pedaços separados de 64 bytes parecessem para a aplicação como um pedaço grande contínuo de 1MB.

Aí cada uma escolhe qual é o melhor tamanho de pedaço, qual a maneira mais rápida, se querem tentar ao máximo antes de dar erro de falta de memória, se querem que a memória alocada seja de outro computador no cluster, etc etc.

O que importa é que a aplicação Java nem saiba o que está acontecendo. Por isso chamamos de máquina virtual Java. Para a aplicação, ela está rodando sempre na mesma máquina.

Thingol e Bruno, muito obrigado, minha dúvida foi respondida

Só acho que não precisava de um comentário tão venenoso no final:

Se seu objetivo for despejar um monte de conhecimento sempre com uma pitada de sarcasmo no final, ou no começo (“oras bolas!”), então nem precisa
me responder. Sei que as vezes a gente procura na API, no Google, na Wiki, se vira com o que dá, mas nem sempre a luz vem no final. Realmente agradeço
todas as vezes que me ajudou, aqui e em outros foruns, mas deprecio todas as vezes que você foi indelicado, seja aqui ou em outros foruns.

No caso específico da JVM da Sun, a organização “macro” da memória depende do algoritmo de garbage collection que a JVM está usando. Para alocar um array, ela precisa usar um espaço contíguo de memória para as referências, ou para os valores (se for um array de primitivos). Isso porque ela guarda o endereço do início do array e seu tamanho, e basta fazer uma simples conta (usualmente uma soma e uma multiplicação por 1, 2, 4, ou 8, que em muitos processadores é algo muito rápido porque se usam “left shifts”) para poder determinar o endereço de um determinado elemento no array. Se um array fosse guardado em pedaços, seria necessário fazer múltiplas comparações, só para poder determinar em que local está o elemento a ser acessado no array.
Mas cada referência pode apontar para onde for necessário - não precisa ser em locais contíguos, embora isso seja possível se a memória estiver relativamente vazia.