ArrayList: jak zwiększa się rozmiar?

Będzie zależeć od implementacji, ale z kodu źródłowego Sun Java 6:

int newCapacity = (oldCapacity * 3)/2 + 1;

To metoda ensureCapacity. Inne implementacje JDK mogą się różnić.

Sun ' s JDK6:

Wierzę, że rośnie do 15 elementów. Nie kodowanie go, ale patrząc na wzrost() kod w jdk.

Int newCapacity then = 10 + (10 >> 1) = 15.

/**
 * Increases the capacity to ensure that it can hold at least the
 * number of elements specified by the minimum capacity argument.
 *
 * @param minCapacity the desired minimum capacity
 */
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

Z Javadoc, jest napisane, że to jest z Java 2 i dalej, więc jest to Bezpieczny zakład w słońcu JDK.

EDIT : dla tych, którzy nie zrozumieli jaki jest związek między mnożnikiem 1.5 i int newCapacity = oldCapacity + (oldCapacity >> 1);

>> jest właściwym operatorem zmiany, który redukuje liczbę do jej poł. Tak więc,
int newCapacity = oldCapacity + (oldCapacity >> 1);
=> int newCapacity = oldCapacity + 0.5*oldCapacity;
=> int newCapacity = 1.5*oldCapacity ;

Kiedy próbujemy dodać obiekt do arraylist,

Java sprawdza , czy w istniejącej tablicy jest wystarczająco dużo pojemności, aby pomieścić nowy obiekt. Jeśli nie, tworzy się nowa tablica o większym rozmiarze, stara tablica jest kopiowana do nowej tablicy przy użyciu tablic .copyOf i nowa tablica jest przypisana do istniejącej tablicy.

Spójrz na poniższy kod (zaczerpnięty z kodu Java ArrayList na GrepCode.com).

Edit:

Public ArrayList () tworzy pustą listę o początkowej pojemności 10.

Public ArrayList(int initialCapacity) możemy określić początkową pojemność.

Public ArrayList (Collection c) tworzy listę zawierającą elementy podanej kolekcji, w kolejności, w jakiej są zwracane przez iterator kolekcji.

Teraz kiedy używamy ArrayList () constructore otrzymujemy ArrayList o Size = 10 Przy dodawaniu W metodzie ensureCapacity() powstaje 11.element na liście Nowa Arraylist.

Używając następującego wzoru:

  int newCapacity= (oldCapacity * 3)/2 +1;

Gdy ArrayList jest zadeklarowana i zainicjalizowana przy użyciu domyślnej konstruktor, zostanie utworzone Miejsce Pamięci na 10 elementów. teraz, kiedy dodam 11 element, to co się dzieje to

ArrayList utwórz nowy obiekt o następującym rozmiarze

I. E OldCapacity*3/2+1 = 10*3/2+1 =16

Zazwyczaj pamięć dla kontenerów typu ArrayList jest zwiększana przez podwojenie jej. Tak więc, jeśli początkowo miałeś miejsce na 10 elementów i dodałeś 10, jedenasty element zostanie dodany do nowej (wewnętrznej) Tablicy 20 elementów. Powodem tego jest to, że Przyrostowy koszt dodawania elementów jest zmniejszany Z O(N^2), jeśli tablica została zwiększona w przyrostach o stałym rozmiarze do ładnego O (n), gdy podwojenie rozmiaru za każdym razem, gdy wewnętrzna tablica jest pełna.

Context java 8

Tutaj udzielam odpowiedzi w kontekście implementacji Oracle java 8, ponieważ po przeczytaniu wszystkich odpowiedzi okazało się, że odpowiedź w kontekście java 6 została udzielona przez gmgmiller, a inna odpowiedź została udzielona w kontekście java 7. Ale jak java 8 implementuje zwiększenie rozmiaru nie zostało podane.

W Javie 8 zachowanie zwiększania rozmiaru jest takie samo jak w Javie 6, zobacz metodę grow ArrayList:

   private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Kod klucza jest to linia:

int newCapacity = oldCapacity + (oldCapacity >> 1);

Więc wyraźnie, czynnik wzrostu jest również 1,5, taki sam jak java 6.

Gdy ArrayList jest zadeklarowana i zainicjalizowana przy użyciu domyślnego konstruktora, tworzona jest przestrzeń pamięci dla 10 elementów.

 /**
 * 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 == EMPTY_ELEMENTDATA will be expanded to
 * DEFAULT_CAPACITY when the first element is added.
 */
private transient Object[] elementData;

P. S. Nie mam wystarczającej reputacji, aby skomentować pytanie, więc stawiam to jako odpowiedź, ponieważ nikt nie wskazał tego błędnego założenia wcześniej.

Do JDK 6 pojemność rośnie ze wzorem newCapacity = (oldCapacity * 3/2) + 1.

W JDK 7 i wyżej wzór zmienia się na newCapacity = oldCapacity + (oldCapacity >> 1).

Więc jeśli początkowa pojemność to 10 wtedy nowa pojemność to 16 in JDK6 i 15 in above JDK6

Powstaje nowa tablica z n * 2 spacjami, następnie wszystkie elementy starej tablicy są kopiowane i nowy element jest wstawiany do pierwszej wolnej przestrzeni. Podsumowując, powoduje to czas dodania O (N) dla ArrayList.

