Tổng quan về Collections trong Java
Bài đăng này đã không được cập nhật trong 3 năm
1. Giới thiệu Java Collection Framework
Bất kì lập trình viên nào đã từng làm việc với Java hay Android có lẽ đều biết tới ArrayList – một class cực kì dễ dùng và tiện dụng. Nhưng có lẽ không nhiều người biết rằng ArrayList chỉ là một trong số rất nhiều class thuộc bộ thư viện Java Collection Framework của Java – một bộ thư viện với rất nhiều class mạnh mẽ giúp bạn đơn giản hóa các thao tác khi làm việc với tập hợp và đồ thị. Java Collection Framework (có thể gọi là nền tảng tập hợp) được xây dựng các interface đinh nghĩa các cách thao tác với tập hợp, các class cụ thể thực thi các interface và các giải thuật thông dụng thường xuyên được sử dụng với tập hợp. Java Collection Framework cung cấp cho bạn hầu như tất cả những gì bạn cần khi muốn làm việc với các tập hợp hay là đồ thị, không chỉ vậy nó còn cho phép bạn mở rộng bằng các kế thừa từ các class hay interface có sẵn để tạo ra bộ thư viện phù hợp nhất với nhu cầu của bạn. Collection framework được thiết kế với mục đích như sau:
- Framework phải là hiệu năng cao. Sự triển khai cho các tập hợp cơ bản (các mảng động, linked list, tree và hashtable) được sử dụng với hiệu quả cao.
- Framework phải cho phép các kiểu tập hợp khác nhau để làm việc theo một cách tương tự như nhau với độ phân hóa ở mức cao.
- Kế thừa và/hoặc tìm hiểu với các tập hợp phải là dễ dàng. Một collections framework là một cấu trúc thống nhất để biểu diễn và thao tác các collection. Tất cả collections framework đều chứa:
- Interface: Đây là các kiểu dữ liệu abstract mà biểu diễn collection. Interface cho phép collection được thao tác một cách độc lập theo phép biểu diễn của chúng. Trong ngôn ngữ hướng đối tượng, các interface nói chung cấu tạo nên một hierarchy.
- Sự triển khai: ví dụ như các Class Đây là sự triển khai cụ thể của collection interface. Về bản chất, chúng là những cấu trúc dữ liệu có thể tái sử dụng.
- Thuật toán: Đây là các phương thức thực hiện các trình tính toán hữu ích, như tìm kiếm và xếp thứ tự phân loại, trên các đối tượng mà triển khai collection interface. Các thuật toán được xem như là đa hình: đó là, cùng một phương thức có thể được sử dụng trên nhiều sự triển khai khác nhau của collection interface thích hợp.
- Ngoài ra, framework định nghĩa một số map interfaces và class. Map lưu giữ các cặp key/value. Mặc dù các map không là collections về khái niệm, nhưng chúng hoàn toàn tương thích với collection. Để làm rõ hơn mình sẽ đi luôn vào giới thiệu tới các bạn từng thành phần chính được của Java Collection Framework.
2. Collection Interface
Collection Interface định nghĩa những phương thức cơ bản khi làm việc với tập hợp, đây là gốc cũng là nền móng để từ đó xây dựng lên cả bộ thư viện Java Collection Framework. Collection Interface được kế thừa từ Iterable Interface nên các bạn có thể dễ dàng duyệt qua từng phần tử thông qua việc sử dụng Iterator.
3. Set Interface
Set (tập hợp) là kiểu dữ liệu mà bên trong nó mỗi phần tử chỉ xuất hiện duy nhất một lần (tương tự như tập hợp trong toán học vậy) và Set Interface cung cấp các phương thức để tương tác với set. Set Interface được kế thừa từ Collection Interface nên nó cũng có đầy đủ các phương thức của Collection Interface. Một số class thực thi Set Interface thường gặp:
- TreeSet: là 1 class thực thi giao diện Set Interface, trong đó các phần tử trong set đã được sắp xếp.
- HashSet: là 1 class implement Set Interface, mà các phần tử được lưu trữ dưới dạng bảng băm (hash table).
- EnumSet: là 1 class dạng set như 2 class ở trên, tuy nhiên khác với 2 class trên là các phần tử trong set là các enum chứ không phải object.
4. List Interface
List (danh sách) là cấu trúc dữ liệu tuyến tính trong đó các phần tử được sắp xếp theo một thứ tự xác định. List Interface định nghĩa các phương thức để tương tác với list cũng như các phần tử bên trong list. Tương tự như Set Interface, List Interface cũng được kế thừa và có đầy đủ các phương thức của Collection Interface.
Một số class thực thi List Interface thường sử dụng:
- ArrayList: là 1 class dạng list được implement dựa trên mảng có kích thước thay đổi được.
- LinkedList: là một class dạng list hoạt động trên cơ sở của cấu trúc dữ liệu danh sách liên kết đôi (double-linked list)
- Vector: là 1 class thực thi giao diện List Interface, có cách thực lưu trữ như mảng tuy nhiên có kích thước thay đổi được, khá là tương tự với ArrayList, tuy nhiên điểm khác biệt là Vector là synchronized, hay là đồng bộ, có thể hoạt động đa luồng mà không cần gọi synchronize một cách tường minh
- Stack: cũng là 1 class dạng list, Stack có cách hoạt động dựa trên cơ sở của cấu trúc dữ liệu ngăn xếp (stack) với kiểu vào ra LIFO (last-in-first-out hay vào sau ra trước) nổi tiếng.
5. Queue Interface
Queue (hàng đợi) là kiểu dữ liệu nổi tiếng với kiểu vào ra FIFO (first-in-first-out hay vào trước ra trước), tuy nhiên với Queue Interface thì queue không chỉ còn dừng lại ở mức đơn giản như vậy mà nó cũng cấp cho bạn các phương thức để xây dựng các queue phức tạp hơn nhiều như priority queue (queue có ưu tiên), deque (queue 2 chiều), … Và cũng giống như 2 interface trước, Queue Interface cũng kế thừa và mang đầy đủ phương thức từ Collection Interface. Một số class về Queue thường sử dụng:
- LinkedList: chính là LinkedList mình đã nói ở phần List
- PriorityQueue: là 1 dạng queue mà trong đó các phần tử trong queue sẽ được sắp xếp.
- ArrayDeque: là 1 dạng deque (queue 2 chiều) được implement dựa trên mảng
6. Map Interface
Map (đồ thị/ánh xạ) là kiểu dữ liệu cho phép ta quản lý dữ liệu theo dạng cặp key-value, trong đó key là duy nhất và tương ứng với 1 key là một giá trị value. Map Interface cung cấp cho ta các phương thức để tương tác với kiểu dữ liệu như vậy. Không giống như các interface ở trên, Map Interface không kế thừa từ Collection Interface mà đây là 1 interface độc lập với các phương thức của riêng mình. Dưới đây là một số class về Map cần chú ý:
- TreeMap: là class thực thi giao diện Map Interface với dạng cây đỏ đen (Red-Black tree) trong đó các key đã được sắp xếp. Class này cho phép thời gian thêm, sửa, xóa và tìm kiếm 1 phần tử trong Map là tương đương nhau và đều là O(log(n))
- HashMap: là class thực thi giao diện Map Interface với các key được lưu trữ dưới dạng bảng băm, cho phép tìm kiếm nhanh O(1).
- EnumMap: cũng là 1 Map class nữa, tuy nhiên các key trong Map lại là các enum chứ không phải object như các dạng Map class ở trên.
- WeakHashMap: tương tự như HashMap tuy nhiên có 1 điểm khác biệt đáng chú ý là các key trong Map chỉ là các Weak reference (hay Weak key), có nghĩa là khi phần tử sẽ bị xóa khi key được giải phóng hay không còn một biến nào tham chiếu đến key nữa.
Nguồn tham khảo:
http://vietjack.com/java/collection_trong_java.jsp https://docs.oracle.com/javase/8/docs/technotes/guides/collections/overview.html http://that2u.com/java-collection-framework-phan-1-gioi-thieu-chung/ http://o7planning.org/vi/10165/huong-dan-su-dung-nen-tang-tap-hop-trong-java#a12326
All rights reserved
Bình luận