Sự khởi đầu của con đường
Hôm nay tôi muốn nói về một chủ đề thú vị như “
Khung công tác bộ sưu tập Java ” hay nói một cách đơn giản là về các bộ sưu tập. Hầu hết công việc của mã là xử lý dữ liệu ở dạng này hay dạng khác. Lấy danh sách người dùng, lấy danh sách địa chỉ, v.v. Bằng cách nào đó sắp xếp chúng, thực hiện tìm kiếm, so sánh chúng. Đây là lý do tại sao kiến thức về bộ sưu tập được coi là kỹ năng cốt lõi. Đó là lý do tại sao tôi muốn nói về nó. Ngoài ra, một trong những câu hỏi phổ biến nhất trong các cuộc phỏng vấn nhà phát triển Java là các bộ sưu tập. Ví dụ: "vẽ phân cấp các bộ sưu tập." Trình biên dịch trực tuyến sẽ giúp chúng tôi trên con đường của mình. Ví dụ: bạn có thể sử dụng "
Trình biên dịch Java trực tuyến Tutorialspoint " hoặc
Repl.it. Con đường tìm hiểu bất kỳ cấu trúc dữ liệu nào đều bắt đầu bằng các biến thông thường (Biến). Trên trang web của Oracle, nhiều chủ đề khác nhau được thể hiện dưới dạng "đường dẫn" hoặc Đường mòn. Vì vậy, con đường làm quen với Java có tên là “
Con đường: Học ngôn ngữ Java: Mục lục ”. Và những điều cơ bản về ngôn ngữ (tức là Kiến thức cơ bản về ngôn ngữ) bắt đầu bằng Biến. Vì vậy, hãy viết một mã đơn giản:
public static void main(String[] args) {
String user = "Max";
System.out.println("Hello, " + user);
}
Nó tốt về mọi mặt, ngoại trừ việc chúng tôi hiểu rằng mã này chỉ tốt và đẹp cho một biến. Phải làm gì nếu có một vài trong số họ? Mảng được phát minh để lưu trữ dữ liệu thuộc một loại. Trong cùng một Đường mòn của Oracle có một phần riêng dành riêng cho mảng. Phần này được gọi là: "
Mảng ". Làm việc với mảng cũng khá đơn giản:
import java.util.Arrays;
class Main {
public static void main(String[] args) {
String[] users = new String[2];
users[0] = "Max";
users[1] = "John";
System.out.println("Hello, " + Arrays.toString(users));
}
}
Mảng giải quyết vấn đề lưu trữ nhiều giá trị ở một nơi. Nhưng nó đặt ra một hạn chế: kích thước mảng không đổi. Như trong ví dụ, nếu chúng ta nói kích thước = 2 thì nó bằng hai. Đó là tất cả. Nếu chúng ta muốn một mảng lớn hơn, chúng ta cần tạo một thể hiện mới. Ngoài ra, việc tìm kiếm một phần tử cũng là một điều khó khăn đối với một mảng. Có một phương thức
Arrays.binarySearch
, nhưng tìm kiếm này chỉ hoạt động trên một mảng đã được sắp xếp (đối với một mảng chưa được sắp xếp, kết quả là không xác định hoặc đơn giản là không thể đoán trước được). Nghĩa là, việc tìm kiếm sẽ bắt buộc chúng ta phải sắp xếp mỗi lần. Xóa cũng chỉ xóa giá trị. Vì vậy, chúng ta vẫn chưa biết thực sự có bao nhiêu dữ liệu trong mảng mà chỉ biết mảng đó có bao nhiêu ô. Để làm mới kiến thức của bạn về mảng:
Và do sự phát triển của ngôn ngữ Java, Khung công tác bộ sưu tập Java đã xuất hiện trong JDK 1.2 mà chúng ta sẽ nói đến hôm nay.
Bộ sưu tập
Bắt đầu tính giá ngay từ đầu. Tại sao Bộ sưu tập? Bản thân thuật ngữ này xuất phát từ những thứ như “Lý thuyết loại” và “Các loại dữ liệu trừu tượng”. Nhưng nếu không nhìn vào vấn đề cao siêu nào, thì khi chúng ta có nhiều thứ, chúng ta có thể gọi chúng là “bộ sưu tập đồ vật”. Những người thu thập vật phẩm. Nói chung, từ thu thập có nguồn gốc từ tiếng Lat. sưu tầm "thu thập, thu thập." Nghĩa là, một bộ sưu tập là một tập hợp của một cái gì đó, là nơi chứa một số phần tử. Vì vậy, chúng tôi có một tập hợp các yếu tố. Những gì chúng ta có thể muốn làm với nó:
Như bạn có thể thấy, chúng ta có thể muốn những thứ khá hợp lý. Chúng tôi cũng hiểu rằng chúng tôi có thể muốn làm điều gì đó với nhiều bộ sưu tập:
Theo đó, các nhà phát triển Java đã viết giao diện java.util.Collection để mô tả hành vi chung này cho tất cả các bộ sưu tập . Giao diện Bộ sưu tập là nơi bắt nguồn của tất cả các bộ sưu tập. Bộ sưu tập là một ý tưởng, đó là ý tưởng về cách tất cả các bộ sưu tập sẽ hoạt động. Do đó, thuật ngữ "Bộ sưu tập" được thể hiện dưới dạng giao diện. Đương nhiên, một giao diện cần được triển khai. Giao diện
java.util.Collection
có một lớp trừu tượng
AbstractCollection
, tức là một số "bộ sưu tập trừu tượng", đại diện cho khung cho các triển khai khác (như được viết trong JavaDoc phía trên lớp
java.util.AbstractCollection
). Nói về các bộ sưu tập, hãy quay lại và nhớ rằng chúng ta muốn lặp lại chúng. Điều này có nghĩa là chúng ta muốn lặp qua từng phần tử một. Đây là một khái niệm rất quan trọng. Do đó, giao diện
Collection
được kế thừa từ
Iterable
. Điều này rất quan trọng vì... trước tiên, mọi thứ Iterable phải có khả năng trả về Iterator dựa trên nội dung của nó. Và thứ hai, mọi thứ Iterable đều có thể được sử dụng trong các vòng lặp
for-each-loop
. Và với sự trợ giúp của một trình lặp
AbstractCollection
mà các phương thức như
contains
,
toArray
, được thực hiện
remove
. Và con đường tìm hiểu các bộ sưu tập bắt đầu bằng một trong những cấu trúc dữ liệu phổ biến nhất - danh sách, tức là.
List
.
Danh sách
Vì vậy, danh sách chiếm một vị trí quan trọng trong hệ thống phân cấp của các bộ sưu tập:
Như chúng ta có thể thấy, các danh sách triển khai giao diện
java.util.List . Danh sách thể hiện rằng chúng ta có một tập hợp các phần tử được sắp xếp theo trình tự nào đó. Mỗi phần tử có một chỉ mục (như trong một mảng). Thông thường, một danh sách cho phép bạn có các phần tử có cùng giá trị. Như chúng tôi đã nói ở trên,
List
nó biết về chỉ mục của phần tử. Điều này cho phép bạn lấy (
get
) một phần tử theo chỉ mục hoặc đặt giá trị cho một chỉ mục cụ thể (
set
). Các phương thức thu thập
add
,
addAll
,
remove
cho phép bạn chỉ định chỉ mục để thực thi chúng. Ngoài ra, y
List
có phiên bản lặp riêng của nó được gọi là
ListIterator
. Trình lặp này biết về chỉ mục của phần tử, vì vậy nó có thể lặp không chỉ tiến mà còn lặp lại. Nó thậm chí có thể được tạo từ một vị trí cụ thể trong bộ sưu tập. Trong số tất cả các cách triển khai, có hai cách được sử dụng phổ biến nhất:
ArrayList
và
LinkedList
. Đầu tiên,
ArrayList
đó là một danh sách (
List
) dựa trên một mảng (
Array
). Điều này cho phép bạn đạt được "Truy cập ngẫu nhiên"
vào các phần tử. Truy cập ngẫu nhiên là khả năng truy xuất ngay một phần tử theo chỉ mục, thay vì lặp qua tất cả các phần tử cho đến khi chúng ta tìm thấy phần tử có chỉ mục mong muốn. Chính mảng làm cơ sở cho phép đạt được điều này. Ngược lại,
LinkedList
nó là Danh sách liên kết. Mỗi mục trong danh sách liên kết được biểu thị dưới dạng
Entry
, biểu mẫu này lưu trữ dữ liệu cũng như liên kết tới mục tiếp theo (tiếp theo) và trước đó (trước đó)
Entry
. Do đó
LinkedList
thực hiện "Truy cập tuần tự
" . Rõ ràng để tìm phần tử thứ 5 chúng ta sẽ phải đi từ phần tử đầu tiên đến phần tử cuối cùng, bởi vì chúng tôi không có quyền truy cập trực tiếp vào phần tử thứ năm. Chúng ta chỉ có thể truy cập nó từ phần tử thứ 4. Sự khác biệt trong khái niệm của họ được đưa ra dưới đây:
Trong công việc, như bạn hiểu, cũng có sự khác biệt. Ví dụ: thêm các phần tử. Các
LinkedList
phần tử được kết nối đơn giản như những mắt xích trong một chuỗi. Nhưng
ArrayList
nó lưu trữ các phần tử trong một mảng. Và một mảng, như chúng ta biết, không thể thay đổi kích thước của nó. Sau đó nó hoạt động như thế nào
ArrayList
? Và nó hoạt động rất đơn giản. Khi hết dung lượng trong mảng, nó sẽ tăng lên 1,5 lần. Đây là mã thu phóng:
int newCapacity = oldCapacity + (oldCapacity >> 1);
Một điểm khác biệt trong hoạt động là bất kỳ sự dịch chuyển nào của các phần tử. Ví dụ: khi thêm hoặc xóa các phần tử ở giữa. Để xóa khỏi
LinkedList
một phần tử, chỉ cần xóa các tham chiếu đến phần tử này. Trong trường hợp ,
ArrayList
chúng tôi buộc phải dịch chuyển các phần tử mỗi lần sử dụng
System.arraycopy
. Vì vậy, càng nhiều yếu tố thì càng phải thực hiện nhiều hành động. Một mô tả chi tiết hơn có thể được tìm thấy trong các bài viết này:
Sau khi xem xét ArrayList, người ta không thể không nhớ đến “người tiền nhiệm” của nó, lớp
java.util.Vector . Nó khác
Vector
ở
ArrayList
chỗ các phương thức làm việc với bộ sưu tập (thêm, xóa, v.v.) được đồng bộ hóa. Nghĩa là, nếu một luồng (
Thread
) thêm các phần tử thì các luồng khác sẽ đợi cho đến khi luồng đầu tiên hoàn thành công việc của nó. Vì sự an toàn của luồng thường không được yêu cầu nên nên sử dụng lớp này trong những trường hợp như vậy
ArrayList
, như được nêu rõ ràng trong JavaDoc cho lớp đó
Vector
. Ngoài ra,
Vector
nó tăng kích thước không phải gấp 1,5 lần
ArrayList
mà là gấp 2 lần. Mặt khác, hoạt động vẫn giống nhau -
Vector
việc lưu trữ các phần tử ở dạng mảng bị ẩn và việc thêm/xóa các phần tử sẽ gây ra hậu quả tương tự như trong
ArrayList
. Trên thực tế,
Vector
chúng tôi nhớ điều này là có lý do. Nếu nhìn vào Javadoc, chúng ta sẽ thấy trong "Các lớp con được biết trực tiếp" có cấu trúc như
java.util.Stack . Ngăn xếp là một cấu trúc thú vị là
last-in-first-out
cấu trúc LIFO (cuối cùng vào, ra trước). Stack dịch từ tiếng Anh là một chồng (như chồng sách chẳng hạn). Ngăn xếp thực hiện các phương thức bổ sung:
peek
(nhìn, nhìn),
pop
(đẩy),
push
(đẩy). Phương pháp này
peek
được dịch là nhìn (ví dụ,
nhìn trộm bên trong túi được dịch là “
nhìn vào bên trong túi ”, và
nhìn trộm qua lỗ khóa được dịch là “
nhìn qua lỗ khóa ”). Phương pháp này cho phép bạn nhìn vào “đỉnh” của ngăn xếp, tức là lấy phần tử cuối cùng mà không xóa (tức là không xóa) nó khỏi ngăn xếp. Phương thức
push
đẩy (thêm) một phần tử mới vào ngăn xếp và trả về nó, còn phương thức phần tử
pop
sẽ đẩy (xóa) và trả về phần tử đã bị xóa. Trong cả ba trường hợp (tức là nhìn trộm, bật và đẩy), chúng tôi chỉ làm việc với phần tử cuối cùng (tức là “đỉnh của ngăn xếp”). Đây là tính năng chính của cấu trúc ngăn xếp. Nhân tiện, có một nhiệm vụ thú vị là tìm hiểu về ngăn xếp, được mô tả trong cuốn sách “Sự nghiệp của lập trình viên” (Phỏng vấn bẻ khóa mã hóa). Có một nhiệm vụ thú vị là sử dụng cấu trúc “ngăn xếp” (LIFO) bạn cần triển khai “hàng đợi”. “cấu trúc (FIFO). Nó sẽ giống như thế này:
Bạn có thể tìm thấy phân tích về nhiệm vụ này tại đây: "
Triển khai hàng đợi bằng cách sử dụng ngăn xếp - ADT hàng đợi ("Triển khai hàng đợi bằng cách sử dụng ngăn xếp" trên LeetCode) ". Vì vậy, chúng tôi chuyển sang cấu trúc dữ liệu mới - hàng đợi một cách suôn sẻ.
Xếp hàng
Hàng đợi là một cấu trúc quen thuộc với chúng ta trong cuộc sống. Xếp hàng đến cửa hàng, tới bác sĩ. Ai đến trước (First In) sẽ là người ra khỏi hàng trước (First Out). Trong Java, hàng đợi được biểu thị bằng giao diện
java.util.Queue . Theo Javadoc của hàng đợi, hàng đợi sẽ thêm các phương thức sau:
Như bạn có thể thấy, có các phương thức đặt hàng (không thực thi chúng sẽ có nhiều ngoại lệ) và có các phương thức yêu cầu (việc không thể thực thi chúng không dẫn đến lỗi). Cũng có thể lấy phần tử mà không cần xóa phần tử đó (xem nhanh hoặc phần tử). Giao diện hàng đợi cũng có một giao diện kế thừa hữu ích -
Deque . Đây được gọi là "hàng đợi hai chiều". Nghĩa là, hàng đợi như vậy cho phép bạn sử dụng cấu trúc này cả từ đầu và cuối. Tài liệu nói rằng "Deques cũng có thể được sử dụng làm ngăn xếp LIFO (Vào trước ra trước). Giao diện này nên được sử dụng ưu tiên hơn lớp Stack kế thừa.", tức là nên sử dụng triển khai Deque thay vì Cây rơm. Javadoc hiển thị các phương thức mà giao diện Deque mô tả:
Hãy xem có những triển khai nào. Và chúng ta sẽ thấy một sự thật thú vị - LinkedList đã được đưa vào trại xếp hàng) Nghĩa là, LinkedList triển khai cả
List
, và
Deque
. Nhưng cũng có những "chỉ hàng đợi", chẳng hạn
PriorityQueue
. Cô ấy không thường xuyên được nhớ đến, nhưng vô ích. Thứ nhất, bạn không thể sử dụng "đối tượng không thể so sánh" trong hàng đợi này, tức là. Bộ so sánh phải được chỉ định hoặc tất cả các đối tượng phải có thể so sánh được. Thứ hai, "việc triển khai này cung cấp thời gian O(log(n)) cho các phương thức xếp hàng và loại bỏ hàng đợi". Độ phức tạp logarit là có lý do. Đã triển khai PriorityQueue dựa trên vùng nhớ heap. Javadoc cho biết: "Hàng đợi ưu tiên được biểu thị dưới dạng đống nhị phân cân bằng." Bản thân việc lưu trữ này là một mảng thông thường. Mà phát triển khi cần thiết. Khi heap nhỏ, nó tăng gấp 2 lần. Và sau đó là 50%. Nhận xét từ mã: "Kích thước gấp đôi nếu nhỏ; nếu không thì tăng 50%". Hàng đợi ưu tiên và Heap nhị phân là một chủ đề riêng biệt. Vì vậy, để biết thêm thông tin:
Việc triển khai
java.util.Deque
có thể là lớp
java.util.ArrayDeque . Nghĩa là, danh sách có thể được triển khai bằng danh sách liên kết và mảng, đồng thời hàng đợi cũng có thể được triển khai bằng mảng hoặc danh sách liên kết. Các giao diện
Queue
và
Deque
có các giao diện con đại diện cho "hàng đợi chặn":
BlockingQueue
và
BlockingDeque
. Đây là sự thay đổi giao diện so với hàng đợi thông thường:
Hãy xem xét một số ví dụ về việc chặn hàng đợi. Nhưng chúng rất thú vị. Ví dụ: BlockingQueue được triển khai bởi:
PriorityBlockingQueue ,
SynchronousQueue , ArrayBlockingQueue,
DelayQueue ,
LinkedBlockingQueue . Nhưng
BlockingDeque
họ triển khai mọi thứ từ Khung sưu tập tiêu chuẩn
LinkedBlockingDeque
. Mỗi hàng đợi là chủ đề của một bài đánh giá riêng biệt. Và trong khuôn khổ bài đánh giá này, chúng tôi sẽ mô tả hệ thống phân cấp lớp không chỉ với
List
, mà còn với
Queue
:
Như chúng ta có thể thấy từ sơ đồ, các giao diện và lớp của Khung công tác bộ sưu tập Java có mối liên hệ chặt chẽ với nhau. Hãy thêm một nhánh khác của hệ thống phân cấp -
Set
.
Bộ
Set
- được dịch là “bộ.” Nó khác với hàng đợi và danh sách
Set
ở chỗ nó có tính trừu tượng cao hơn trong việc lưu trữ các phần tử.
Set
- giống như một cái túi đựng đồ vật, không biết đồ vật đó được đặt ở đâu và xếp theo thứ tự nào. Trong Java, tập hợp như vậy được biểu thị bằng giao diện
java.util.Set . Như tài liệu nói,
Set
đây là "bộ sưu tập không chứa các phần tử trùng lặp". Điều thú vị là bản thân giao diện
Set
không thêm các phương thức mới vào giao diện
Collection
mà chỉ làm rõ các yêu cầu (về những gì không được chứa trùng lặp). Ngoài ra, từ mô tả trước đó, bạn không thể đơn giản
Set
lấy một phần tử từ nó. Iterator được sử dụng để lấy các phần tử.
Set
có thêm một số giao diện liên quan đến nó. Điều thứ nhất là
SortedSet
. Như tên gợi ý,
SortedSet
nó chỉ ra rằng một tập hợp như vậy đã được sắp xếp và do đó các phần tử triển khai giao diện
Comparable
hoặc được chỉ định
Comparator
. Ngoài ra,
SortedSet
nó còn cung cấp một số phương pháp thú vị:
Ngoài ra, còn có các phương thức
first
(phần tử nhỏ nhất theo giá trị) và
last
(phần tử lớn nhất theo giá trị). Có
SortedSet
người thừa kế -
NavigableSet
. Mục đích của giao diện này là mô tả các phương pháp điều hướng cần thiết để xác định chính xác hơn các phần tử thích hợp. Một điều thú vị là
NavigableSet
nó thêm vào trình vòng lặp thông thường (đi từ nhỏ nhất đến lớn nhất) một trình vòng lặp theo thứ tự ngược lại -
descendingIterator
. Ngoài ra,
NavigableSet
nó cho phép bạn sử dụng phương pháp này
descendingSet
để có được chế độ xem về chính bạn (Chế độ xem), trong đó các phần tử theo thứ tự ngược lại. Điều này được gọi
View
là vì thông qua phần tử kết quả, bạn có thể thay đổi các phần tử của phần tử gốc
Set
. Về bản chất, đó là sự thể hiện dữ liệu gốc theo một cách khác chứ không phải là bản sao của dữ liệu gốc. Điều thú vị là
NavigableSet
, như
Queue
, có thể xử lý các phần tử
pollFirst
(tối thiểu) và
pollLast
(tối đa). Nghĩa là, nó lấy phần tử này và xóa nó khỏi tập hợp. Có những loại triển khai nào? Thứ nhất, cách triển khai nổi tiếng nhất dựa trên mã băm -
HashSet . Một triển khai nổi tiếng không kém khác dựa trên cây đỏ đen -
TreeSet . Hãy hoàn thành sơ đồ của chúng tôi:
Trong các bộ sưu tập, vẫn phải sắp xếp thứ bậc - những ẩn sĩ. Mà thoạt nhìn đã đứng sang một bên -
java.util.Map
.
Bản đồ
Bản đồ là một cấu trúc dữ liệu trong đó dữ liệu được lưu trữ theo khóa. Ví dụ: khóa có thể là ID hoặc mã thành phố. Và chính nhờ khóa này mà dữ liệu sẽ được tìm kiếm. Điều thú vị là các thẻ được hiển thị riêng biệt. Theo các nhà phát triển (xem "
Câu hỏi thường gặp về thiết kế API bộ sưu tập Java "), ánh xạ khóa-giá trị không phải là một bộ sưu tập. Và bản đồ có thể nhanh chóng được coi là một tập hợp các khóa, một tập hợp các giá trị, một tập hợp các cặp khóa-giá trị. Đây là một loài động vật thú vị. Thẻ cung cấp những phương pháp nào? Chúng ta hãy xem giao diện API Java
java.util.Map . Bởi vì Vì bản đồ không phải là bộ sưu tập (chúng không kế thừa từ Bộ sưu tập) nên chúng không chứa tệp
contains
. Và điều này là hợp lý. Một bản đồ bao gồm các khóa và giá trị. Phương pháp nào trong số này nên kiểm tra
contains
và làm thế nào để không bị nhầm lẫn? Vì vậy, giao diện
Map
có hai phiên bản khác nhau:
containsKey
(chứa khóa) và
containsValue
(chứa giá trị). Sử dụng nó
keySet
cho phép bạn nhận được một bộ chìa khóa (giống nhau
Set
). Và bằng cách sử dụng phương pháp này,
values
chúng ta có thể nhận được một tập hợp các giá trị trên bản đồ. Các khóa trong bản đồ là duy nhất, được nhấn mạnh bởi cấu trúc dữ liệu
Set
. Các giá trị có thể được lặp lại, điều này được nhấn mạnh bởi cấu trúc dữ liệu Bộ sưu tập. Ngoài ra, bằng cách sử dụng phương pháp này,
entrySet
chúng ta có thể thu được một tập hợp các cặp khóa-giá trị. Bạn có thể đọc thêm về cách triển khai thẻ trong các phân tích chi tiết nhất:
Tôi cũng muốn xem những gì
HashMap
rất giống với
HashSet
, và
TreeMap
với
TreeSet
. Chúng thậm chí còn có giao diện tương tự:
NavigableSet
và
NavigableMap
,
SortedSet
và
SortedMap
. Vì vậy, bản đồ cuối cùng của chúng ta sẽ trông như thế này:
Chúng ta có thể kết thúc với một thực tế thú vị là bộ sưu tập
Set
sử dụng nội bộ
Map
, trong đó các giá trị bổ sung là khóa và giá trị giống nhau ở mọi nơi. Điều này thật thú vị vì nó
Map
không phải là một bộ sưu tập và trả về
Set
, mà là một bộ sưu tập nhưng trên thực tế được triển khai dưới dạng
Map
. Hơi kỳ quái một chút, nhưng hóa ra là vậy)
Phần kết luận
Tin tốt là bài đánh giá này kết thúc ở đây. Tin xấu là đây là một bài viết rất đánh giá. Mỗi lần triển khai của mỗi bộ sưu tập đều xứng đáng có một bài viết riêng và cho từng thuật toán ẩn khỏi tầm mắt của chúng tôi. Nhưng mục đích của việc xem xét này là để ghi nhớ chúng là gì và mối liên hệ giữa các giao diện là gì. Tôi hy vọng rằng sau khi đọc kỹ, bạn sẽ có thể vẽ sơ đồ các bộ sưu tập từ trí nhớ.
Vâng, như thường lệ, một số liên kết:
#Viacheslav
GO TO FULL VERSION