- Collections ra đời là để khắc phục những hạn chế, nhược điểm khi sử dụng mảng để lập trình. Trong bài đầu tiên, tôi sẽ giới thiệu tổng quan về Collections trong Java và sau đó tôi sẽ lần lượt giới thiệu chi tiết về từng loại Collections trong các bài tiếp theo.Collections là một tập các lớp dùng để lưu trữ danh sách và có khả năng tự co dãn khi danh sách đó thay đổi, ví dụ như khi chúng ta thêm, sửa, xóa, chèn phần tử trong danh sách đó. Ngoài ra, Collections còn được dùng để lưu trữ, truy xuất, tương tác với dữ liệu và truyền dữ liệu giữa các phương thức với nhau (chi tiết về phương thức tôi sẽ giới thiệu trong chương Lập trình hướng đối tượng).Một đặc điểm rất quan trong là khi sử dụng Collections đó là chúng ta không cần phải khai báo trước số lượng phần tử. Chính đặc điểm này đã khắc phục được hạn chế về kích thước khi khai báo mảng trong Java.Collections Framework
- Framework là một tập hợp các thư viện (Library) đã được đóng gói để hỗ trợ phát triển ứng dụng dựa trên Framework đó. Đồng thời, Framework cung cấp các nguyên tắc, cấu trúc của ứng dụng mà chúng ta phải tuân thủ theo nó."
- Collections Framework được hiểu như sau: "Một Java Collections Framework là một tập hợp các lớp (class) và các interface dùng để hỗ trợ việc thao tác trên tập các đối tượng" (chi tiết về interface tôi sẽ giới thiệu trong chương Lập trình hướng đối tượng, nhưng bạn có thể hiểu nôm na là 1 interface là 1 lớp rỗng chỉ chứa khai báo về tên phương thức, không có khai báo về thuộc tính hay thứ gì khác và các phương thức này cũng là phương thức rỗng).
Trong Java, các Collections Framework cung cấp những thành phần sau:
Loại thành phần | Mô tả |
---|---|
Interfaces | Kiểu dữ liệu trừu tượng (abstract) biểu diễn Collections (chi tiết về abstract tôi sẽ giới thiệu trong chương Lập trình hướng đối tượng). |
Implementations | Là sự triển khai các Interface, ví dụ như các Class. |
Algorithms (các thuật toán) | Là các phương thức dùng để thực thi các phép toán như tìm kiếm và sắp xếp trên các đối tượng mà triển khai các Interface. |
Interface Collections
Là một tập hợp đại diện cho một nhóm các đối tượng, và được gọi là các phần tử (elements).
Một số Interface Collection cho phép lưu trữ các phần tử giống nhau, còn một số khác thì không. Ngoài ra, các phần tử này có thể có thứ tự hoặc không có thứ tự tùy theo từng loại Collection khác nhau.
Bao gồm các phương thức như thêm (add), xóa (clear), so sánh (compare) và duy trì (retainining) các đối tượng.
Trong Interface Collections chúng ta có các Interface chính như: List Interface, Set, SortedSet, Map và SortedMap. Bảng dưới đây sẽ mô tả khái quát về các Interface này:
Tên Interface | Đặc điểm khái quát |
---|---|
List Interface | Các phần tử trong List Interface được sắp xếp có thứ tự và có thể có giá trị giống nhau. |
Set | Các phần tử trong Set là duy nhất (nghĩa là giá trị của các phần tử này không được giống nhau). |
SortedSet | Là 1 dạng riêng của Set Interface, trong đó giá trị của các phần tử mặc định được sắp xếp tăng dần. |
Map | Giá trị của mỗi phần tử trong Map bao gồm 2 phần đó là khóa (key) và giá trị tương ứng của key đó (value) và khóa của các phần tử này là duy nhất. |
SortedMap | Là 1 dạng riêng của Map Interface, trong đó giá trị key được sắp xếp tăng dần. |
Class Collections
Java cung cấp một tập hợp các lớp tiêu chuẩn dùng để triển khai các Interface Collection. Trong Class Collections chúng ta có rất nhiều loại nhưng trong phạm vi của series Lập trình Java căn bản này thì chúng ta chỉ cần nắm 6 loại chính sau: LinkedList, ArrayList, HashSet, TreeSet, HashMap và TreeMap. Bảng dưới đây sẽ mô tả khái quát về các Class này:
Tên Class | Đặc điểm khái quát |
---|---|
LinkedList (Danh sách liên kết) | Là 1 cấu trúc dữ liệu lưu trữ các phần tử dưới dạng danh sách. Các phần tử trong LinkedList được sắp xếp có thứ tự và có thể có giá trị giống nhau. |
ArrayList | Là kiểu danh sách sử dụng cấu trúc mảng để lưu trữ phần tử. Thứ tự các phần tử dựa theo thứ tự lúc thêm vào và giá trị của các phần tử này có thể trùng nhau. |
HashSet | Thứ tự các phần tử trong HashSet không dựa theo thứ tự lúc thêm vào và giá trị của các phần tử này là duy nhất. |
TreeSet | Các phần tử trong TreeSet mặc định được sắp xếp tăng dần và giá trị của các phần tử này là duy nhất. |
HashMap | Giá trị của mỗi phần tử trong HashMap bao gồm 2 phần đó là khóa (key) và giá trị tương ứng của key đó (value) và khóa của các phần tử này là duy nhất. HashMap cho phép truy xuất trực tiếp dữ liệu bằng khóa duy nhất của nó. |
TreeMap | Giá trị của mỗi phần tử trong TreeMap bao gồm 2 phần đó là khóa (key) và giá trị tương ứng của key đó (value) và khóa của các phần tử này là duy nhất. Giá trị của các phần tử trong TreeMap được sắp xếp tăng dần. |
Algorithms (các thuật toán)
Collections Framework trong Java cung cấp các thuật toán để các Collection có thể sử dụng được.
List Interface là một loại Interface Collection. Như đã nói trong bài Tổng quan về Collection trong Java, các phần tử của List Interface được sắp xếp có thứ tự và giá trị của các phần tử này có thể trùng nhau.
Các phần tử trong
List
có thể được truy cập, thêm, sửa hoặc xóa thông qua vị trí của nó trong danh sách, và phần tử đầu tiên trong List
sẽ có chỉ số là 0.
Dưới đây là hình ảnh minh họa một List Interface:
Trong hình trên các bạn thấy List này có 5 phần tử là
apple
, lemon
, banana
, orange
và grape
. Phần tử đầu tiên là apple
có chỉ số là 0
và phần tử cuối cùng là grape
có chỉ số là 4
.
để khai báo một List chúng ta cần phải dùng đến các Class để triển khai nó, trong phần này chúng ta sẽ sử dụng 2 loại phổ biến nhất là
ArrayList
và LinkedList
.- Set Interface là một loại Interface Collection. Khác với
List
, các phần tử trongList
có thể giống nhau, còn đối vớiSet
, các phần tử trongSet
là duy nhất (nghĩa là giá trị của các phần tử này không được giống nhau).
Vậy
Set
được sử dụng trong trường hợp nào? Chúng ta sẽ sử dụng Set
khi chúng ta muốn lưu trữ một danh sách các phần tử không có sự trùng lặp hoặc khi chúng ta không quan tâm đến thứ tự của các phần tử trong danh sách đó.- dể khai báo một Set chúng ta cần phải dùng đến các Class để triển khai nó, trong phần này chúng ta sẽ sử dụng 2 loại phổ biến nhất là
HashSet
vàTreeSet
. Đối với Set Interface cóClass
triển khai làHashSet
thì các phần tử không được sắp xếp theo bất kỳ thứ tự nào, còn đối với Set Interface cóClass
triển khai làTreeSet
thì thứ tự các phần tử trongSet
được sắp xếp tăng dần - SortedSet Interface là 1 dạng riêng của Set Interface nên nó có những đặc điểm của
Set
đó là các phần tử trongSortedSet
là duy nhất (nghĩa là giá trị của các phần tử này không được giống nhau) vàSortedSet
được sử dụng khi chúng ta muốn lưu trữ một danh sách các phần tử không có sự trùng lặp. Ngoài ra,SortedSet
có điểm vượt trội hơn so vớiSet
là thứ tự các phần tử trongSet
được sắp xếp tăng dần hoặc giảm dần (mặc định là tăng dần).
Để khai báo một
SortedSet
, chúng ta cần phải dùng đến Class
để triển khai nó, trong phần này chúng ta sẽ sử dụng Class
là TreeSet
bởi vì các phần tử trong TreeSet
được sắp xếp theo chiều tăng dần.- Map là một tập các cặp khóa - giá trị (key - value). Giá trị của các phần tử trong Map có thể giống nhau, nhưng khóa thì không được giống nhau (vì thế chúng ta có thể tạo ra 1 Set có các phần tử là khóa của Map). Dựa vào khóa, chúng ta có thể xác định được các giá trị value tương ứng với khóa đó. Dưới đây là hình ảnh minh họa mối quan hệ giữa key và value trong Map:
Map được sử dụng trong trường hợp chúng ta muốn truy xuất, cập nhật hoặc tìm kiếm phần tử thông qua khóa của phần tử đó. Ví dụ:
- Một Map bao gồm thông tin của người quản lý và nhân viên trong một công ty. Mỗi một người quản lý (key) sẽ liên kết với danh sách các nhân viên mà người đó quản lý (value).
- Một Map bao gồm thông tin của một lớp học và các sinh viên có trong lớp đó. Mỗi một lớp (key) sẽ liên kết với danh sách các sinh viên của lớp đó (value)
để khai báo một Map chúng ta cần phải dùng đến các Class để triển khai nó, trong phần này chúng ta sẽ sử dụng 3 loại phổ biến nhất là
HashMap
, LinkedHashMap
và TreeMap
. Đối với Map Interface có Class
triển khai là HashMap
thì thứ tự các phần tử không dựa theo thứ tự lúc thêm vào, đối với Map Interface có Class
triển khai là LinkedHashMap
thì thứ tự các phần tử dựa theo thứ tự lúc thêm vào, còn đối với Map Interface có Class triển khai là TreeMap
thì thứ tự các phần tử được sắp xếp theo chiều tăng dần của khóa.- SortedMap Interface là 1 dạng riêng của Map Interface nên nó có những đặc điểm của
Map
đó là SortedMap cũng bao gồm một tập các cặp khóa - giá trị (key - value). Giá trị của các phần tử trong SortedMap có thể giống nhau, nhưng khóa thì không được giống nhau, và dựa vào khóa chúng ta có thể xác định được các giá trị value tương ứng với khóa đó. Ngoài ra, SortedMap có điểm vượt trội hơn so với Map là các entry có trong SortedMap được sắp xếp tăng dần theo khóa.
Để khai báo một
SortedMap
, chúng ta cần phải dùng đến Class
để triển khai nó, trong phần này chúng ta sẽ sử dụng Class
là TreeMap
bởi vì các entry
trong TreeMap
được sắp xếp tăng dần theo khóa.
ArrayList và Vector cả hai được impements giao diện List và duy trì thứ tự chèn của các phần tử.
ArrayList | Vector |
---|---|
1) ArrayList là không synchronized. | Vector là synchronized. |
2) ArrayList tăng 50% kích thước hiện tại nếu số phần tử vượt quá khả năng chứa của nó. | Vector tăng 100% nghĩa là tăng gấp đôi kích thước hiện tại nếu số phần tử vượt quá khả năng chứa của nó.. |
3) ArrayList không là một lớp legacy, nó được tạo ra từ phiên bản JDK 1.2. | Vector là một lớp lớp legacy. |
4) ArrayList là nhanh hơn vì nó là non-synchronized. | Vector là chậm hơn ví nó là synchronized. Tức là, trong môi trường đa luồng, các thread giữ nó ở trong trạng thái runnable hoặc non-runnable cho đến khi thread hiện tại giải phóng đối tượng đó. |
5) ArrayList sử dụng Iterator để duyệt các phần tử. | Vector sử dụng Enumeration và Iterator để duyệt các phần tử. |
Khác nhau giữa vector và list
List là double linked list
Vector là dynamic array, tức là array được cấp phát động bằng Allocator23
Vector là dynamic array, tức là array được cấp phát động bằng Allocator23
Khi nào nên dùng list và khi nào nên dùng vector?
Nên mặc định sử dụng
vector
. Bởi vì phần lớn các trường hợp mình hay dùng là thêm phần tử vào cuối mảng và truy xuất random một phần từ nào đấy. Vector là array, việc thêm phần tử vào cuối mảng hay lấy một phần tử bất rất dễ dàng và nhanh.
Khi náo ử dụng
list
?
Khi ta cần thêm/xóa phần tử ở giữa mảng hoặc ở đầu mảng nhiều hơn so với việc thêm vào ở cuối. Và không có nhu cầu truy vấn random các phần tử một cách thường xuyên
Ưu và nhược của chúng là gì?
Ưu của vector:
Thêm vào cuối mảng nhanh, truy xuất phần tử nhanh vì mỗi phần tử đều có index.
Nhược của vector:
Chèn phần tử chậm, cần một khoảng nhớ liên tiếp để chứa mảng. Khi hết chứa đủ mảng thì cần phải allocate/move9 một mảng mới với số phần tử gấp đôi.
Ưu của list:
Chèn phần tử, xóa phần tử nhanh, không cần một khoảng nhớ liên tiếp để chứa các phần tử vì nó là double linked list
Nhược của list:
Truy xuất phần tử chậm vì các phần tử không có index thực, phải duyệt danh sách phần tử cho tới khi tới được phần tử cần.
Tuy nhiên, có vài sự khác nhau giữa ArrayList và Vector được đưa ra dưới đây:
- Lớp Stack là một lớp phụ của lớp Vector trong Java mà triển khai một last-in-first-out (LIFO) stack. Bạn có thể nghĩ về Stack như là một ngăn xếp thẳng đứng.
Stack chỉ định nghĩa constructor mặc định, mà tạo một stack trống. Lớp Stack bao gồm tất cả phương thức được định nghĩa bởi lớp Vector, và một số phương thức khác của riêng nó.
Stack và Queue trong Java
Chào mừng các bạn đã quay trở lại với thachleblog, tiếp tục chuyên mục Java collections. Ở bài trước, mình đã có bài so sánh về ArrayList và LinketList. Bài viết hôm nay mình sẽ tiếp tục chia sẻ về Stack và Queue trong Java. Stack và Queue trong Java được implement như thế nào? Giải quyết vấn đề gì, chúng ta cùng bắt đầu nhé.
Giới thiệu
Stack là kiểu cấu trúc dữ liệu mà các phần từ thêm vào và lấy ra được thực hiện theo cơ chế Last – In – First – Out (LIFO), tức là phần tử nào được thêm vào đầu tiên thì sẽ được lấy ra sau cùng. Ví dụ một cái hộp để đựng đĩa, cái nào được đặt vào đầu tiên sẽ được lấy ra sau cùng. Ở đây cái hộp đựng đĩa được hiểu như là Stack.
Queue là kiểu cấu trúc dữ liệu mà các phần tử thêm vào là lấy ra được thực hiện theo cơ chế Fist – In – First – Out (FIFO), tức là phần tử nào thêm vào đầu tiên sẽ được lấy ra đầu tiên (có vẻ công bằng ^.^). Ví dụ mọi người xếp hàng đợi lên xe bus, người nào đứng trước sẽ được lên xe trước.
Ví dụ minh họa Stack và Queue
Implement
Trong Java, Stack API gồm các method:

Có 2 method đáng chú ý là push() là thêm vào một phần tử và pop() là lấy ra phần tử mà được thêm vào gần nhất.
Queue API gồm các method:

Tương tự Stack, Queue có các method enqueue() là thêm một phần tử vào Queue và dequeue() là lấy ra phần tử mà được thêm vào trước nhất.
Ứng dụng
Việc sử dụng đúng Stack và Queue có thể sẽ giải quyết được các vấn đề phức tạp nếu sử dụng các collection khác. Bởi vì Stack và Queue được tạo ra để giải quyết các vấn đề đó.
Ví dụ Stack, chúng ta cần danh sách những sản phẩm vừa được mua gần nhất hoặc những khách hàng vừa mới truy cập. Sử dụng Stack để lưu trữ các thông tin trên, chỉ cần lấy ra là chúng ta có được kết quả mong muốn.
Queue thì mình sử dụng trong ghi log (tracking data), dữ liệu log sẽ được thêm vào Queue và ghi lần lượt xuống đĩa, đảm bảo dữ liệu log theo thứ tự thời gian…
Lớp Dictionary trong Java là một lớp abstract mà biểu diễn một kho lưu giữ key/value và hoạt động khá giống lớp Map trong Java.
Với một cặp key/value đã cung cấp, bạn có thể lưu giữ giá trị trong đối tượng Dictionary. Khi giá trị được lưu, bạn có thể thu nhận nó bởi sử dụng key của nó. Ngoài ra, giống như lớp Map, một Dictionary có thể được xem như là một danh sách các cặp key/value.
Các cấu trúc dữ liệu trong Java
Các cấu trúc dữ liệu cung cấp bởi các package tiện ích của Java rất mạnh mẽ và thực hiện các tính năng rộng rãi. Những cấu trúc dữ liệu này bao gồm những interface và class.
Lớp Enumeration trong Java
Interface Enumeration bản thân nó không phải là cấu trúc dữ liệu, nhưng rất quan trọng bên trong ngữ cảnh sử dụng các cấu trúc dữ liệu khác. Interface Enumeration định nghĩa để nhận các thành phần kế tiếp từ cấu trúc dữ liệu.
Ví dụ, Enumeration định nghĩa phương thức gọi là nextElement được sử dụng để lấy các thành phần tiếp theo trong cấu trúc dữ liệu chứa nhiều thành phần.
Lớp BitSet trong Java
Lớp BitSet trong Java triển khai một nhóm các bit hoặc flag mà có thể được thiết lập và xóa một cách riêng rẽ.
Class này rất hữu dụng trong trường hợp bạn muốn lưu trữ một tập các giá trị Boolean và chỉ muốn gắn từng bit các giá trị và thiết lập hoặc xóa nó thích hợp.
Lớp Vector trong Java
Lớp Vector trong Java là tương tự như các mảng dữ liệu Java truyền thống, ngoại trừ việc có thể tăng lưu trữ cho các thành phần mới.
Giống như mảng, các thành phần trong đối tượng Vector có thể truy cập bởi index.
Một điều tốt về việc sử dụng Vector là bạn không phải lo lắng về việc cài đặt nó cho một kích cỡ cụ thể ngoài việc tạo ra nó, nó có thể tăng và giảm độ lớn khi cần thiết.
Lớp Stack trong Java
Lớp Stack trong Java triển khai một last-in-first-out (LIFO) stack các phần tử.
Bạn có thể nghĩ về stack như một ngăn xếp thẳng đứng các đối tượng, khi bạn thêm một đối tượng mới, bạn lấy nó ở phần đầu các thành phần khác.
Khi bạn lấy một thành phần trên stack, nó lấy từ trên đỉnh xuống. Theo cách nói khác, thành phần cuối cùng mà bạn thêm vào stack sẽ là thành phần đầu tiên khi lấy ra và ngược lại.
Lớp Dictionary trong Java
Lớp Dictionary là một abstract class để định nghĩa cấu trúc dữ liệu cho việc liên kết giữa các key tới value.
Nó thực sự hữu ích trong các trường hợp khi bạn muốn có thể truy cập dữ liệu thông qua một key cụ thể thay vì sử dụng một integer index.
Khi lớp Dictionary là abstract, nó chỉ cung cấp framework cho một cấu trúc dữ liệu so khớp key thay vì một sự triển khai cụ thể.
Lớp Hashtable trong Java
Lớp Hashtable cung cấp các ý nghĩa về mặt tổ chức dữ liệu dựa vào cấu trúc mà người dùng định nghĩa key.
Ví dụ, một danh sách địa chỉ bạn có thể lưu trữ và xếp thứ tự dựa và key như zip code hơn là việc sử dụng tên người.
Ý nghĩa đặc trưng của các key liên quan tới hashtable là hoàn toàn phụ thuộc vào hashtable và dữ liệu nó chứa.
Lớp Properties trong Java
Lớp properties là lớp con của Hashtable. Nó được sử dụng để duy trì danh sách các giá trị trong đó key là String và value cũng là một String.
Lớp Properties được sử dụng bởi nhiều class khác trong Java. Ví dụ, bạn có một kiểu đối tượng trả về bởi System.getProperties() để lấy về các biến môi trường.
Nhận xét
Đăng nhận xét