Please enable JavaScript.
Coggle requires JavaScript to display documents.
Sơ Đồ Tư Duy Tuần 3(Module 2)(1), Set, List, Queue, HashMap, HashTable,…
Sơ Đồ Tư Duy Tuần 3(Module 2)(1)
DSA: Danh sách
Java Collection Framework
Là khuôn khổ cung cấp một kiến trúc để lưu trữ và thao tác với nhóm các đối tượng.
Interface Collection:
List (Interface): Là cấu trúc dữ liệu tuyến tính, trong đó các phần được sắp xếp theo thứ tự xác định. Nó cho phép các phần tử được trùng lặp.
Queue: Hàng đợi hoạt động theo cơ chế FIFO(first in first out).
set: Mỗi phần tử xuất hiện 1 lần duy nhất. Tập hợp chưa được sắp xếp.
ArrayList
Là 1 class dạng list dựa trên mảng có kích thước thay đổi được
Array
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ờ cơ chế auto-boxing)
Có nhiều phương thức
Chậm hơn
Kích thước cố định
Có thể lưu trữu kiểu nguyên thủy và đối tượng
Chỉ có thuộc tính length
Tốc độ lưu trữ thao tác nhanh hơn
LinkedList
ArraykedList
Array
Sử dụng mảng động để lưu trữ các phần tử
Truy xuất ngẫu nhiên phần tử nhanh hơn
Thêm, xóa phần tử chậm hơn
Sử dụng danh sách liên kết đôi để lưu các phần tử.
Truy suất ngẫu nhiên chậm hơn
Thêm, xóa phần tử nhanh hơn
Set
hashset
các phần tử được lưu dưới dạng mã băm, nó sẽ không duy trì thứ tự chèn
LinkedHashset
Các phần tử 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ứ tự chèn
TreeSet
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
Java Collection Framework
Generic là gì? và ưu nhược điểm
Generic là cơ chế cho phép sử dụng kiểu dữ liệu như là tham số(tham số hóa kiểu dữ liệu)
Ưu điểm:
Phát hiện lỗi ngay tại thời điểm biên dịch
Không cần ép kiểu dữ liệu
Xây dựng các thuật toán tổng quát, tái sử dụng mã nguồn
Một số hạn chế của Generic:
Không thể gọi Generic với kiểu nguyên thủy
Không dùng static cho generics
Không thể tạo instansce kiểu generics
Không tạo class ngoại lệ generic
...
Stack là gì? Các phương thức làm việc với Stack
Stack - ngăn xếp là một cấu trúc dữ liệu dạng danh sách, thêm và lấy phần tử theo quy tắt FILO(First - in/ First - out)
Một số phương thức:
Thêm: push()
Lấy ra xem: peek()
Lấy ra xem và xóa: pop()
Kiễm tra rỗng: empty(),Empty()
Tìm kiếm: searsch
Queue là gì? Các phương làm việc với Queue?
Queue - Hàng đợi là một cấu trúc dữ liệu danh sách, thêm và lấy phần tử theo quy tắt FIFO(First in/First)
Có 3 lớp triển khai báo của Queue:
LinkedList, Frionrity Queue, Array Deque
Các phương thức:
add(): Thêm mới thành công thì mới trả về true, thất bại thì nếm ra ngoại lệ
ofter(): Thêm mới thành công thì trả về true, thất bại trả về false
element(): Lấy phần tử ở đầu hàng đợi, ném ngoại lệ hàng đợi bị rỗng
remove(): Xóa phần tử hàng đợi, ném ngoại lệ nếu hàng đợi rỗng
Map là gì? Đặc điểm của Map?
Sử dụng để lưu trữ và truy xuất theo cặp khóa (key) và giá trị(value)
Mỗi cặp key-value gọi entry
Map không cho phép 2 key trùng nhau
Mỗi key tương ứng là một key value
HashMap
Giống Map
Điểm khác nhau so với map
Không đảm bảo thứ tự entry được thêm vào
Cho phép một key null
Cho phép value có thể null
LinkedHashMap
Giống với HashMap
Điểm khác:
Duy trì các phần tử entry theo thứ tự chèn vào
TreeMap
Giống với Map
Điểm khác:
Không cho key có giá trị null
Duy trì các phần tử được thêm vào theo thứ tự được sắp xếp
(Mặc định sắp xếp tăng dần)
Lưu ý: Với key là kiểu Object do người dùng tự định nghĩa thì cần phải triển khai interface Comparable hoặc Comparator
Search Algorithm
Binary Search
Brinary Search tree(cây tìm kiếm nhị phân) mỗi cây sẽ có 0,1 hoặc tối đa 2 cây con
Giá trị cả node ở cây con bên trái < giá trị của node gốc
Giá trị cả node gốc < giá trị của tất cả các node ở cây con bên phải
Yêu cầu: Tập hợp được sắp xếp tăng(hoặc giảm)ý tưởng:
So sánh các phần tử cần tìm với phần tử giữa ở mảng
Nếu trả tìm thấy thì 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 ở mảng con bên trái của phần tử giữa.
Lặp lại bước 1
Độ phức tạp
Tối ưu O(1)
Tệ nhất O(log n)
Độ phức tạp thuật toán
Độ phức tạp thuật toán được hiểu là thời gian để thực hiện số 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
n có thể là số phần tử của mảng
Linear Search
Ý 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 thì trả về index của nó
Độ phức tạp
Trường hợp tối ưu: O(1)
Trường hợp tệ nhất O(n)-n là số lượng phần tử của tập hợp!
Thường áp dụng với các bài toán/tập hợp có số lượng phần tử nhỏ và chưa sắp xếp
Set
HashSet
LinkedList
TreeSet
List
Vector
Stack
LinkedList
ArrayList
Queue
PriorityQueue
Collection
Iterable
Deque
HashMap
HashTable
LinkedList
ArrayDeque
TreeMap
SortedMap
Map
:left_right_arrow:
Interface
:arrow_right:
Class
Extends
Implement