Collection
Trang này chứa các mẹo và tài nguyên để chuẩn bị cho buổi phỏng vấn Collection.
Mô tả hệ thống phân cấp kiểu Collections. Các giao diện chính là gì và sự khác biệt giữa chúng là gì?
Hệ thống phân cấp kiểu Collections trong Java là một khung công cụ mạnh mẽ để làm việc với các nhóm đối tượng. Dưới đây là mô tả chi tiết:
1. Iterable Interface:
Đây là giao diện gốc của tất cả các collections.
Nó định nghĩa phương thức
iterator()để trả về mộtIteratorcho phép duyệt qua các phần tử của collection.Bất kỳ collection nào triển khai
Iterableđều có thể được sử dụng trong vòng lặp for-each.
2. Collection Interface:
Kế thừa từ
Iterable.Định nghĩa các phương thức chung để kiểm tra sự tồn tại của phần tử, thêm, xóa phần tử, xác định kích thước, v.v.
Các giao diện
List,SetvàQueuekế thừa từCollection.
3. List Interface:
Đại diện cho một collection có thứ tự (ordered collection).
Các phần tử có thể được truy cập bằng chỉ số (index) của chúng.
Cho phép các phần tử trùng lặp.
Ví dụ:
ArrayList,LinkedList.
4. Set Interface:
Đại diện cho một collection không có thứ tự (unordered collection) với các phần tử duy nhất (distinct elements).
Không cho phép các phần tử trùng lặp.
Ví dụ:
HashSet,TreeSet,LinkedHashSet.
5. Queue Interface:
Đại diện cho một collection được thiết kế để giữ các phần tử trước khi xử lý.
Cung cấp các phương thức bổ sung để thêm, xóa và kiểm tra các phần tử.
Thường được sử dụng để triển khai các cấu trúc dữ liệu FIFO (First-In-First-Out).
Ví dụ:
LinkedList,PriorityQueue.
6. Map Interface:
Là một phần của framework Collections, nhưng không kế thừa từ
Collection.Đại diện cho một cấu trúc dữ liệu key-value, trong đó các key là duy nhất và mỗi key có tối đa một value.
Sự khác biệt này là có chủ đích, để nhấn mạnh sự khác biệt giữa collections và mappings, vốn khó có thể gom chung dưới một sự trừu tượng chung.
Ví dụ:
HashMap,TreeMap,LinkedHashMap.
Tóm tắt sự khác biệt chính:
List: Thứ tự, cho phép trùng lặp, truy cập bằng chỉ số.
Set: Không thứ tự, không cho phép trùng lặp, các phần tử duy nhất.
Queue: Thứ tự (thường là FIFO), giữ các phần tử trước khi xử lý.
Map: Cấu trúc key-value, key duy nhất, value có thể trùng lặp.
Hệ thống phân cấp này cung cấp một bộ công cụ linh hoạt và mạnh mẽ để quản lý và thao tác dữ liệu trong Java.
Mô tả các triển khai khác nhau của interface Map và sự khác biệt về trường hợp sử dụng của chúng.
Interface Map trong Java cung cấp một cấu trúc dữ liệu để lưu trữ các cặp key-value. Dưới đây là các triển khai phổ biến và sự khác biệt về trường hợp sử dụng:
1. HashMap:
Mô tả:
Triển khai dựa trên bảng băm (hash table).
Cho phép truy cập các phần tử trong thời gian hằng số O(1) (trung bình).
Không duy trì thứ tự của các phần tử.
Không an toàn cho luồng (thread-safe).
Trường hợp sử dụng:
Khi hiệu suất truy cập nhanh là ưu tiên hàng đầu.
Khi thứ tự của các phần tử không quan trọng.
Trong các ứng dụng đơn luồng hoặc khi việc đồng bộ hóa được xử lý bên ngoài.
2. LinkedHashMap:
Mô tả:
Kế thừa từ
HashMap.Duy trì thứ tự chèn của các phần tử bằng cách sử dụng danh sách liên kết kép (doubly linked list).
Hiệu suất truy cập gần giống
HashMap, nhưng có thêm chi phí cho việc duy trì danh sách liên kết.
Trường hợp sử dụng:
Khi cần duy trì thứ tự chèn của các phần tử.
Trong các ứng dụng yêu cầu dự đoán thứ tự lặp lại (iteration order).
3. TreeMap:
Mô tả:
Lưu trữ các phần tử trong một cấu trúc cây đỏ-đen (red-black tree).
Cho phép truy cập các phần tử trong thời gian logarit O(log(n)).
Duy trì thứ tự của các phần tử theo một
Comparatorđược cung cấp hoặc theo thứ tự tự nhiên của các key.
Trường hợp sử dụng:
Khi cần duy trì thứ tự sắp xếp của các phần tử.
Trong các ứng dụng yêu cầu tìm kiếm theo phạm vi hoặc truy xuất các phần tử theo thứ tự.
4. ConcurrentHashMap:
Mô tả:
Triển khai bảng băm an toàn cho luồng (thread-safe).
Cung cấp tính đồng thời cao cho các thao tác đọc và ghi.
Các thao tác đọc không yêu cầu khóa (locking).
Các thao tác ghi được chia thành các phân đoạn (segments) để giảm thiểu xung đột.
Trường hợp sử dụng:
Trong các ứng dụng đa luồng yêu cầu hiệu suất cao và tính đồng thời.
Khi nhiều luồng cần truy cập và sửa đổi map đồng thời.
5. Hashtable:
Mô tả:
Là một triển khai bảng băm an toàn cho luồng (thread-safe) từ Java 1.0.
Hầu hết đã lỗi thời và được thay thế bởi
ConcurrentHashMap.Tất cả các phương thức đều được đồng bộ hóa (synchronized), dẫn đến hiệu suất thấp hơn so với
ConcurrentHashMap.
Trường hợp sử dụng:
Trong các ứng dụng cũ cần duy trì tính tương thích ngược.
Không nên sử dụng trong các ứng dụng mới.
Tóm tắt sự khác biệt:
HashMap: Nhanh, không có thứ tự, không an toàn cho luồng.
LinkedHashMap: Nhanh, duy trì thứ tự chèn, không an toàn cho luồng.
TreeMap: Sắp xếp theo thứ tự, truy cập logarit, không an toàn cho luồng.
ConcurrentHashMap: An toàn cho luồng, hiệu suất cao, đồng thời.
Hashtable: An toàn cho luồng, hiệu suất thấp, đã lỗi thời.
Giải thích sự khác biệt giữa LinkedList và ArrayList.
Cả ArrayList và LinkedList đều là các triển khai của interface List trong Java, nhưng chúng có các cấu trúc dữ liệu và đặc điểm hiệu suất khác nhau:
1. ArrayList:
Cấu trúc dữ liệu:
Dựa trên một mảng động (dynamic array).
Khi mảng đầy, nó sẽ tự động tăng kích thước.
Hiệu suất:
Truy cập phần tử theo chỉ số (index) có thời gian hằng số O(1).
Thêm hoặc xóa phần tử ở giữa hoặc đầu danh sách có thời gian tuyến tính O(n) vì cần phải dịch chuyển các phần tử sau đó.
Việc dịch chuyển các phần tử được tối ưu với
System.arraycopy()nên thực tế nhanh hơn nhiều so với dự tính.
Ưu điểm:
Truy cập ngẫu nhiên nhanh.
Sử dụng bộ nhớ hiệu quả hơn so với
LinkedList(ít overhead hơn).
Nhược điểm:
Thêm hoặc xóa phần tử ở giữa hoặc đầu danh sách chậm.
Việc resize mảng có thể tốn kém nếu mảng rất lớn.
2. LinkedList:
Cấu trúc dữ liệu:
Dựa trên danh sách liên kết kép (doubly-linked list).
Mỗi phần tử được lưu trữ trong một
Nodechứa tham chiếu đến phần tử trước và sau.
Hiệu suất:
Truy cập phần tử theo chỉ số có thời gian tuyến tính O(n).
Thêm hoặc xóa phần tử ở đầu hoặc cuối danh sách có thời gian hằng số O(1).
Thêm hoặc xóa phần tử ở giữa danh sách, cần tìm đến vị trí cần chèn hoặc xóa, nên cũng là O(n).
Ưu điểm:
Thêm hoặc xóa phần tử ở đầu hoặc cuối danh sách nhanh.
Thêm hoặc xóa phần tử ở giữa danh sách nhanh hơn ArrayList nếu biết vị trí cần chèn hoặc xóa.
Nhược điểm:
Truy cập ngẫu nhiên chậm.
Sử dụng bộ nhớ kém hiệu quả hơn do overhead của các đối tượng
Node.
Tóm tắt sự khác biệt chính:
Truy cập:
ArrayList: Nhanh (O(1)) cho truy cập ngẫu nhiên.LinkedList: Chậm (O(n)) cho truy cập ngẫu nhiên.
Thêm/Xóa:
ArrayList: Chậm (O(n)) cho thêm/xóa ở giữa hoặc đầu, nhanh ở cuối.LinkedList: Nhanh (O(1)) cho thêm/xóa ở đầu hoặc cuối, O(n) cho thêm xóa ở giữa, nếu không biết vị trí.
Bộ nhớ:
ArrayList: Sử dụng bộ nhớ hiệu quả hơn.LinkedList: Sử dụng bộ nhớ kém hiệu quả hơn.
Khi nào nên sử dụng:
ArrayList:
Khi truy cập ngẫu nhiên là quan trọng.
Khi thêm hoặc xóa phần tử chủ yếu ở cuối danh sách.
LinkedList:
Khi thêm hoặc xóa phần tử thường xuyên ở đầu hoặc cuối danh sách.
Khi cần thêm xóa ở giữa danh sách, và đã biết vị trí cần thêm hoặc xóa.
Trong hầu hết các trường hợp, ArrayList thường có hiệu suất tốt hơn LinkedList do việc truy cập ngẫu nhiên nhanh và việc tối ưu hoá của System.arraycopy() cho việc dịch chuyển các phần tử.
Sự khác biệt giữa HashSet và TreeSet là gì?
Cả lớp HashSet và TreeSet đều triển khai interface Set và đại diện cho tập hợp các phần tử riêng biệt. Ngoài ra, TreeSet còn triển khai interface NavigableSet. Interface này định nghĩa các phương thức tận dụng thứ tự sắp xếp của các phần tử.
HashSet được xây dựng dựa trên HashMap (bên trong), còn TreeSet được xây dựng dựa trên một đối tượng TreeMap, điều này định nghĩa các thuộc tính của chúng: HashSet không giữ các phần tử theo bất kỳ thứ tự cụ thể nào. Việc lặp qua các phần tử trong HashSet tạo ra chúng theo thứ tự xáo trộn. Ngược lại, TreeSet tạo ra các phần tử theo thứ tự dựa trên một Comparator được định nghĩa trước.
HashMap được triển khai như thế nào trong Java?
Lớp HashMap đại diện cho một cấu trúc dữ liệu hash map điển hình với một số lựa chọn thiết kế cụ thể.
HashMap được hỗ trợ bởi một mảng có thể thay đổi kích thước, với kích thước là lũy thừa của 2. Khi một phần tử được thêm vào HashMap, trước tiên hashCode của nó được tính toán (một giá trị kiểu int). Sau đó, một số bit thấp hơn của giá trị này được sử dụng làm chỉ số mảng. Chỉ số này trỏ trực tiếp đến ô của mảng (được gọi là "bucket" hoặc "thùng") nơi cặp key-value này nên được đặt. Việc truy cập một phần tử theo chỉ số của nó trong một mảng là một thao tác O(1) rất nhanh, đây là tính năng chính của cấu trúc hash map.
Tuy nhiên, hashCode không phải là duy nhất, và ngay cả đối với các hashCode khác nhau, chúng ta vẫn có thể nhận được cùng một vị trí mảng. Điều này được gọi là "collision" (xung đột). Có nhiều cách để giải quyết xung đột trong cấu trúc dữ liệu hash map. Trong HashMap của Java, mỗi bucket thực sự không trỏ đến một đối tượng đơn lẻ, mà trỏ đến một cây đỏ-đen chứa tất cả các đối tượng được đặt trong bucket này (trước Java 8, đây là một danh sách liên kết).
Vì vậy, khi HashMap đã xác định được bucket cho một key, nó phải duyệt qua cây này để đặt cặp key-value vào vị trí của nó. Nếu một cặp có key như vậy đã tồn tại trong bucket, nó sẽ được thay thế bằng cặp mới.
Để truy xuất đối tượng bằng key của nó, HashMap lại phải tính toán hashCode cho key, tìm bucket tương ứng, duyệt qua cây, gọi equals trên các key trong cây và tìm key phù hợp.
HashMap có độ phức tạp O(1), hoặc độ phức tạp thời gian không đổi, cho việc đặt và lấy các phần tử. Tất nhiên, nhiều xung đột có thể làm giảm hiệu suất xuống độ phức tạp thời gian O(log(n)) trong trường hợp xấu nhất, khi tất cả các phần tử được đặt trong một bucket duy nhất. Điều này thường được giải quyết bằng cách cung cấp một hàm hash tốt với phân phối đồng đều.
Khi mảng nội bộ của HashMap đầy (thêm thông tin về điều này trong câu hỏi tiếp theo), nó sẽ tự động được thay đổi kích thước để lớn gấp đôi. Thao tác này kéo theo việc "rehashing" (xây dựng lại cấu trúc dữ liệu nội bộ), rất tốn kém, vì vậy bạn nên lên kế hoạch kích thước của HashMap từ trước.
Mục đích của các tham số Initial Capacity (Dung lượng ban đầu) và Load Factor (Hệ số tải) của HashMap là gì?
Tham số initialCapacity của constructor HashMap ảnh hưởng đến kích thước của cấu trúc dữ liệu nội bộ của HashMap, nhưng việc suy luận về kích thước thực tế của một map có phần phức tạp. Cấu trúc dữ liệu nội bộ của HashMap là một mảng có kích thước là lũy thừa của 2. Vì vậy, giá trị của tham số initialCapacity được tăng lên lũy thừa của 2 tiếp theo (ví dụ: nếu bạn đặt nó thành 10, kích thước thực tế của mảng nội bộ sẽ là 16).
Hệ số tải (load factor) của HashMap là tỷ lệ giữa số lượng phần tử chia cho số lượng bucket (tức là kích thước mảng nội bộ). Ví dụ: nếu một HashMap 16 bucket chứa 12 phần tử, hệ số tải của nó là 12/16 = 0.75. Hệ số tải cao có nghĩa là có nhiều xung đột, điều này có nghĩa là map cần được thay đổi kích thước thành lũy thừa của 2 tiếp theo. Vì vậy, tham số loadFactor là giá trị tối đa của hệ số tải của một map. Khi map đạt được hệ số tải này, nó sẽ thay đổi kích thước mảng nội bộ của nó thành giá trị lũy thừa của 2 tiếp theo.
initialCapacity mặc định là 16 và loadFactor mặc định là 0.75, vì vậy bạn có thể đặt 12 phần tử vào một HashMap được khởi tạo với constructor mặc định và nó sẽ không thay đổi kích thước. Điều tương tự cũng áp dụng cho HashSet, được hỗ trợ bởi một instance HashMap bên trong.
Do đó, việc đưa ra initialCapacity đáp ứng nhu cầu của bạn không phải là điều đơn giản. Đây là lý do tại sao thư viện Guava có các phương thức Maps.newHashMapWithExpectedSize() và Sets.newHashSetWithExpectedSize() cho phép bạn xây dựng một HashMap hoặc HashSet có thể chứa số lượng phần tử dự kiến mà không cần thay đổi kích thước.
Mô tả các Collection đặc biệt cho Enums.
EnumSet và EnumMap là các triển khai đặc biệt của interface Set và Map tương ứng. Bạn nên luôn sử dụng các triển khai này khi làm việc với enums vì chúng rất hiệu quả.
EnumSet thực chất là một vector bit với các "bit 1" ở các vị trí tương ứng với giá trị thứ tự (ordinal value) của các enums có trong tập hợp. Để kiểm tra xem một giá trị enum có nằm trong tập hợp hay không, triển khai chỉ cần kiểm tra xem bit tương ứng trong vector có phải là "bit 1" hay không, đây là một thao tác rất đơn giản. Tương tự, EnumMap là một mảng được truy cập với giá trị thứ tự của enum làm chỉ số. Trong trường hợp của EnumMap, không cần phải tính toán mã hash hoặc giải quyết xung đột.
Sự khác biệt giữa Iterator Fail-Fast và Fail-Safe là gì?
Iterators (bộ lặp) cho các collection khác nhau có thể là fail-fast hoặc fail-safe, tùy thuộc vào cách chúng phản ứng với các sửa đổi đồng thời. Sửa đổi đồng thời không chỉ là sửa đổi collection từ một luồng khác mà còn là sửa đổi từ cùng một luồng nhưng sử dụng một iterator khác hoặc sửa đổi trực tiếp collection.
Iterators fail-fast (những iterator được trả về bởi HashMap, ArrayList và các collection không an toàn luồng khác) lặp qua cấu trúc dữ liệu nội bộ của collection và chúng ném ra ngoại lệ ConcurrentModificationException ngay khi phát hiện ra một sửa đổi đồng thời.
Iterators fail-safe (những iterator được trả về bởi các collection an toàn luồng như ConcurrentHashMap, CopyOnWriteArrayList) tạo ra một bản sao của cấu trúc mà chúng lặp qua. Chúng đảm bảo an toàn khỏi các sửa đổi đồng thời. Nhược điểm của chúng bao gồm tiêu thụ bộ nhớ quá mức và lặp qua dữ liệu có thể đã lỗi thời trong trường hợp collection bị sửa đổi.
Làm thế nào bạn có thể sử dụng interface Comparable và Comparator để sắp xếp Collections?
Interface Comparable là một interface cho các đối tượng có thể được so sánh theo một thứ tự nào đó. Phương thức duy nhất của nó là compareTo, hoạt động trên hai giá trị: chính đối tượng và đối tượng đối số cùng kiểu. Ví dụ: Integer, Long và các kiểu số khác triển khai interface này. String cũng triển khai interface này và phương thức compareTo của nó so sánh các chuỗi theo thứ tự từ điển.
Interface Comparable cho phép sắp xếp danh sách các đối tượng tương ứng bằng phương thức Collections.sort() và duy trì thứ tự lặp trong các collection triển khai SortedSet và SortedMap. Nếu các đối tượng của bạn có thể được sắp xếp bằng một số logic, chúng nên triển khai interface Comparable.
Interface Comparable thường được triển khai bằng cách sử dụng thứ tự tự nhiên của các phần tử. Ví dụ: tất cả các số Integer được sắp xếp từ giá trị nhỏ hơn đến giá trị lớn hơn. Nhưng đôi khi bạn có thể muốn triển khai một loại sắp xếp khác, ví dụ: sắp xếp các số theo thứ tự giảm dần. Interface Comparator có thể giúp ích ở đây.
Lớp của các đối tượng bạn muốn sắp xếp không cần phải triển khai interface này. Bạn chỉ cần tạo một lớp triển khai và định nghĩa phương thức compare nhận hai đối tượng và quyết định cách sắp xếp chúng. Sau đó, bạn có thể sử dụng instance của lớp này để ghi đè thứ tự tự nhiên của phương thức Collections.sort() hoặc các instance SortedSet và SortedMap.
Last updated