Chiều 30 tết cuối năm, rảnh viết nốt bài để đón tết con Heo 😀

Tiếp tục là 1 bài về so sánh các thứ trong Java, cái này thi thoảng cũng gặp khi phỏng vấn nhưng bài này mình muốn giúp các bạn có thể hiểu rõ hơn về bản chất để sử dụng hợp lý hơn, đảm bảo hiệu năng tốt hơn.

Trước tiên mình muốn đề cập Array mô tả 1 cấu trúc dữ liệu mảng cơ bản từ C/C++. Array được lưu trữ trong 1 dãy các ô nhớ liền nhau trong bộ nhớ và có thể truy xuất trực tiếp đến từng phần tử thông qua số thứ tự (index) của phần tử trong mảng. Không có các tiện ích sẵn để add/get/remove… phần tử mà chỉ có thuộc tính length để lấy kích thước. Kích thước của Arraycố định và buộc phải định nghĩa khi khai báo.

Còn ArrayList LinkedListVector, cả 3 cái này đều là class implement List, trong đó List là 1 collection trong Java được thiết kế có đầy đủ các method cơ bản như get, add, remove, sort,… vì vậy ArrayList LinkedListVector implement lại List đều mang đầy đủ những tiện ích này từ List. List được lưu trữ dưới dạng các ô nhớ rải rác trong bộ nhớ trỏ đến nhau thông qua địa chỉ ô nhớ. Việc này nhằm tối ưu về bộ nhớ có thể tận dụng các ô nhớ ở các vị trí khác nhau không nhất thiết phải liền nhau, nhưng lại gây ra việc không thể truy xuất trực tiếp đến 1 phần từ bất kỳ mà phải duyệt từ đầu List để tìm.

Tìm hiểu chi tiết hơn.

LinkedList là class implement List và cũng mang đầy đủ tiện ích của List và được bổ sung thêm các tiện ích của Deque tối ưu cho các thao tác add/remove phần từ, hay các tiện ích của AbstractSequentialList giúp tối ưu khi duyệt phần tử bằng Iterator. Nhưng lại không được tối ưu cho việc truy xuất ngẫu nhiên qua số thứ tự phần tử nên ít khi được sử dụng. Kích thước danh sách là động và được tăng mỗi khi bổ sung phần tử.

ArrayList là class implement List, được mang thêm tiện ích của RandomAccess giúp tối ưu việc truy xuất ngẫu nhiên qua số thứ tự, nhưng lại không được implement Deque nên các thao tác add/remove không nhanh như LinkedList (mình sẽ có ví dụ test performce cụ thể ở dưới). Kích thước ArrayList là cố định tại 1 thời điểm, nhưng có thể resize thêm 50% mỗi khi đạt giới hạn max hiện tại nên có thể coi là kích thước động.

Vector là class implement giống hệt ArrayList nên mang đầy đủ tiện ích như ArrayList có, và hơn thế nữa được xây dựng thêm các method thao tác phần tử như addElement setElement removeElement insertElement …. và đặc biệt các method của Vector đều được cài đặt synchronized nghĩa là safe nhưng fail-fast, an toàn cho dữ liệu khi sử dụng trong đa luồng nhưng lại gây chậm xử lý. Kích thước của Vector tương tự như ArrayList chỉ khác là sẽ tăng 100% mỗi khi đạt giới hạn max hiện tại.

Các bạn có thể đọc thêm docs của java hoặc đơn giản là decompile jdk hoặc đọc trong source nén của jdk để thấy rõ hơn về những sự giống và khác biệt này.

Tổng hợp lại dưới dạng bảng từ đó rút ra cân nhắc sử dụng cái nào trong từng trường hợp cụ thể.

