Mẹo sử dụng bộ sưu tập

1. Danh sách các bộ sưu tập

Như bạn có thể nhớ, Java có các bộ sưu tập — một công cụ hữu ích để lưu trữ các đối tượng cùng loại.

Hãy thử nhớ lại các giao diện chính liên quan đến bộ sưu tập:

Danh sách , Tập hợp , Bản đồ và Hàng đợi .

Như thường lệ, các công cụ không nhất thiết là tốt hay xấu — điều quan trọng là bạn có đang sử dụng chúng cho mục đích đã định hay không. Và để làm được điều đó, chúng ta phải tìm hiểu kỹ các tính năng cụ thể của chúng để biết nên sử dụng bộ sưu tập nào và khi nào.

1. Liệt kê

Hãy bắt đầu với bộ sưu tập được sử dụng nhiều nhất.

Liệt kê càng gần càng tốt với một mảng cũ đơn giản.

Bộ sưu tập này cho phép chúng ta lưu trữ một danh sách các đối tượng cùng loại một cách thuận tiện mà không phải lo lắng về kích thước của chính bộ sưu tập đó, như chúng ta sẽ phải làm nếu sử dụng một mảng. Các phần tử của bộ sưu tập được truy cập bằng chỉ mục. Nếu chúng ta biết chính xác vị trí của một đối tượng và cần truy cập nó thường xuyên mà không cần phải thêm hoặc xóa các phần tử thường xuyên, thì Danh sách là lý tưởng.

2 bộ

Set có cấu trúc hoàn toàn khác.

Bộ phù hợp nhất khi chúng ta cần lưu trữ các đối tượng độc đáo. Ví dụ: một nhóm tác giả trong thư viện mà mỗi tác giả là duy nhất. Nhưng chúng ta không thể đi và lấy bất kỳ tác giả cụ thể nào từ nó. Set cho phép chúng tôi nhanh chóng kiểm tra xem một tác giả cụ thể có trong thư viện của chúng tôi hay không, tức là chúng tôi có thể kiểm tra xem một đối tượng duy nhất có trong Set hay không . Chúng tôi cũng có thể lặp lại toàn bộ bộ sưu tập, truy cập từng phần tử, nhưng làm điều đó không phải là tối ưu.

Nói cách khác, đối với thư viện của chúng tôi, một Tập hợp có thể đại diện cho bộ sưu tập của tất cả các tác giả duy nhất để nhanh chóng kiểm tra xem có tác giả cụ thể nào không.

3. Bản đồ

Bản đồ giống như một tủ hồ sơ, trong đó mỗi tệp được ký và có thể lưu trữ các đối tượng riêng lẻ hoặc toàn bộ cấu trúc. Bản đồ nên được sử dụng trong trường hợp chúng ta cần duy trì ánh xạ từ giá trị này sang giá trị khác.

Đối với Bản đồ , các mối quan hệ này được gọi là cặp khóa-giá trị.

Chúng ta có thể sử dụng cấu trúc này trong thư viện của mình bằng cách sử dụng các đối tượng tác giả làm khóa và danh sách ( List đối tượng) sách làm giá trị. Do đó, sau khi kiểm tra Set để xem đối tượng tác giả có tồn tại trong thư viện hay không, chúng ta có thể sử dụng cùng một đối tượng tác giả để lấy Danh sách sách của họ từ Bản đồ .

4. Xếp hàng

Hàng đợi là một bộ sưu tập — bất ngờ! - thực hiện hành vi của một hàng đợi. Và hàng đợi có thể là LIFO (Last In, First Out) hoặc FIFO (First In, First Out). Hơn nữa, hàng đợi có thể là hai chiều hoặc "kết thúc kép".

Cấu trúc này rất hữu ích khi các đối tượng được thêm vào lớp cần được sử dụng theo thứ tự chúng được nhận. Ví dụ, lấy thư viện của chúng tôi.

Chúng tôi có thể thêm khách truy cập mới đến vào Hàng đợi và lần lượt phục vụ họ, phát sách cho họ.

