Java ArrayList trong ảnh

Xin chào! Bài giảng hôm nay ArrayListmột mặt sẽ đơn giản hơn nhưng mặt khác sẽ khó hơn những bài trước. Điều đó khó khăn hơn vì hôm nay chúng ta sẽ xem xét “chi tiết” ArrayListvà nghiên cứu xem điều gì xảy ra với nó trong quá trình vận hành. Mặt khác, bài giảng này hầu như sẽ không có code - chủ yếu là hình ảnh và giải thích. Vì vậy, hãy bắt đầu :) Như bạn đã biết, bên trong ArrayList'a có một mảng thông thường, 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ó kích thước nào đó! Điều này là đúng. 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, chúng ta hãy xem việc thêm một phần tử mới trông như thế nào. Trước hết, việc kiểm tra được thực hiện để xem liệu có đủ không gian trong mảng bên trong hay không và liệu có thêm một phần tử nào phù hợp hay không. Nếu còn chỗ trống, phần tử mới sẽ được thêm vào cuối danh sách. Khi chúng ta nói “đến cuối”, chúng ta không có ý nói đến ô cuối cùng của mảng (điều đó thật lạ). Điều này đề cập đến ô bên cạnh phần tử hiện tại cuối cùng. Chỉ số của nó sẽ bằng cars.size(). Danh sách của chúng tôi hiện đang trống ( cars.size() = 0). Theo đó, một phần tử mới sẽ được thêm vào ô có chỉ mục 0.

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

Mọi thứ đều rõ ràng ở đây. Điều gì sẽ xảy ra nếu việc chèn được thực hiện ở giữa, tức là giữa một số phần tử?

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);//добавляем ford в ячейку 1, которая уже занята
}

Một lần nữa, trước tiên nó sẽ kiểm tra xem có đủ dung lượng trong mảng hay không. Nếu có đủ không gian, các phần tử sẽ được dịch chuyển sang bên phải bắt đầu từ ô nơi chúng ta chèn phần tử mới. Chúng ta dán vào ô có chỉ số 1. Tức là phần tử từ ô 3 được sao chép sang ô 4, phần tử 2 sang ô 3, phần tử 1 sang ô 2. Sau đó, phần tử mới của chúng ta được dán vào vị trí. Phần tử trước đó ( bugatti) đã được sao chép từ đó sang vị trí mới. Bây giờ hãy tìm hiểu xem quá trình này sẽ diễn ra như thế nào nếu không có khoảng trống để chèn vào mảng. Tất nhiên, trước tiên, việc kiểm tra được thực hiện để xem có đủ dung lượng hay không. Nếu không có đủ dung lượng, ArrayListmột mảng có kích thước mới (kích thước của OldArray * 1.5) + 1 sẽ được tạo bên trong 'a. Trong trường hợp của chúng tôi, mảng mới sẽ có kích thước 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ị trình thu gom rác xóa và chỉ còn lại mảng mới, được mở rộng. Bây giờ có không gian trống cho phần tử mới. Chúng tôi dán nó vào ô 3, ô đã bị chiếm 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 từ chỉ mục 3 được dịch chuyển một ô sang bên phải và một phần tử mới được thêm vào một cách lặng lẽ. Và bây giờ việc chèn thành công! Chúng tôi đã sắp xếp việc chèn. Bây giờ hãy nói về việc loại bỏ các phần tử . Như bạn còn nhớ, khi làm việc với mảng, chúng tôi gặp phải một vấn đề: khi chúng tôi xóa chúng, các “lỗ hổng” vẫn còn trong đó. Giải pháp duy nhất là dịch chuyển các phần tử sang trái mỗi khi chúng bị xóa và bạn phải tự viết mã cho ca làm việc đó. ArrayListhoạt động theo nguyên tắc tương tự, nhưng trong đó cơ chế này đã được triển khai tự động. Nó trông như thế này: Và cuối cùng chúng ta nhận được kết quả mong muốn: Phần tử lambođã được xóa thành công. Ở đây chúng tôi đã loại bỏ từ giữa. Rõ ràng là việc xóa từ cuối danh sách sẽ nhanh hơn vì phần tử mong muốn sẽ bị xóa mà không làm dịch chuyển tất cả các phần tử khác. Chúng ta hãy xem xét lại kích thước của mảng bên trong và việc lưu trữ nó trong bộ nhớ. Mở rộng mảng là một quá trình cần một lượng tài nguyên nhất định. Vì vậy, bạn không nên tạo ArrayListvới kích thước mặc định nếu biết chắc chắn rằng nó sẽ có ít nhất 100 phần tử. Vào thời điểm bạn chèn phần tử thứ 100, mảng bên trong sẽ mở rộng 6 lần , mỗi lần chuyển tất cả các phần tử.

• 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 (theo công thức (kích thước của Mảng Cũ * 1.5) + 1)

Đương nhiên, điều này khá tốn kém về mặt tài nguyên. Do đó, nếu bạn đã biết một số (ít nhất là gần đúng) số phần tử được lưu trữ, tốt hơn là tạo ngay một danh sách với một mảng có kích thước nhất định:

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

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