Nội dung
Giới thiệu
Các giới hạn của việc sử dụng mảng (Array)
- Mảng rất cơ bản và quen thuộc .
- Lưu trữ các kiểu tham chiếu (object), các kiểu nguyên thủy (primitive type).
- int[] myArray = new int[]{1,4,3};
- Object[] myArrayObj = new Object[] { “Object”, new Integer(100) };
- Mảng có kích cỡ và số chiều cố định.
- Khó khăn cho việc mở rộng mảng
- Các phần tử được đặt và tham chiếu một cách liên tiếp nhau trong bộ nhớ.
- Khó khăn cho việc xóa một phần tử ra khỏi mảng .
Xóa phần tử ra khỏi mảng
Các phần tử của một mảng được đặt liên tiếp nhau trong bộ nhớ điều đó là khó khăn khi bạn cố tình bỏ đi một phần tử nào đó trong mảng, nó mất tính liên tiếp. Thông thường một kỹ thuật mà thường sử dụng là tạo một mảng mới lưu trữ các đối tượng của mảng ban đầu và bỏ đi các phần tử không cần thiết, nhưng điều này làm giảm hiệu năng của chương trình. Với trường hợp mở rộng mảng cũng với kỹ thuật tương tự là khởi tạo một mảng mới với kích cỡ lớn hơn sau đó thì copy các phần tử mảng cũ sang cho mảng mới.
Rõ ràng mảng không phải là một cách tốt cho nhiều trường hợp của ứng dụng .
Danh sách có kết nối (Linked List)
Danh sách có kết nối ( Linked List) là một trong các cách quản lý danh sách dữ liệu khắc phục được các nhược điểm của mảng. Tất nhiên để quản lý danh sách trong Java có nhiều cách khác ví dụ ArrayList.
Hãy xem các đặc điểm của LinkedList:
- Các phần tử trong danh sách này có thể nằm cách ly nhau (không liên tục) trong bộ nhớ .
- Nó thực sự là một liên kết có tính hai chiều giữa các phần tử.
- Mỗi phần tử trong danh sách cầm giữ một tham chiếu đến đối phần tử đằng trước nó và tham chiếu đến phần tử ngay sau nó.
LinkedList thực sự là một liên kết 2 chiều.
Phần tử Link là một đối tượng nó chứa dữ liệu bạn cần quản lý (data), và nó có 2 tham chiếu tới phần tử Link phía trước và phần tử Link phía sau nó. Cũng giống như một nhóm người xếp hàng, mỗi người chỉ cần nhớ người đứng trước họ là ai, và người đứng sau họ là ai.
Xóa một phần tử ra khỏi LinkedList
Xóa một phần tử ra khỏi LinkedList cũng giống bỏ một người ra khỏi hàng đang sắp xếp, hai người đứng gần người này phải cập nhập lại thông tin người đứng trước, đứng sau họ là ai.
Thêm phần tử vào LinkedList (Thêm vào cuối hoặc trèn vào giữa danh sách)
Như vậy mặc dù ta chỉ đưa ra một ví dụ về danh sách được liên kết xong nó cũng làm chúng ta hiểu hơn về package java.util.
Chú ý: LinkedList là một trong các giải pháp giải quyết hạn chế của mảng, ArrayList cũng là cách quản lý tập hợp dữ liệu, giải quyết được các hạn chế của mảng, nhưng cách thức quản lý dữ liệu của nó khác.
Hệ thống phân cấp của Collection Framework
Các kiểu tập hợp của Collection Framework được xây dựng trên cơ sở một số interface trong package java.util. Và được phân chia ra làm 2 hệ thống phân cấp dẫn đầu bởi 2 interface java.util.Collection chứa danh sách các đối tượng và java.util.Map chứa các cặp key/value.
Hệ thống phân cấp của chúng được mô tả tổng quát như bên dưới:
Cách thức chứa dữ liệu
Cấp cao nhất của lớp Collection là Iterable interface, nó chứa dữ liệu thành viên Iterator interface.
Hệ thống phân cấp tiếp theo dẫn đầu bởi 2 interface Collection và Map:
Nhóm Collection lưu trữ các đối tượng.
- Có 3 nhánh con trong nhóm Collection: List, Queue, Set .
- List (danh sách):
- List (danh sách) là một collection có thứ tự (đôi khi còn được gọi là một chuỗi).
- List có thể chứa các phần tử trùng lặp.
- Ví dụ: [1, 7, 1, 3, 1, 1, 1, 5]
- Có thể get phần tứ “thứ N” trong danh sách. Có thể thêm một phần tử vào bất kỳ một vị trí nào trong danh sách, thay đổi một phần tử nào tại một vị trí nào đó trong danh sách, hoặc xóa một phần tử tại một vị trí bất kỳ trong danh sách.
- Queue (hàng đợi):
- Queue (hàng đợi) cũng là một tập hợp tuần tự, nhưng bạn chỉ có thể chạm vào phần tử đứng ở đầu hàng đợi.
- Queue có thể được sử dụng như là FIFO (first-in, first-out – vào trước, ra trước). Tất cả các phần tử được trèn vào phía cuối của hàng đợi và xóa phần tử đầu tiên của hàng đợi. Bạn có thể biết được có bao nhiêu phần tử trong hàng đợi, nhưng bạn không thể tìm ra hoặc nói về phần tử thứ N, bạn chỉ có thể thấy nó khi nó đứng lên đầu tiên của hàng đợi.
- Queue là tập hợp cho phép các phần tử trùng lặp.
- Queue không cho phép phần tử null.
Deque (Double Ended Queue): là một collection được sử dụng để chứa nhiều phần tử trước khi xử lý. Ngoài các thao tác cơ bản của collection, một Deque cung cấp các thao tác bổ sung như chèn, lấy ra và kiểm tra. Deques có thể được sử dụng như là FIFO (first-in, first-out – vào trước, ra trước) và LIFO (last-in, first-out – vào sau, ra trước). Trong một Deque, tất cả các phần tử mới có thể được chèn vào, lấy ra và lấy ra ở cả hai đầu. Các phần tử có thể giống nhau hoặc không phụ thuộc vào thuộc nhánh nào trong 3 nhánh kể trên.
- Set (tập hợp): là một tập hợp không tuần tự, và nó không cho phép trùng lặp. Bạn không thể nói về phần tử thứ N thậm chí là phần tử đầu tiên, vì nó không có sự tuần tự. Bạn có thể thêm hoặc xóa các phần tử, và có thể tìm ra nếu thực sự nó tồn tại. SortedSet là một interface con của Set nó có thể chứa các phần tử có thứ tự.
- List (danh sách):
Nhóm Map lưu trữ các cặp key/value
- Map: là một đối tượng ánh xạ mỗi key tương úng với một value. Map không thể chứa key trùng lặp. Mỗi key có thể ánh xạ đến nhiều nhất một giá trị.
- Các cặp key/value chứa trong Map (bản đồ) là luôn có key khác nhau giữa các cặp
- Nếu biết key có thể lấy ra giá trị value trong Map ứng với key này .
Hai interface được sắp xếp (sort) của Set mà Map:
- SortedSet: là một interface con của Set, nó có thể chứa các phần tử có thứ tự tăng dần.
- SortedMap: là một Map chứa các phần tử được sắp xếp theo thứ tự tăng dần của key của chúng. Các SortedMap được sử dụng cho các collection theo thứ tự tự nhiên của cặp key/value, chẳng hạn như từ điển và danh bạ điện thoại.
Cách thức lấy dữ liệu
Trên hình minh họa trên có 2 Interface Iterator & RandomAccess, nó đại diện cho 2 cách truy cập vào các phần tử trong một tập hợp.
- java.util.Iterator: giống như một máy lặp để lấy dữ liệu, cách truy cập lần lượt từ phần tử này đến phần tử khác.
- java.util.RandomAccess: cách truy cập ngẫu nhiên, ví dụ cho vị trí phần tử và lấy ra phần tử đó trong tập hợp.
- java.util.Collection: mở rộng từ interface java.lang.Iterable (có thể lặp được), nó thừa kế phương thức public Iterator<E> iterator(). Do đó, nhóm Collection có thể truy cập theo kiểu lần lượt bằng cách gọi phương thức iterator() để lấy được đối tượng Iterator
Chú ý: Đối với các đối tượng trong nhóm List bạn cũng có thể lấy ra đối tượng ListIterator, bộ lặp này cho phép bạn lùi và tiến vị trí con trỏ trên tập hợp thay vì chỉ có thể tiến như của Iterator.
Ví dụ:
package java.util; public class Vector<E> extends AbstractList<E> public class Vector<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, Serializable
Như ví dụ trên Vector thuộc nhóm Collection, bạn có thể truy cập các phần tử của nó thông qua Iterator và cũng có thể truy cập ngẫu nhiên thông qua phương thức get(index).
Các phương thức của một số Interface trong Collection Framework
Các phương thức của Iterator interface
Phương thức | Mô tả |
public boolean hasNext() | Trả về true nếu iterator còn phần tử kế tiếp phần tử đang duyệt. |
public object next() | Trả về phần tử hiện tại và di chuyển con trỏ trỏ tới phần tử tiếp theo. |
public void remove() | Loại bỏ phần tử cuối được trả về bởi Iterator. |
Các phương thức của interface Collection trong java
Phương thức | Mô tả |
public boolean add(Object element) | Thêm một phần tử vào collection. |
public boolean addAll(Collection c) | Thêm các phần tử collection được chỉ định vào collection gọi phương thức này. |
public boolean remove(Object element) | Xóa phần tử ra khỏi collection. |
public boolean removeAll(Collection c) | Xóa tất cả các phần tử từ collection được chỉ định ra khỏi collection gọi phương thức này. |
public boolean retainAll(Collection c) | Xóa tất cả các thành phần từ collection gọi phương thức này ngoại trừ collection được chỉ định. |
public int size() | Trả về tổng số các phần tử trong collection. |
public void clear() | Xóa tất cả các phần tử trong Collection, sau khi thực hiện phương thức này, Collection sẽ rỗng (empty) |
public boolean contains(Object element) | Kiểm tra một phần tử có nằm trong Collection không |
public boolean containsAll(Collection c) | Kiểm tra một Collection có chứa tất cả các phần tử của một Collection khác |
public Iterator iterator() | Trả về một iterator. |
public Object[] toArray() | Chuyển đổi collection thành mảng (array). |
public boolean isEmpty() | Kiểm tra Collection có rỗng hay không. |
public boolean equals(Object element) | So sánh 2 collection. |
public int hashCode() | Trả về số hashcode của collection. |
Các phương thức của Map Interface
Phương thức | Mô tả |
Object put(Object key, Object value) | Thêm một cặp key/value (entry) vào map |
void putAll(Map map) | Thêm các tất cả các cặp key/value được chỉ định vào map gọi phương thức này. |
Object remove(Object key) | Xóa một entry của map dựa vào key được chỉ định. |
Object get(Object key) | Get value của map entry dựa vào key được chỉ định. |
boolean containsKey(Object key) | Kiểm tra map có tồn tại key được chỉ định. |
Set keySet() | Lấy tập hợp tất cả các key của map. |
Set entrySet() | Lấy tập hợp các cặp key/value (entry) của map |
Các phương thức của Map.Entry Interface
Phương thức | Mô tả |
Object getKey() | Lấy khóa (key) của một Entry |
Object getValue() | Lấy giá trị (value) của một Entry |
Ví dụ về Collection Framework
Ví dụ khai báo collection, map trong java
package com.gpcoder.collection; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Set; public class CollectionExample { public static final int NUM_OF_ELEMENT = 5; public static void main(String[] args) { List<String> arrayList = new ArrayList<>(); for (int i = 1; i <= NUM_OF_ELEMENT; i++) { arrayList.add("0" + i); } System.out.println("ArrayList: " + arrayList); List<String> linkedList = new LinkedList<>(); for (int i = 1; i <= NUM_OF_ELEMENT; i++) { linkedList.add("0" + i); } System.out.println("LinkedList: " + linkedList); Set<String> hashSet = new HashSet<String>(); for (int i = 1; i <= NUM_OF_ELEMENT; i++) { hashSet.add("0" + i); } System.out.println("HashSet: " + hashSet); Map<String, Integer> hashMap = new HashMap<>(); for (int i = 1; i <= NUM_OF_ELEMENT; i++) { hashMap.put("Key0" + i, i); } System.out.println("HashMap: " + hashMap); } }
Kết quả thực thi chương trình trên:
ArrayList: [01, 02, 03, 04, 05] LinkedList: [01, 02, 03, 04, 05] HashSet: [01, 02, 03, 04, 05] HashMap: {Key01=1, Key02=2, Key03=3, Key04=4, Key05=5}
Ví dụ duyệt các phần tử của collection
Có nhiều cách để duyệt các phần tử của collection trong java. Trong ví dụ bên dưới tôi sử dụng:
- Iterator interface
- Vòng lặp for
- Vòng lặp for-each
- Vòng while
- Stream trong Java8
- …
package com.gpcoder.collection; import java.util.ArrayList; import java.util.Iterator; import java.util.List; import java.util.ListIterator; public class CollectionExample { public static final int NUM_OF_ELEMENT = 5; public static void main(String[] args) { List<String> list = new ArrayList<>(); for (int i = 1; i <= NUM_OF_ELEMENT; i++) { list.add("0" + i); } System.out.print("Using For Size: "); for (int i = 0; i < NUM_OF_ELEMENT; i++) { System.out.print(list.get(i) + " "); } System.out.println(); System.out.print("Using Foreach: "); for (String item : list) { System.out.print(item + " "); } System.out.println(); System.out.print("Using For Iterator: "); for (Iterator<String> iter = list.iterator(); iter.hasNext();) { System.out.print(iter.next() + " "); } System.out.println(); System.out.print("Using While ListIterator: "); ListIterator<String> listIter = list.listIterator(); while (listIter.hasNext()) { System.out.print(listIter.next() + " "); } System.out.println(); System.out.print("Using While Iterator: "); Iterator<String> iter = list.iterator(); while (iter.hasNext()) { System.out.print(iter.next() + " "); } System.out.println(); System.out.print("Using While Size: "); int i = 0; while (i < NUM_OF_ELEMENT) { System.out.print(list.get(i) + " "); i++; } System.out.println(); System.out.print("Using ForEach Java8: "); list.forEach(s -> System.out.print(s + " ")); System.out.println(); System.out.print("Using Stream ForEach Java8: "); list.stream().forEach(s -> System.out.print(s + " ")); } }
Kết quả thực thi chương trình trên
Using For Size: 01 02 03 04 05 Using Foreach: 01 02 03 04 05 Using For Iterator: 01 02 03 04 05 Using While ListIterator: 01 02 03 04 05 Using While Iterator: 01 02 03 04 05 Using While Size: 01 02 03 04 05 Using ForEach Java8: 01 02 03 04 05 Using Stream ForEach Java8: 01 02 03 04 05
Ví dụ duyệt các phần tử của Map
package com.gpcoder.collection; import java.util.HashMap; import java.util.Map; public class CollectionExample { public static final int NUM_OF_ELEMENT = 5; public static void main(String[] args) { // Khởi tạo map Map<String, Integer> hashMap = new HashMap<>(); for (int i = 1; i <= NUM_OF_ELEMENT; i++) { hashMap.put("Key0" + i, i); } // Duyệt các phần tử của map sử dụng phương thức keySet() System.out.println("Using keySet(): "); for (String key : hashMap.keySet()) { Integer value = hashMap.get(key); System.out.println(key + " = " + value); } // Duyệt các phần tử của map sử dụng phương thức entrySet() System.out.println("Using entrySet(): "); for (Map.Entry<String, Integer> entry : hashMap.entrySet()) { String key = entry.getKey(); Integer value = entry.getValue(); System.out.println(key + " = " + value); } } }
Kết quả thực thi chương trình trên:
Using keySet(): Key01 = 1 Key02 = 2 Key03 = 3 Key04 = 4 Key05 = 5 Using entrySet(): Key01 = 1 Key02 = 2 Key03 = 3 Key04 = 4 Key05 = 5
Tài liệu tham khảo:
- https://www.javatpoint.com/collections-in-java
- http://o7planning.org/vi/10165/huong-dan-su-dung-nen-tang-tap-hop-trong-java
- https://docs.oracle.com/javase/8/docs/api/java/util/Collection.html
Trên đây là những lý thuyết cơ bản về nền tảng tập hợp (Collection Framework) trong Java. Ở những bài viết tiếp theo, tôi sẽ hướng dẫn chi tiết từng tập hợp, so sánh sự giống nhau, khác nhau và trường hợp sử dụng của chúng. Cám ơn các bạn đã quan tâm và theo dõi bài viết. Hẹn gặp lại ở bài viết tiếp theo.