Như chúng ta có thể thấy, mỗi cấu trúc này đều tốt nếu được sử dụng đúng mục đích. Và chúng tôi đã tìm thấy những cách sử dụng tốt cho cả bốn loại bộ sưu tập trong một ví dụ về thư viện.

2. Độ phức tạp

Như đã lưu ý, các bộ sưu tập mà chúng tôi đã xem xét ở trên là các giao diện, có nghĩa là chúng phải có các triển khai để chúng tôi sử dụng chúng.

Giống như việc đóng đinh bằng kính hiển vi không phải là ý tưởng hay nhất, không phải mọi cách triển khai bộ sưu tập đều phù hợp với mọi tình huống.

Khi chọn công cụ phù hợp cho công việc, chúng tôi thường xem xét 2 đặc điểm:

• Công cụ phù hợp với công việc như thế nào?
• Nó sẽ hoàn thành công việc nhanh như thế nào?

Chúng tôi đã dành thời gian tìm hiểu cách chọn một công cụ phù hợp cho công việc, nhưng tốc độ của nó là một điều mới mẻ.

Trong điện toán, tốc độ của một công cụ thường được biểu thị bằng độ phức tạp của thời gian và được biểu thị bằng chữ in hoa O.

Điều gì trên thế giới là thời gian phức tạp?

Nói một cách đơn giản, độ phức tạp của thời gian biểu thị thời gian cần thiết để thuật toán trong tập hợp thực hiện một hành động cụ thể (thêm/bớt phần tử, tìm kiếm phần tử).

ArrayList so với LinkedList

Hãy xem xét điều này bằng cách sử dụng hai triển khai của giao diện Danh sách — ArrayList và LinkedList .

Đối với hình thức bên ngoài, làm việc với các bộ sưu tập này cũng tương tự:

List<String> arrayList = new ArrayList<>();
arrayList.add(String);
arrayList.get(index);
arrayList.remove(index);
arrayList.remove(String);
 
List<String> linkedList = new LinkedList<>();
 
linkedList.add(String);
 
linkedList.get(index);
linkedList.remove(index);
linkedList.remove(String);
    

Như bạn có thể thấy, đối với cả hai loại bộ sưu tập, việc thêm, nhận và xóa các phần tử trông giống nhau. Điều này là do đây là những triển khai trên cùng một giao diện. Nhưng đó là nơi những điểm tương đồng kết thúc.

Do cách triển khai giao diện Danh sách khác nhau , hai cấu trúc này thực hiện các hành động khác nhau hiệu quả hơn các cấu trúc khác.

Xem xét loại bỏ và thêm một yếu tố.

Nếu chúng ta cần xóa một phần tử ở giữa ArrayList , chúng ta phải ghi đè lên bất kỳ phần nào của danh sách theo sau phần tử mà chúng ta xóa.

Giả sử chúng ta có một danh sách gồm 5 phần tử và chúng ta muốn xóa phần tử thứ 3.

List<Integer> list = Arrays.asList(1, 2, 3, 4, 5);
list.remove(2);
    

Trong trường hợp này, việc loại bỏ sẽ giải phóng một ô, vì vậy chúng ta cần viết phần tử thứ 4 vào vị trí của phần tử thứ 3 và phần tử thứ 5 vào vị trí thứ 4.

Điều này rất kém hiệu quả.

Điều tương tự cũng xảy ra khi thêm một phần tử vào giữa danh sách.

LinkedList được cấu trúc khác nhau. Việc thêm hoặc xóa phần tử diễn ra nhanh chóng vì chúng ta chỉ cần thay đổi các tham chiếu trong phần tử trước và phần tử tiếp theo, do đó loại trừ đối tượng mà chúng ta đang xóa khỏi chuỗi phần tử.

Trở lại với ví dụ về cùng một danh sách 5 phần tử, sau khi loại bỏ phần tử thứ 3, việc chúng ta cần làm chỉ là thay đổi tham chiếu của phần tử thứ 2 thành phần tử tiếp theo và tham chiếu của phần tử thứ 4 thành phần tử trước đó.

