Java: Cách ArrayList quản lý bộ nhớ

Question

Trong lớp Cấu trúc dữ liệu của tôi, chúng tôi đã nghiên cứu lớp Java ArrayList và cách nó phát triển mảng cơ bản khi người dùng thêm nhiều phần tử hơn. Điều đó được hiểu. Tuy nhiên, tôi không thể tìm ra cách chính xác lớp này giải phóng bộ nhớ khi có nhiều phần tử bị loại bỏ khỏi danh sách. Nhìn vào nguồn, có ba phương pháp loại bỏ các phần tử:

public E remove(int index) { 
RangeCheck(index); 

modCount++; 
E oldValue = (E) elementData[index]; 

int numMoved = size - index - 1; 
if (numMoved > 0) 
    System.arraycopy(elementData, index+1, elementData, index, 
     numMoved); 
elementData[--size] = null; // Let gc do its work 

return oldValue; 
} 

public boolean remove(Object o) { 
if (o == null) { 
      for (int index = 0; index < size; index++) 
    if (elementData[index] == null) { 
     fastRemove(index); 
     return true; 
    } 
} else { 
    for (int index = 0; index < size; index++) 
    if (o.equals(elementData[index])) { 
     fastRemove(index); 
     return true; 
    } 
     } 
return false; 
} 


private void fastRemove(int index) { 
     modCount++; 
     int numMoved = size - index - 1; 
     if (numMoved > 0) 
      System.arraycopy(elementData, index+1, elementData, index, 
          numMoved); 
     elementData[--size] = null; // Let gc do its work 
} 

Không ai trong số đó giảm mảng dữ liệu. Tôi thậm chí còn bắt đầu đặt câu hỏi nếu bộ nhớ miễn phí lên bao giờ xảy ra, nhưng các thử nghiệm thực nghiệm cho thấy rằng nó. Vì vậy, phải có một số cách khác nó được thực hiện, nhưng ở đâu và như thế nào? Tôi đã kiểm tra các lớp cha mẹ cũng như không thành công.

Answer 1

Chúng không làm giảm mảng cơ bản. Họ chỉ đơn giản là giảm kích thước. Lý do cho điều này là nếu bạn có 1000 phần tử trong một mảng và xóa 1, tại sao tái phân bổ và sao chép mảng? Đó là cực kỳ lãng phí cho rất ít được.

Về cơ bản Java ArrayList s có hai thuộc tính quan trọng và điều quan trọng là phải hiểu chúng khác nhau:

• kích thước: bao nhiêu yếu tố này là notionally trong List; và

• công suất: số lượng phần tử có thể phù hợp với mảng cơ bản.

Khi mở rộng khoảng 50% ngay cả khi bạn chỉ thêm một phần tử. Đây là một nguyên tắc tương tự ngược lại. Về cơ bản nó đi xuống này: reallocating mảng và sao chép các giá trị là (tương đối) đắt tiền. Vì vậy, nhiều như vậy mà bạn muốn giảm thiểu nó xảy ra. Miễn là kích thước tiêu chuẩn là với một nhà máy khoảng 2 của kích thước mảng, nó chỉ là không đáng lo ngại về.

Answer 2

Tôi phải có một cái nhìn khác về mã nguồn của ArrayList, nhưng remove loại bỏ đối tượng khỏi mảng, và sau đó nếu đối tượng không được tham chiếu bởi bất kỳ đối tượng nào khác, GC có thể xóa đối tượng đó. Nhưng kích thước mảng không giảm.

Answer 3

Không có nhiều lợi ích bằng cách thay đổi kích thước mảng nội bộ ArrayList, thậm chí bạn đang sử dụng ArrayList để giữ một đối tượng lớn.

List<LargeObject> list = new ArrayList<LargetObject>(); 

danh sách sẽ chỉ giữ tham chiếu đến cá thể LargeObject và không giữ chính đối tượng LargeObject.

Tham chiếu không tiêu tốn nhiều không gian. (Hãy suy nghĩ nó như con trỏ trong C)

Answer 4

Kích thước mảng không bao giờ được giảm tự động. Rất hiếm khi thực sự có một danh sách được lấp đầy đầu tiên với một số lượng lớn các nguyên tố, sau đó đã làm trống nhưng vẫn giữ nguyên. Và hãy nhớ rằng phải có đủ bộ nhớ để giữ danh sách (chỉ bao gồm các tham chiếu) và các phần tử của nó - không chắc rằng bộ nhớ được tiêu thụ bởi danh sách trống sẽ là một vấn đề.

Nếu bạn thực sự gặp phải thuật toán kỳ quái đủ để điều này trở thành vấn đề, bạn vẫn có thể giải phóng bộ nhớ bằng cách gọi trimToSize() theo cách thủ công.

Answer 5

Một ArrayList không tự động thu nhỏ lại, theo như tôi biết. Tuy nhiên, bạn có thể nói điều gì đó như:

ArrayList al = new ArrayList(); 

// fill the list for demo's sake 
for (int i = 0; i < 1000000; ++i) 
{ 
    al.add(i); 
} 

// now remove all but one element 
al.removeRange(1, al.size()); 

// this should shrink the array back to a decent size 
al.trimToSize(); 

Lưu ý, lượng bộ nhớ có thể sẽ không thay đổi cho đến khi chạy lại GC.