Vừa qua mình nhận được một vài câu hỏi về collection (Arraylist, LinkedList, Set, …) Và lúc đó mình chợt nhận ra rằng bản thân đã quên mất về các collection. Trong toàn bộ dự án dù lớn hay bé mình đều chỉ dùng ArrayList cả dù rằng biết nó sẽ không tối ưu. Cho nên hôm nay mình sẽ cùng các bạn tìm hiểu về collection trong java. Thú thật mình đã học qua về nó nhưng có lẽ chính việc học kiến thức một cách khô khan khiến mình quên mất đi tất cả. Cho nên trong bài viết này mình sẽ tìm hiểu theo một cách mới mẻ hơn. Đó chính là đi đọc mã nguồn của các collection. Oke let gâuuuuuu.
Sơ đồ sơ khai về các collection.
( Nguồn sưu tầm ) Ở đây mình cần một sơ đồ sơ khai để dễ hình dung về cấu trúc của các collection trước rồi mình sẽ tự vẽ lại nó ở phần sau.
I - ArrayList
Bây giờ ta sẽ đi đọc mã nguồn của ArrayList bằng cách:
Bước 1: Khởi tạo ArrayList
Bước 2: Mình sẽ đưa trỏ chuột vào ArrayList và ấn ctrl + click (Trên intellij bạn có thể dùng ctrl + b) Như ở đây ta thấy mã nguồn của ArrayList có: extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable. Tất nhiên ta sẽ không đọc tất cả mình sẽ tiếp tục vào AbstractList<E> bằng cách ctrl + click như trên. Mình sẽ tiếp tục như thế cho tới khi tới tận cùng hay chính là gốc cha nhé. Và sau khi một hồi loay hoay thì mình cũng đã vẽ lại được 1 sơ đồ như sau đối với ArrayList. Trên thực tế mọi thứ có thể phức tạp hơn nữa nhưng cốt lõi ta vẫn không cần quan tâm tới quá nhiều thứ như này. Ví dụ: RandomAccess, Cloneable, Serializable thực chất nó cũng chỉ cung cấp thêm tính năng cho ArrayList là chính. Thứ chúng ta quan tâm vẫn là cấu trúc cấu tạo của ArrayList mà thôi. Vậy nên ở đây mình sẽ tối giản lại sơ đồ này. Oke như thế này là đủ.
Nhìn vào sơ đồ này ta sẽ đọc từ gốc tới ngọn nên mình sẽ vào Iterable để tìm hiểu.
Iterable
Đập vào mắt mình là dòng comment:
Implementing this interface allows an object to be the target of the enhanced for statement (sometimes called the "for-each loop" statement).
Hiểu nôm na thì nếu mình implement interface này mình sẽ có thể dùng được chức năng for each thần thánh. Ô vậy ra trước giờ mọi thứ mình làm thật đơn giản và nhờ thứ này. 10 điểm cho em nó 😂
Để cho mọi thứ thật tuyệt vời mình sẽ test luôn em nó:
public class SimpleIterable implements Iterable<Integer> { private final int[] numbers; public SimpleIterable(int[] numbers) { this.numbers = numbers; } @Override public Iterator<Integer> iterator() { return new Iterator<Integer>() { private int index = 0; @Override public boolean hasNext() { return index < numbers.length; } @Override public Integer next() { if (!hasNext()) { throw new NoSuchElementException(); } return numbers[index++]; } }; } public static void main(String[] args) { int[] nums = {1, 2, 3, 4, 5}; SimpleIterable iterable = new SimpleIterable(nums); for (int number : iterable) { System.out.println(number); } }
}
Ở đây mình khởi tạo 1 class có chứa 1 mảng và dùng constructor để khởi tạo. Vì đã implement nên mình cần override để triển khai các abstract method. Ở đây có 3 cái cần override y như vòng lặp for vậy:
- Bắt đầu từ đâu ? private int index = 0;
- Đến đâu là dừng ? return index < numbers.length;
- Bước nhảy bao nhiêu ? return numbers[index++]
Oke vậy là ta đã hiểu được qua Iterable rồi đó. Và đọc trong ArrayList mình tìm được triển khai của Iterable trong ArrayList class
Collection
Đọc qua Collection chúng ta cũng sẽ thấy các phương thức hay sử dụng nằm ở đây. Ta có thể hiểu Collection chính là bộ khung cơ bản chứa các phương thức mà các collection implement sử dụng. Qua đây ta cũng có cách để xem liệu 1 collection có những phương thức nào thông qua việc đọc mã nguồn của nó.
SequencedCollection
Thực chất interface này cũng dùng để định nghĩa các phương thức cho việc cấu tạo collection. Bản chất ArrayList hay LinkedList hay collection nào cũng là cấu trúc dữ liệu liên kết. Nghĩa là 1 List gồm nhiều Node được nối với nhau thông qua con trỏ (Bạn có thể tìm hiểu thêm về nó). Vậy nên những phương thức trong interface này như getFirst, add, … khá là dễ hiểu đúng không nào.
List
Vẫn là cung cấp thêm 1 vài tính năng của List.
Việc chia ra làm nhiều interface implement nhau sẽ giúp module hóa các việc khác nhau qua đó nếu như một class nào chỉ cần dùng 1 nhánh vào đó có thể implement vào.
AbstractList
Dịch sang tiếng việt nôm na sẽ là: Đây là lớp cung cấp một triển khai cơ bản của giao diện List nhằm giảm thiểu công sức cần thiết để triển khai giao diện này dựa trên một kho dữ liệu "truy cập ngẫu nhiên" (chẳng hạn như một mảng). Đối với dữ liệu truy cập tuần tự (chẳng hạn như danh sách liên kết), nên sử dụng AbstractSequentialList thay cho lớp này. Để triển khai một danh sách không thể thay đổi, lập trình viên chỉ cần mở rộng lớp này và cung cấp các triển khai cho các phương thức get(int) và size().
Và hiểu nôm na sẽ là: Nó triển khai các interface ở trên ta đã nói :v
ArrayList (Chùm cúi)
Trong class này mình sẽ phải tìm hiểu về constructor xem các nó được khởi tạo. Qua đó mình sẽ hình dung được cấu trúc của nó. Và xem qua 1 vài method add, remove để xem nó thêm xóa giá trị trong mảng như thế nào. Đây là constructor. Ta thấy có 3 kiểu constructor là:
- Truyền số lượng mảng
- Constructor trống
- Truyền sẵn 1 mảng collection Và chung quy chúng đều tạo ra thứ này mình sẽ gọi nó là một Node.
Ta đến với phương thức add để xem cách nó thêm 1 Node vào ArrayList như thế nào. Qua đây ta hiểu cách hoạt động của add trong ArrayList. Nếu bạn chèn vào giữa 1 mảng ArrayList nó sẽ dịch chuyển toàn bộ phần sau của mảng và chèn giá trị bạn vào chỗ cần chèn.
Ban đầu mình nghĩa ArrayList sẽ là loại danh sách liên kết 1 chiều có con trỏ trỏ tới node next nhưng sau khi đọc mình hiểu rằng con trỏ ấy chính là index luôn. Thay vì phải có thêm 1 con trỏ thì ArrayList dùng index như cách con trỏ hoạt động. Nhờ việc làm này mà việc chèn cuối hay truy xuất tuần tự mảng hay việc truy xuất ngẫu nhiên 1 index sẽ cực kì là nhanh vì đơn giản nó chỉ cần lấy ngay index đã có nên thường các cái nói trên chỉ có độ phức tạp là O(1)
Tuy nhiên: Việc thêm sửa xóa sẽ chậm vì nó cần dịch chuyển lại toàn bộ index liên quan có thể lên tới O(n). Và để giải quyết vấn đề đó ta có LinkedList.
Tóm lại
**ArrayList là một cấu trúc mảng động sử dụng index để phân biệt cũng như truy cập các node. Do index không thay đổi nên khi ta cần chèn 1 phần tử hay xóa một phần tử giữa mảng thì đồng thời phần còn lại của mảng cũng phải tăng index hoặc giảm index. Do vậy việc thêm, xóa sẽ chậm (Nhanh O(1): chèn, xóa cuối dãy, chậm O(n): chèn, xóa đầu dãy ). Tuy vậy việc truy xuất ngẫu nhiên theo index hay truy xuất trình tự hoặc chèn cuối sẽ cực kì nhanh chỉ O(1) **
II - Linked List
Ta vẫn sẽ làm y hệt các bước lúc nãy. Để tránh mất thời gian đọc mình đã lấy được ra sơ đồ của em nó.
Ta thấy có sự giống nhau giữa ArrayList và LinkedList phải không nào. Điều này cũng giải thích vì sao 2 cái lại có cách sự dụng giống nhau đến thế. Ta chỉ cần tìm hiểu thẳng vào class LinkedList là xong.
Đập vào mắt mình chính là việc khai báo của Linked: Size: Lưu độ dài mảng first: Con trỏ cho node đầu last: Con trỏ cho node cuối Và dĩ nhiên ai đã học qua cấu trúc dữ liệu liên kết sẽ thấy rất quen đúng không nào. Và đúng thì LinkedList chính là 1 cấu trúc dữ liệu liên kết 2 chiều. Sau đó mình vẫn vào constructor xem nó làm như nào thì thấy nó gọi tới addAll. Mình cũng thử vào xem xem nó hoạt động ra sao nhé.
Ở đây ta cũng sẽ thấy rõ nó tạo node và truyền vào 3 tham số:
- pred: Địa chỉ node trước
- e: giá trị truyền
- null: địa chỉ node sau (Do khi ta chèn node này luôn là node cuối nên để địa chỉ sau là null)
Ở đây mình cũng tìm thấy được cấu hình của Node trong class.
Sau đó nó sẽ xem có node đầu chưa nếu chưa nó sẽ cho node vừa tạo làm node đầu bằng cách cho node = first. Nếu có rồi nó sẽ gắn prev cho nốt cuối và cho last = node. Thật ra đoạn này mình sẽ nói khá khó hiểu nếu bạn chưa học qua về cấu trúc dữ liệu liên kết. Đây là hình ảnh của linkedList. Vì linkedList được nối với nhau bằng địa chỉ chứ không phải index vậy nên nó là một liên kết vô cùng lỏng lẻo. Do vậy ta có thể dễ dàng chèn thêm 1 node vào giữa mảng bằng cách thay đổi địa chỉ các node liên quan. Như ở đây ta thấy 2 -> 7 nhưng ta chỉ cần thay đổi địa chỉ cho 2 -> 4 và 4 -> 7 là được. Tương tự với xóa cũng thế.
Tóm lại
**LinkedList là một cấu trúc dữ liệu liên kết 2 chiều và được liên kết với nhau bằng con trỏ. Do vậy liên kết nó sẽ rất lỏng lẻo cho phép ta chèn, xóa một cách cực dễ dàng và nhanh chóng O(1). Tuy vậy việc duyệt qua nó hay truy xuất nó lại chậm do phải thông qua con trỏ tìm địa chỉ tới node tiếp theo O(n). Và việc cần thêm 2 con trỏ trong 1 node cũng khiến cho nó trở nên nặng và tốn tài nguyên hơn so với ArrayList. **
So sánh ArrayList và LinkedList
Chat Gpt viết khá hay nên mình copy luôn :v
III - Vector
Và không thể không nhắc tới vector được ta cũng xem thử cấu trúc nó nhé.
Khá giống 2 cái trên đúng không nào. Ta có thể ví chúng là anh em của nhau :v. Đọc qua mình thấy khá giống ArrayList. Tuy vậy điểm khác lớn nhất của Vector so với ArrayList là đồng bộ hóa. Mọi method trong vector điều được đồng bộ hóa. Cho nên nó có thể đồng bộ hóa giữa nhiều luồng khác nhau. Do vậy nếu có 2 luồng đang chạy mà dùng cùng 1 ArrayList nó sẽ lỗi còn Vector thì không. Rõ ràng kết quả ArrayList đã sai. Còn với Vector lại đúng.
Đồng bộ hóa ArrayList
Tuy vậy ta vẫn có thể đồng bộ hóa ArrayList bằng cách sử dụng Collections.synchronizedList.
Syntax:
List<Integer> list = Collections.synchronizedList(new ArrayList<>());
IV - Tổng kết:
Vậy là qua bài đọc khá dài này chúng ta đã có một các tiếp cận công nghệ bằng một phương pháp khác. Bài viết vẫn còn nhiều lỗi mình mong được sự góp ý của tất cả mọi người. Chúc mọi người một ngày thật vui vẻ.