Khi một phần tử được thêm vào danh sách, quy trình tương tự sẽ xảy ra nhưng ngược lại.

Lưu ý rằng chúng ta cần làm ít công việc hơn trong LinkedList so với ArrayList . Và đó mới chỉ là 5 yếu tố. Nếu danh sách của chúng ta có từ 100 phần tử trở lên thì tính ưu việt của LinkedList càng được chú ý.

Nhưng tình huống sẽ thay đổi như thế nào nếu chúng ta truy cập một phần tử theo chỉ mục?

Mọi thứ hoàn toàn ngược lại ở đây.

Vì ArrayList được cấu trúc như một mảng thông thường, nên việc lấy bất kỳ phần tử nào theo chỉ mục của nó sẽ rất dễ dàng đối với chúng tôi. Chúng ta chỉ cần di chuyển con trỏ đến một vị trí nhất định và lấy phần tử từ ô tương ứng.

Nhưng một LinkedList đơn giản là không hoạt động theo cách đó. Chúng ta phải duyệt qua tất cả các phần tử của danh sách để tìm phần tử có chỉ số nhất định.

Chúng ta sẽ cố gắng diễn đạt tất cả những điều này dưới dạng chữ O lớn chứ?

Hãy bắt đầu bằng cách truy cập một phần tử theo chỉ mục.

Trong một ArrayList , điều này xảy ra trong một bước, bất kể phần tử nằm ở đâu trong danh sách. Dù ở cuối hay ở đầu.

Trong trường hợp này, độ phức tạp thời gian sẽ là O(1) .

Trong một LinkedList , chúng ta phải lặp lại một số phần tử bằng với giá trị của chỉ mục mà chúng ta cần.

Độ phức tạp về thời gian cho một hành động như vậy là O(n) , trong đó n là chỉ mục của phần tử chúng ta cần.

Ở đây bạn thấy rằng số chúng tôi đặt trong dấu ngoặc đơn chữ O lớn tương ứng với số lượng hành động được thực hiện.

Vỏ chúng tôi quay lại loại bỏ và thêm?

Hãy bắt đầu với LinkedList.

Bởi vì chúng ta không cần thực hiện một số lượng lớn các thao tác để thêm hoặc xóa một phần tử và tốc độ của thao tác này không phụ thuộc vào vị trí của phần tử, nên độ phức tạp của nó được biểu thị bằng O(1) và được cho là để được không đổi.

Độ phức tạp về thời gian của thao tác này đối với ArrayList cũng là O(n) , mà chúng tôi gọi là độ phức tạp tuyến tính.

Trong các thuật toán có độ phức tạp tuyến tính, thời gian chạy phụ thuộc trực tiếp vào số phần tử cần xử lý. Nó cũng có thể phụ thuộc vào vị trí của phần tử, cho dù nó ở đầu danh sách hay ở cuối danh sách.

Độ phức tạp thời gian cũng có thể là logarit. Điều này được thể hiện dưới dạng O(log n) .

Ví dụ, hãy xem xét một TreeSet được sắp xếp bao gồm 10 số. Chúng tôi muốn tìm số 2.

Vì danh sách đã được sắp xếp và không chứa phần trùng lặp, nên chúng ta có thể chia nó thành hai nửa và kiểm tra xem nửa nào sẽ chứa số mong muốn, loại bỏ phần không liên quan và sau đó lặp lại quy trình này cho đến khi chúng ta đạt được phần tử mong muốn. Cuối cùng, chúng ta sẽ tìm thấy (hoặc không tìm thấy) số sau khi xử lý log(n) số phần tử.

Đây là bảng tóm tắt độ phức tạp về thời gian của các bộ sưu tập còn lại.

Bây giờ chúng ta có một bảng hiển thị độ phức tạp về thời gian của các bộ sưu tập phổ biến, chúng ta có thể trả lời câu hỏi tại sao, trong số rất nhiều bộ sưu tập, chúng ta thường sử dụng ArrayList , HashSet và HashMap nhất .

Đơn giản là chúng hoạt động hiệu quả nhất cho hầu hết các tác vụ :)