Please enable JavaScript.
Coggle requires JavaScript to display documents.
Java Collection Framework - Coggle Diagram
Java Collection Framework
Là một khuôn khổ cung cấp một kiến trúc để lưu trữ và thao tác với nhóm đối tượng
ArrayList : là một class dạng list dựa trên mảng có kích thước thay đổi được
Các thao tác cơ bản : add(), get(), remove(), indexOf()
Sự khác nhau của ArrayList và Array
Array : Có kích thước ổn định , có thể lưu trử kiểu nguyên thủy và dối tượng , chỉ có thuộc tính length, tốc độ lưu trữ thao tác nhanh hơn
ArrayList: Kích thước có thể thay đổi được, chỉ lưu được kiểu đôi tượng (với kiểu nguyên thủy được tự động chuyển qua kiểu đối tượng nhờ chế độ auto-boxing), có nhiều phương thức, tốc dộ lưu trư chậm hơn
Sự khác nhau giữa ArrayList và LinkedList
ArrayList: Sử dụng mảng động lưu trữ phần tử, truy xuất ngẫu nhiên nhanh hơn, Thêm xóa phần tử chậm hơn
LinkedList: Sử dụng danh sách liên kết để lưu trữ các phần tử , truy xuất ngẫu nhiên chậm, thêm xóa phần tử nhanh hơn
Set
hashSet: các phần tử được lưu trữ dưới dạng mã băm , nó sẽ không duy trì thứ tự chèn
LinkedHashSet: Các phần tử được lưu dưới dạng mã băm, cấu trúc dữ liệu dạng danh sách liên kết, duy trì thứu tự chèn
Sử dụng 1 tree cho lưu trữ, mặc định các phân tử sẽ được sắp xếp tăng dần
Generic
Là cơ chế cho phép sử dụng kiểu dữ liệu như tham số (Tham số hóa kiểu dữ liệu) .
Ưu và nhược điểm
Ưu điểm : Phát hiên lỗi ngay tại thời điểm biên dịch,k yêu cầu ép kiểu dữ liệu, xây dựng các thuật toán , tái sử dụng mã nguồn
Nhược điểm : không thể gọi generic với kiểu dữ liẹu nguyên thủy , không thể tạo instance cho kiểu generic, không thể tạo mảng cho generic, không thể tạo class ngoại lệ là generic
Stack Và Queue
Stack
Ngăn xếp là một cấu trúc dữ liệu dang danh sách , thêm và lấy phần tử theo quy tắc FILO (Fisrt in last out)
Các phương thức thao tác với Stack
push(), peek(),pop(), enpty(), isEm[ty(), search()
Queue :
Hàng đợi là một cấu trúc dữ liệu danh sách, lấy phần tử bằng quy tắc FIFO (Fisrt in Fisrt out)
Có ba lớp triển khai của Queue : LinkedList, PeorityQueue, ArrayDequeue
Các phương thức
add(): thêm mới thành công thì trả về một true, thất bại thì tạo ra một ngoại lệ
Offer(): thêm mới thàn công thì tạo về một true, thất bại thì tạo ra một false
element(): lấy phần tử ở đầu hàng đợi , ném ngoại lệ nếu hàng đợi rỗng
remove(): xóa phần tử đầu hàng đợi, ném ngoại lệ nếu hàng đợi rỗng
poll(): lấy phần tử đầu hàng đợi và xóa nó đi , trả về null nếu hàng đợi rỗng
Map và tree
Map: sử dụng để lưu trữ và truy xuất theo cặp khóa key và value. Mỗi cặp key và value được gọi là entry
Map không cho phép 2 key trùng nhau, mỗi key tương ứng với một value
HashMap: Giống map
Điểm khác so với map : không đảm bảo thứ tự entry, cho phép một key null, cho phép nhiều value có thể null
TreeMap:
Không cho key giá trị null, duy trì các phần tử được thêm vào theo thứ tự key được sắp xếp tăng dần
LinkedHashMap: Giống Map
Điểm khác: Duy trì các phần tử - entry thứ tự chèn vào
Lưu ýL với key là kiểu Obj do người dùng tự định nghĩa thì cần triển khai lớp Comparable hoặc Comparator
Thuật toán tìm kiếm
Độ phức tạp thuật toán:
Được hiểu là thời gian để thực thi phép tính mà thuật toán cần để thực hiện với bộ dữ liệu đầu vào có kích thước n , với n là số phần tử mảng
LinerSearch
Ý tưởng : Mỗi phần tử đều được kiểm tra, nếu tìm thấy phần tử cần tìm, trả về index của nó. TH tối ưu O(1), TH tệ nhất O(n)[n là số lượng của tập]. Thường áp dụng với những bài toán hoặc tập hợp có số lượng phần tử nhỏ và chưa được sắp xếp
BinarySearch
Yêu cầu : mảng phải được sắp xếp tăng hoặc giảm
So sánh phần tử cần tìm ở giữa mảng, nếu tìm thấy trả về index, nếu phần tử cần tìm lớn hơn phần tử ở giữa thì phần tử cần tìm sẽ nằm ở mảng con bên phải của phần tử ở giữa, nếu phần tử cần tìm bé hơn phần tử ở giữa thì phần tử cần tìm sẽ nằm bên mảng con bên trái của phần tử giữa, bước cuối là lặp lại bước một. Tối ưu : O(1), Tệ nhất o(log_n)