Kolekcje w Javie w wielu przypadkach (np ArrayList) opierają się na tablicach. Kolekcje są zaimplementowane w Javie i możesz sobie ten kod Javowy przejrzeć i wyciągnąć wnioski. Tablice w Javie mają stały rozmiar, więc implementacje kolekcji muszą jakoś sprytnie zarządzać tymi tablicami pod spodem, by zarówno nie były zbyt pamięciożerne oraz by nie miały zbyt dużego narzutu obliczeniowego (w to wchodzi alokacja i kopiowanie pamięci).
- Jak to jest z tymi kolekcjami. Gdy tworzę kolekcję (np. listę) bez podania początkowego rozmiaru domyślnie rozmiar nadaje jej maszyna wirtualna?
W implementacji ArrayListy jest podany początkowy rozmiar tablicy pod spodem.
- Druga sprawa związana z rozmiarem. Gdy mam np. listę string'ów zarezerwowaną na 100 el. to po dodaniu przykładowego string'a jest on przechowywany w pamięci zarezerwowanej dla kolekcji, czy jest tam tylko wskaźnik do niego, a na sam string jest przechowywany gdzie indziej? Czy jest on cały umieszczany w pamięci przeznaczonej dla kolekcji? Wyczytałem, że stworzenie takiej kolekcji jest podobne do:
int ** tab;
tab = new int *[n];
w C++.
Typy w Javie to:
- prymitywy,
- referencje,
- tablice prymitywów,
- tablice referencji,
Tablica to też obiekt, a w kodzie Javowym w rzeczywistości operujemy referencją do tablicy (tak jak referencją do obiektu). W szczególności tablica tablic jest tablicą referencji.
Przechodząc do twojego pytania: każdy String to osobny obiekt, a tablica Stringów zawiera w rzeczywistości referencje do nich.
- Jakiś czas temu czytałem, że po przekroczeniu zarezerwowanego miejsca, JRE alokuje w pamięci 2 razy więcej miejsca i kopiuje elementy z kolekcji do nowo zaalokowanej pamięci, a tamtą zostawia systemowi zbierania nieużytków. Prawda?
Tak działa część implementacji kolekcji. Zajrzyj do źródeł, by zobaczyć które tak robią. Ta alokowana pamięć jest w takich przypadkach tablicą.
- Kolekcje są alokowane na stercie?
Tak. Tak samo jak wszystkie inne obiekty (oprócz specjalnych obiektów typu Class czy statycznych pól).
Dla przykładu, weźmy sobie ArrayList i źródła z tej strony: http://grepcode.com/file_/repository.grepcode.com/java/root/jdk/openjdk/6-b14/java/util/ArrayList.java/?v=source
Elementy trzymane są w tablicy:
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer.
*/
private transient Object[] elementData;
Aktualny rozmiar jest trzymany w zmiennej, przez co dodawanie czy usuwanie elementów nie wymusza alokowania tablicy od nowa za każdym razem:
/**
* The size of the ArrayList (the number of elements it contains).
*
* @serial
*/
private int size;
Domyślny początkowy rozmiar tablicy to 10:
/**
* Constructs an empty list with an initial capacity of ten.
*/
public ArrayList() {
this(10);
}
Operacje dodawania elementów upewniają się najpierw czy jest miejsce na nowe elementy i jeśli trzeba alokują nową, większą tablicę. Logika jest zawarta w tej funkcji:
/**
* Increases the capacity of this <tt>ArrayList</tt> instance, if
* necessary, to ensure that it can hold at least the number of elements
* specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
Operacje usuwania wyglądają jakby nie przejmowały się zmniejszaniem tablicy elementów, ale rozmiar tej tablicy można ręcznie zoptymalizować wywołując metodę:
/**
* Trims the capacity of this <tt>ArrayList</tt> instance to be the
* list's current size. An application can use this operation to minimize
* the storage of an <tt>ArrayList</tt> instance.
*/
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}