ArrayList trong ảnh

CHÀO! Bài học hôm nay ArrayListsẽ vừa dễ vừa khó hơn các bài học trước. Sẽ khó khăn hơn vì hôm nay chúng ta sẽ xem xét ArrayListvà nghiên cứu những gì xảy ra trong các hoạt động khác nhau. Mặt khác, bài học này sẽ hầu như không có mã. Nó chủ yếu là hình ảnh và giải thích. Chà, bắt đầu nào :) Như bạn đã biết, ArrayListcó một mảng thông thường bên trong, hoạt động như một kho lưu trữ dữ liệu. Trong hầu hết các trường hợp, chúng tôi không chỉ định kích thước chính xác của danh sách. Nhưng mảng bên trong phải có một số kích thước! Và như vậy nó làm. Kích thước mặc định của nó là 10 .

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
}

Đầu tiên, hãy xem việc thêm các phần tử mới trông như thế nào. Thứ tự đầu tiên của công việc là kiểm tra xem mảng bên trong có đủ không gian trong mảng bên trong hay không và liệu một phần tử nữa có phù hợp hay không. Nếu có khoảng trống thì phần tử mới sẽ được thêm vào cuối danh sách. Khi chúng tôi nói "đến cuối", chúng tôi không có nghĩa là vị trí cuối cùng trong mảng (điều đó thật kỳ lạ). Chúng tôi muốn nói đến vị trí theo sau phần tử hiện tại cuối cùng. Chỉ số của nó sẽ là cars.size(). Danh sách của chúng tôi hiện đang trống ( cars.size() == 0). Theo đó, phần tử mới sẽ được thêm vào ở vị trí 0.

ArrayList<Car> cars = new ArrayList<>();
Car ferrari = new Car("Ferrari 360 Spider");
cars.add(ferrari);

Điều đó đủ rõ ràng. Điều gì xảy ra nếu chúng ta chèn vào giữa, tức là giữa các phần tử khác?

public static void main(String[] args) {
   ArrayList<Car> cars = new ArrayList<>();
   Car ferrari = new Car("Ferrari 360 Spider");
   Car bugatti = new Car("Bugatti Veyron");
   Car lambo = new Car("Lamborghini Diablo");
   Car ford = new Car("Ford Modneo");
  
   cars.add(ferrari);
   cars.add(bugatti);
   cars.add(lambo);
  
   cars.add(1, ford);// add ford to cell 1, which is already occupied
}

Một lần nữa, đầu tiên là kiểm tra xem có đủ khoảng trống trong mảng hay không. Nếu có đủ không gian, thì các phần tử sẽ được dịch chuyển sang phải , bắt đầu từ vị trí mà chúng ta sẽ chèn phần tử mới. Chúng ta đang chèn ở vị trí 1. Nói cách khác, phần tử từ vị trí 3 được sao chép sang vị trí 4, phần tử 2 sang vị trí 3 và phần tử 1 sang vị trí 2. Sau đó, phần tử mới của chúng ta được chèn vào vị trí của nó. Phần tử trước đó (bugatti) đã được sao chép từ đó sang một vị trí mới. Bây giờ hãy xem quá trình này diễn ra như thế nào nếu không có chỗ để chèn các phần tử mới vào mảng. Đương nhiên, trước tiên phải kiểm tra xem có đủ chỗ không. Nếu không đủ chỗ, thì một mảng mới sẽ được tạo bên trongArrayListcó kích thước bằng kích thước của mảng cũ nhân 1,5 cộng 1 Trong trường hợp của chúng ta, kích thước của mảng mới sẽ là 16. Tất cả các phần tử hiện tại sẽ được sao chép vào đó ngay lập tức. Mảng cũ sẽ bị bộ thu gom rác xóa và chỉ còn lại mảng mới, được mở rộng. Bây giờ có chỗ cho một yếu tố mới. Chúng tôi đang chèn nó vào vị trí 3, vị trí đã được sử dụng. Bây giờ thủ tục quen thuộc bắt đầu. Tất cả các phần tử, bắt đầu với chỉ số 3, được dịch chuyển sang phải một vị trí và phần tử mới được thêm vào một cách lặng lẽ. Và việc chèn được thực hiện! Và chúng ta đã hoàn thành việc chèn. Bây giờ hãy nói về việc loại bỏ các mục . Bạn sẽ nhớ rằng chúng ta đã gặp phải một vấn đề khi làm việc với mảng: việc loại bỏ các phần tử sẽ tạo ra các "lỗ hổng" trong mảng.với mỗi lần xóa và chúng tôi phải viết mã của riêng mình mỗi lần để thực hiện ca này. ArrayList tuân theo nguyên tắc tương tự, nhưng nó đã thực hiện cơ chế này. Đây là giao diện của nó: Và cuối cùng, chúng ta có được thứ mình muốn: Phần lambotử đã bị xóa. Ở đây chúng tôi đã loại bỏ một phần tử ở giữa. Rõ ràng, việc loại bỏ một phần tử khỏi cuối danh sách sẽ nhanh hơn, vì phần tử này được loại bỏ đơn giản mà không cần phải chuyển tất cả các phần tử khác. Chúng ta hãy nói lại một chút về kích thước của mảng bên trong và cách nó được sắp xếp trong bộ nhớ. Mở rộng một mảng cần một số tài nguyên. Theo đó, không tạo ra mộtArrayListvới kích thước mặc định nếu bạn chắc chắn rằng nó sẽ có ít nhất 100 phần tử. Mảng bên trong sẽ phải được mở rộng 6 lần vào thời điểm bạn chèn phần tử thứ 100 và tất cả các phần tử sẽ phải được dịch chuyển mỗi lần.

• từ 10 phần tử đến 16
• từ 16 phần tử đến 25
• từ 25 đến 38
• từ 38 đến 58
• từ 58 đến 88
• từ 88 đến 133 (tức là kích thước của mảng cũ nhân 1,5 cộng 1)

Như bạn có thể tưởng tượng, điều này khá tốn tài nguyên. Vì vậy, nếu bạn đã biết (thậm chí xấp xỉ) số lượng mục cần thiết, thì tốt hơn là tạo một danh sách với một mảng có kích thước cụ thể:

ArrayList<Car> cars = new ArrayList<>(100);

Giờ đây, bộ nhớ cho một mảng gồm 100 phần tử sẽ được cấp phát cùng một lúc, giúp mảng hoạt động hiệu quả hơn (không cần mở rộng). Chiến lược này cũng có một mặt trái. Khi bạn loại bỏ các đối tượng khỏi một mảng ArrayList, kích thước của mảng bên trong không tự động giảm. Giả sử chúng ta có ArrayListmột mảng bên trong hoàn toàn đầy đủ gồm 88 phần tử: Khi chương trình chạy, chúng ta loại bỏ 77 phần tử, vì vậy chỉ còn lại 11 phần tử: Bạn đã đoán ra vấn đề là gì chưa? Bạn hiểu rồi, sử dụng bộ nhớ không hiệu quả! Chúng tôi chỉ sử dụng 11 vị trí ở đây, nhưng chúng tôi đã phân bổ bộ nhớ cho 88 phần tử. Đó là gấp 8 lần so với chúng ta cần! Trong trường hợp này, chúng ta có thể tối ưu hóa việc sử dụng bộ nhớ bằng một trong ArrayListcác phương thức đặc biệt của lớp:trimToSize(). Phương thức này "cắt bớt" độ dài của mảng bên trong xuống theo số lượng phần tử hiện được lưu trữ trong đó. Bây giờ chúng tôi chỉ phân bổ nhiều bộ nhớ như chúng tôi cần! :)