Не могу понять возможность переполнения при изменении размера ArrayList в Java - PullRequest
Новая
       4

Не могу понять возможность переполнения при изменении размера ArrayList в Java

4 голосов
/ 19 декабря 2011

Приведенный фрагмент кода из класса JDK 7 java.util.ArrayList смущает меня.Я не могу на всю жизнь понять, как это может привести к переполнению.Области, в которых я запутался, отмечены <--- what do they mean by this?.Может кто-нибудь помочь мне разобраться в обстоятельствах, при которых эта логика может переполниться?ТИА.

public void ensureCapacity(int minCapacity) {
    if (minCapacity > 0)
        ensureCapacityInternal(minCapacity);
}  

private void ensureCapacityInternal(int minCapacity) {
    modCount++;
    // overflow-conscious code <--- what do they mean by this?
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

private void grow(int minCapacity) {
    // overflow-conscious code <--- what do they mean by this?
    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);
}

private static int hugeCapacity(int minCapacity) {
    if (minCapacity < 0) // overflow <--- what do they mean by this?
        throw new OutOfMemoryError();
    return (minCapacity > MAX_ARRAY_SIZE) ?
        Integer.MAX_VALUE :
        MAX_ARRAY_SIZE;
}

РЕДАКТИРОВАТЬ: Моя главная задача заключается в следующем: как может огромная емкость получить отрицательный размер?

Ответы [ 4 ]

2 голосов
/ 19 декабря 2011

переполнение возникает, когда вычисленное значение превышает число байтов, разрешенных для его типа.

После выполнения некоторых операций над oldCapacity присваивается значение newCapacity, если эти операции приводят кнекоторое значение, которое не вписывается в int, тогда произойдет переполнение.Я думаю, именно поэтому этот код комментируется как код переполнения.

1 голос
/ 19 декабря 2011

OutOfMemoryError() (в ArrayList) выбрасывается для 2 условий:

  1. minCapacity меньше нуля. Это означает, что выделение массива памяти не может быть создано, т. Е. elementData размер массива не может быть меньше нуля.
  2. Емкость массива превысила пространство кучи памяти виртуальной машины. ВМ не может создать память (grow()) для выделения большего количества объектов в массиве.

Поэтому hugeCapacity() обеспечивает безопасное распределение памяти.

grow() и hugeCapacity() используются только в пределах ensureCapacityInternal(), поэтому можно сказать, что minCapacity < 0 не требуется. Я считаю, что это проверка безопасности, чтобы обеспечить рост массива. Любая несоответствие, скорее выкинь ошибку.

0 голосов
/ 09 января 2018

Я обнаружил ситуацию, когда minCapacity < 0.Предположим, есть два длинных массива ArrayList, когда вы добавляете один к другому, size + numNew будет переполнен.

public boolean addAll(Collection<? extends E> c) {
    Object[] a = c.toArray();
    int numNew = a.length;
    ensureCapacityInternal(size + numNew);  // Increments modCount
    System.arraycopy(a, 0, elementData, size, numNew);
    size += numNew;
    return numNew != 0;
}

Например, приведенный ниже код вызовет ошибку OutOfMemoryError. 

int oneSize = Integer.MAX_VALUE - 16;
int twoSize = oneSize >> 1;
List<Byte> one = new ArrayList<>(oneSize);
for (int i = 0; i < oneSize; i++) {
    one.add((byte) 1);
}
List<Byte> two = new ArrayList<>(twoSize);
for (int i = 0; i < twoSize; i++) {
    two.add((byte) 2);
}

one.addAll(two);
0 голосов
/ 19 декабря 2011

Я подозреваю, что в какой-то момент этот код мог быть изменен для работы с массивами, где array.length = long.(Конечно, это не обычная Java ... как мы ее знаем.)

...