Jeśli używasz Eclipse, zainstaluj Jadi Jadclipse Aby dekompilować Jary znajdujące się w bibliotece. Zrobiłem to, aby przeczytać oryginalny kod źródłowy.

Wielkość ArrayList zawsze wzrasta z n+n/2+1.

Domyślna pojemność ArrayList to 10. Gdy pojemność osiągnie maksymalną pojemność, Rozmiar ArrayList będzie 16, gdy pojemność osiągnie maksymalną pojemność 16, Rozmiar ArrayList będzie 25 i nadal rośnie w oparciu o rozmiar danych.....

New capacity = (Current Capacity * 3/2) + 1

Więc jeśli domyślna pojemność to 10, to

Current Capacity = 10
New capacity = (10 * 3/2) + 1
Output is 16

static int getCapacity(ArrayList<?> list) throws Exception {
            Field dataField = ArrayList.class.getDeclaredField("elementData");
            dataField.setAccessible(true);
            return ((Object[]) dataField.get(list)).length;
    }

Użyj powyższej metody, aby sprawdzić rozmiar podczas modyfikacji arraylist.

W Jdk 1.6: New capacity = (Current Capacity * 3/2) + 1;

W Jdk 1.7:

Int j = i + (i > > 1); to jest to samo co New capacity = (Current Capacity * 1/2) + Current Capacity;

Ex: Rozmiar wzrośnie Jak :10-->15-->22-->33

ArrayList zwiększa rozmiar współczynnika obciążenia w następujących przypadkach:

• Pojemność Początkowa: 10
• współczynnik obciążenia: 1 (tzn. gdy lista jest pełna)
• tempo wzrostu: current_size + current_size / 2

Kontekst: JDK 7

Podczas dodawania elementu do ArrayList, następujące wywołania public ensureCapacityInternal i inne wywołania metod prywatnych zdarzają się wewnętrznie, aby zwiększyć rozmiar. To właśnie dynamicznie zwiększa Rozmiar ArrayList. podczas przeglądania kodu można zrozumieć logikę poprzez nazewnictwo konwencji, z tego powodu nie dodaję wyraźnego opisu

public boolean add(E paramE) {
        ensureCapacityInternal(this.size + 1);
        this.elementData[(this.size++)] = paramE;
        return true;
    }

private void ensureCapacityInternal(int paramInt) {
        if (this.elementData == EMPTY_ELEMENTDATA)
            paramInt = Math.max(10, paramInt);
        ensureExplicitCapacity(paramInt);
    }
private void ensureExplicitCapacity(int paramInt) {
        this.modCount += 1;
        if (paramInt - this.elementData.length <= 0)
            return;
        grow(paramInt);
    }

private void grow(int paramInt) {
    int i = this.elementData.length;
    int j = i + (i >> 1);
    if (j - paramInt < 0)
        j = paramInt;
    if (j - 2147483639 > 0)
        j = hugeCapacity(paramInt);
    this.elementData = Arrays.copyOf(this.elementData, j);
}

Spójrzmy na ten kod (jdk1. 8)

@Test
    public void testArraySize() throws Exception {
        List<String> list = new ArrayList<>();
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("cx");
        list.add("ww");
        list.add("ds");
        list.add("cx");
        list.add("last");
    }

1)umieść punkt przerwania na linii, gdy "ostatni" jest wstawiony

2) Przejdź do metody dodawania ArrayList Zobaczysz

ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;

3) go to ensureCapacityInternal method this method call ensureExplicitCapacity

4)

private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
            return true;

W naszym przykładzie minCapacity jest równe 11 11-10 > 0 dlatego potrzebujesz grow metody

5)

private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

Opisujemy każdy krok:

1) oldCapacity = 10 ponieważ nie umieściliśmy tego param Jeśli ArrayList był init, to będzie używał domyślnej pojemności(10)

2) int newCapacity = oldCapacity + (oldCapacity >> 1); Tutaj newCapacity jest równe oldcapacity plus oldCapacity z prawym przesunięciem o jeden (oldCapacity is 10 jest to reprezentacja binarna 00001010 przesuwając się o jeden bit w prawo otrzymamy 00000101, która jest 5 w dziesiętnym zatem newCapacity jest 10 + 5 = 15)

3)

if (newCapacity - minCapacity < 0)
                newCapacity = minCapacity;

Na przykład Twoja pojemność init wynosi 1, gdy dodasz drugi element do arrayList newCapacity będzie równa 1(oldCapacity) + 0 (moved to right by one bit) = 1 W tym przypadku newCapacity jest mniej nie można przechowywać nowego elementu, dlatego newCapacity jest równe minCapacity

4)

if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);

Sprawdź, czy rozmiar tablicy osiąga MAX_ARRAY_SIZE (czyli liczbę całkowitą.MAX-8) dlaczego maksymalny rozmiar tablicy ArrayList jest liczbą całkowitą.MAX_VALUE-8?

5) W końcu kopiuje stare wartości do newArray o długości 15

Domyślny rozmiar arraylist to 10. Kiedy dodamy 11 ....arraylist zwiększa rozmiar (n * 2). Wartości zapisane w starej arraylist są kopiowane do nowej arraylist, której rozmiar wynosi 20.