Array ArrayList LinkedList Vector
Là mảng nguyên thủy, chỉ có thuộc tính length Là class implement List, có các method hỗ trợ get/add/remove/…
Kích thước cố định Tăng 50% kích thước khi đạt giới hạn Kích thước động Tăng 100% kích thước khi đạt giới hạn
Lưu kiểu dữ liệu nguyên thủy và đối tượng Chỉ lưu kiểu dữ liệu đối tượng, từ Java 5 kiểu nguyên thủy được tự động chuyển đổi thành đối tượng để lưu trữ (auto-boxing)
Tốc độ lưu trữ và truy xuất nhanh Tốc độ truy xuất theo index nhanh Tốc độ truy xuất theo index chậm Tốc độ truy xuất theo index nhanh
Rất kém trong việc insert/remove phần tử ở giữa mảng Tốc độ insert/remove phần tử trong mảng trung bình Tốc độ insert/remove phần tử trong mảng nhanh Tốc độ insert/remove phần tử trong mảng trung bình
Không hỗ trợ synchronized, dễ mất dữ liệu khi xử lý đa luồng nhưng nhanh Không hỗ trợ synchronized, dễ mất dữ liệu khi xử lý đa luồng nhưng nhanh Không hỗ trợ synchronized, dễ mất dữ liệu khi xử lý đa luồng nhưng nhanh Hỗ trợ synchronized, an toàn dữ liệu khi xử lý đa luồng nhưng chậm
Thường dùng với các thao tác bổ sung vào cuối mảng và truy xuất thông thường, sử dụng khi nghiệp vụ đơn giản ít nâng cấp Sử dụng để lưu trữ và truy xuất dữ liệu cơ bản, ít khi thay đổi Sử dụng khi cần thao tác thay đổi dữ liệu nhiều, cho các nghiệp vụ phức tạp Sử dụng khi cần thao tác với nhiều luồng xử lý

Dưới đây là các đoạn test performance khi thực hiện add/get/remove trên Array/ArrayList/LinkedList để nhìn trực quan hơn về sự khác biệt. Các kết quả có thể sẽ không chính xác như ví dụ với từng lần chạy nhưng về cơ bản vẫn có độ chênh lệch có thể nhìn thấy

Kết quả

Lưu ý, các bạn có thể sửa các đoạn logger.infor thành System.out.println để test.

Ta có thể thấy array nhanh hơn khá nhiều khi thêm và truy xuất phần tử, các bộ test sau đấy thì phải cài đặt phương thức thủ công nên mình ko đưa Array vào. Ở phần test get 1 phần tử trong mảng bằng vòng lặp for index thì LinkedList quá chậm so với ArrayList vì mỗi lần gọi get(i) là phải duyệt từ đầu danh sách theo từng con trỏ next để tìm được thứ tự phù hợp, độ phức tạp của get(i) LinkedList sẽ là O(n) trong khi của ArrayList chỉ là O(1).

Còn với test method get(i) bằng iterator thì cả ArrayListLinkedList đều sử dụng con trỏ next implement từ List nên kết quả có thể coi là tương đương nhau.

Đến phần test remove phần tử thì ArrayList yếu thế hơn vì mỗi lần remove thì RandomAccess phải sắp xếp lại index từ vị trí remove đến cuối để được chuỗi liên tục nên thời gian xử lý tăng lên, trong khi LinkedList chỉ cần ngắt con trỏ tại ví trí remove để trỏ đến ô nhớ tiếp theo là hoàn tất.

Tiếp theo, ta thử so sánh performance giữa ArrayListVector trong tình huống đơn luồng

Kết quả cho thấy tốc độ xử lý của cả 2 tạm coi là tương đương nhau do Vector có cài đặt giống với ArrayList. Có sai khác thì phần lớn là do môi trường và thời điểm test.

Nếu thử với tình huống đa luồng thì sao nhỉ

Kết quả khi thực hiện

Ta có thể thấy Vector chậm hơn khá nhiều so với ArrayList nhưng ArrayList lại xảy ra xung đột khi nhiều thread cùng truy xuất vào phần tử. Các bạn có thể thử lại với add hoặc remove để biết thêm các trường hợp khác.

Qua bài này hi vọng các bạn có thể hiểu rõ hơn bản chất của những thứ rất cơ bản nhưng ít ai để ý và có thể ứng dụng hợp lý nhất cho các đoạn code của mình giúp cho hệ thống hoạt động trơn tru hiệu quả hơn 🙂

Bình luận