CÂU HỎI TẬP HỢP TRONG JAVA (JAVA COLLECTIONS)

18. Những interface cơ bản trong Java Collections Framework?

Java Collection Framework cung cấp những thiết kế các interface và class để hỗ trợ việc thao tác trên tập hợp của các đối tuợng. Những interface cơ bản nhất đuợc cung cấp trong Java Collections Framework:

• Collection, biểu thị cho nhóm các đối tuợng, những đối tuợng này đưọc gọi là phần tử của tập hợp.
• Set, là một tập hợp mà không chứa những phần từ trùng nhau.
• List, là một tập hợp đã sắp sếp và có thể chứa những phần tử trùng nhau.
• Map, là một đối tuợng mà ánh xạ các khoá vào các giá trị và không chứa những khoá trùng nhau.

19. Tại sao Colection (interface) không kế thừa (extend) interface Cloneable và Serializable?

Interface Collection biểu thị một nhóm các đối tuợng biết đến như phần tử trong tập hợp. Mỗi sự cài đặt cụ thể của Collection có thể lựa chọn cách riêng để bảo trì và sắp sếp phần tử của nó (lớp cài đặt). Một số tập hợp chấp nhập trùng khoá, trong khi một số thì không. Mục đích và ý nghĩa của clone(bản sao) và serialization đuợc sử dụng trong những cài đặt thật. Vì vậy, những cài đặt cụ thể của tập hợp sẽ quyết định chúng sẽ sử dụng clone và serialization như thế nào.

20. Thế nào là Iterator?

Interface Iterator cung cấp một số các phương thức để duyệt(lặp) qua các phần tử bất kỳ tập hợp nào. Mỗi interface Collection trong Java đều chứa một phương thức iterator để trả về một thực thể của interface Iterator. Iterator có khả năng xoá những phần từ tập hợp trong quá trình lặp.

21. Sự khác biệt giữa Iterator và ListIterator?

Vài sự khác nhau của 2 interface trên:

• Iterator đưọc sử dụng để duyệt qua(lặp qua) các interface Set và List, trong khi ListIterator chỉ đuợc sử dụng để duyệt qua List
• Iterator có thể duyệt qua tập hợp chỉ một huớng, trong khi ListIterator có thể duyệt qua List tất cả các huớng (2 huớng).
• ListIterator cài đặt interface Iterator và chứa thêm một số chức năng mới, như thêm mới một phần tử, thay thế phần từ, lấy chỉ mục (index) cho phần từ kế truớc hay sau nó, etc.

22. Sự khác nhau giữa fail-fast và fail-safe?

Thuộc tính fail-fast trong interface Iterator làm việc với bản sao của tập hợp và vì vậy, nó không ảnh huởng đến bất kỳ sự thay đổi trong tập hợp. Tất cả các lớp tập hợp trong java.util là fail-fast, trong khi các lớp trong java.util.concurrent là fail-safe. Fail-fast ném ra ngoại lệ ConcurrentModificationException, trong khi fail-safe không bao giờ ném ra ngoại lệ như thế.

23. HashMap trong Java làm việc như thế nào?

HashMap trong Java chứa những cặp khoá-giá trị. HashMap yêu cầu một hàm băm và sử dụng phương thức hashCode và equals để thêm vào và lấy lại phần từ một tập hợp tương ứng. Khi hàm put (đẩy vào, thêm vào) đuợc gọi, HashMap tính toán giá trị hash(giá trị băm) của khoá và lưu trữ cặp giá trị (key-value) đuợc đánh chỉ mục thích hợp vào tập hợp. Nếu khoá đã tồn tại, giá trị của nó đuợc cập nhập(update) bằng giá trị mới. Một vài đặc tính quan trọng của HashMap là mức chứa của nó, yếu tố tải dữ liệu và ngưỡng thay đổi kích thước tập hợp.

24. Sự quan trọng của hàm hashCode và equals là gì?

HashMap trong Java sử dụng 2 hàm hashCode và equals để xác định chỉ mục của cặp khoá-giá trị(key-value). 2 hàm này còn được sử dụng khi chúng ta yêu cầu giá trị của một khoá cụ thể. Nếu 2 hàm này không đuợc cài đặt(implement) chính xác, như 2 khoá khác nhau lại cho ra hash code (giá trị đã băm) giống nhau và vì vậy, chúng sẽ đuợc xem như là bằng nhau trong tập hợp.Xa hơn nữa, 2 hàm này còn sử dụng để phát hiện trùng lặp. Nên, việc cài đặt 2 hàm là yếu tốt then chốt để kiểm tra tính đúng đắn của HashMap.

25. Sự khác nhau giữa HashMap và Hashtable?

Cả HashMap và Hashtable đều cài đặt interface Map và vì vậy, chúng có nhiều đặc tính giống nhau. Tuy nhiên, chúng khác nhau vài điểm:

• HashMap chấp nhận giá trị khoá hoặc giá trị(value) null, trong khi Hashtable thì không (cả kay và value).
• Hashtable thì đồng bộ (synchronized), HashMap thì không. Vì vậy, HashMap đuợc sử dụng nhiều trong môi truờng đơn luồng(single-thread), còn Hashtable sử dụng trong môi truờng đa luồng (multi-thread).
• HashMap cung cấp bộ khoá cho nó và ứng dụng có thể lặp(duyệt) qua chúng. Vì vậy, HashMap là fail-fast(câu hỏi 22).Hastable thì cung cấp kiểu liệt kê (Enumeration) cho các khoá.
• Hashtable đuợc xem như lớp legacy.

Mình không dịch đưọc từ legacy, mình thêm đuờng dẫn để các bạn đọc thêm legacy classes và interfaces là gì http://www.rapidprogramming.com/tutorial/JAVA-Legacy-classes-interfaces-145.

26.Sự khác nhau giữa Array và ArrayList? Khi nào chúng ta sẽ sử dụng Array thay vì ArrayList?

Array và ArrayList khác nhau :

• Array có thể chứa kiểu dữ liệu cơ bản và đối tưọng, trong khi ArrayList chỉ chứa đối tuợng.
• Array cố định số luợng phần từ, ArrayList thì động
• ArrayList cung cấp nhiều hàm và chức năng hơn như addAll, removeAll, iterator, vv.
• Đối với danh sách kiểu dữ liệu cơ bản, tập hợp (collection) sử dụng autoboxing để giảm viết mã. Tuy nhiên, điều đó sẽ làm chúng (collection) chạy chậm hơn khi làm việc với mảng kiểu dữ liệu cơ bản (fixed).

27. Sự khác biệt giữa ArrayList và LinkedList? 

Cả 2 ArrayList và LinkedList đều cài đặt interface List, nhưng chúng có vài điểm khác biệt:

• ArrayList là một kiểu cấu trúc dữ liệu chỉ mục như Array. Nó cung cấp sự truy cập ngẫu nhiên vào phần tử với hiệu năng là O(1). Còn LinkedList chứa dữ liệu như một danh sách các phần tử và mỗi phần tử liên kết với phần tử truớc và sau nó. Trong truờng hợp này, thao tác tìm kiếm một phần tử mất thời gian là O(n).
• Thao tác thêm và xoá phần tử của LinkedList sẽ nhanh hơn so với ArrayList, bởi vì không cần phải thay đổi kích thuớc hay cập nhập lại chỉ mục khi một phần tử được thêm vào.
• ListedList tiêu hao nhiều bộ nhớ hơn ArrayList bởi vì mỗi phần tử (node) trong LinkedList chứa 2 tham chiếu, một cho phần tử phía trước và một cho phần tử sau nó.

28. 2 interface Comparable và Comparator là gì? Liệt kê điểm khác nhau giữa chúng.

Java cung cấp một interface là Comparable chỉ chứa một phuơng thức compareTo. Phương thức này so sánh 2 đối tuợng, để sắp đặt trật tự giữa chúng. Đặt biệt nó trả về một số dương, 0 hoặc số âm để cho biết đối tuợng nhận vào sẽ nhỏ hơn, bằng hay lớn hơn nó. Java cung cấp interface Comparator chứa 2 phuơng thức là compare và equals. Phuơng thức compare nhận vào 2 tham số và xác định trật tự (order) giữa chúng. Hàm trả về số duơng, 0 hoặc số âm để biểu thị tham số đầu tiên sẽ nhỏ, bằng hay lớn hơn tham số thứ 2. Phương thức equals yêu cầu một đối số là một đối tuợng và giúp xác định đối tuợng truyền vào có phải là một comparator. Hàm trả về true nếu đối tuợng truyền vào là một comparator và đuợc sắp xếp như một comparator.

29. Thế nào là Priority Queue?

PriorityQueue là một queue(hàng đợi) không giới hạn (unbound), dựa trên priority heap và phần tử của nó đuợc sắp sắp theo trật tự ban đầu. Tại thời gian tạo ra nó, chúng ta sẽ cung cấp một Comparator với nhiệm vụ là sắp xếp thứ tự các phần tử của PriorityQueue. PriorityQueue không chập giá trị null, bởi những đối tuơng đó không hề có thứ tự. Cuối cùng, PriorityQueue không thread-safe và nó sử dụng thời gian O(log(n)) cho thao tác enqueue(đẩy vào hàng đợi)  và dequeue (lấy ra khỏi hàng đợi).

30. Thế nào là Big-O notation, liệt kê một số ví dụ  trên các cấu trúc dữ liệu khác nhau?

Ký hiện big-O đơn giản là biểu thị khả năng của thuật toán khi mở rộng hay tính toán trong tình huống xấu nhất, như số luợng phần từ trong cấu trúc dữ liệu tăng lên. Ký hiệu O ngoài ra còn đuợc sử dụng để biểu thị cho cách hành vi khác như mức sử dụng bộ nhớ. Bởi vì những lớp Collection thật ra cũng là những cấu trúc dữ liệu, chúng ta thuờng sử dụng big-O để lựa chọn phuơng pháp cài đặt tốt nhất để sử dụng, dựa vào thời gian, bộ nhớ và kết quả. Big-O đưa ra chỉ số tốt về hiệu năng của dữ liệu lớn.

31. Khác biệt giữa mảng có thứ tự và mảng không thứ tự?

Lợi ích chính của mảng có thứ tự là thời gian tìm kiếm có độ phức tạp là O(logn), trong khi mảng không có thứ tự sẽ là O(n). Bất lợi của mảng có thứ tự là quá trình chèn thêm phần tử có độ phức tạp O(n), bởi vì những phần tử có giá trị lớn hơn phải di chuyển để chứa phần tử mới. Việc chèn thêm phần tử của mảng có thứ tự có thời gian cố định là O(1).

32. Những cách làm tốt nhất (best practices) liên quan đến  Collection trong Java?

• Chọn loại collection phù hợp để sử dụng, dựa vào ứng dụng đang cần gì, và cốt yếu là hiệu năng (performance) khi sử dụng nó. Ví dụ, nếu kích cỡ của các phẩn tử là cố định và biết trước, chúng ta nên sử dụng Array thay vì ArrayList.
• Một số lớp collection cho phép chúng ta đưa vào sức chứa khi khởi tạo (initial capacity). Vì vậy, nếu chúng ta ước lượng số lượng phần tử mà muốn lưu trữ, chúng ta có thể sử dụng nó (capacity) để tránh việc làm mới hay thay đổi kích thước mảng.
• Luôn luôn sử dụng Generics cho các kiểu dữ liệu an toàn(type-safety), dễ đọc và tinh tế hơn. Ngoài ra, sử dụng Generics, bạn tránh được ClassCastException trong quá trình thực thi (runtime).
• Sử dụng lớp bất biến(immutable classes) được cung cấp bởi JDK như khóa trong Map, để tránh việc cài đặt hàm hashCode và equals cho những lớp tự mình tùy chỉnh.
• Program in terms of interface not implementation (Không biết dịch thế nào :D, sẽ cố gắng giải thích trong chú thích riêng)
• Trả về một tập hợp hay mảng rỗng thay vì trả về giá trị null trong trường hợp collection thật sự rỗng.

33. Sự khác biệt giữa hai interfaces Enumeration và Iterator?

Enumeration nhanh gấp đôi so với Iterator và sử dụng rất ít bộ nhớ. Tuy nhiên, Iterator an toàn hơn Enumeration, bởi vì những thread ( luồng) khác không thể thay đổi đối tượng collection khi đang duyệt qua bởi Iterator. Ngoài ra, Iterator cho phép loại bỏ phần từ trong tập hợp, trong khi không thể làm điều đó với Enumeration.

34. Sự khác biệt giữa HashSet và TreeSet?

HashSet được cài đặt sử dụng bảng băm (hash table), nên những phần tử của nó không có thứ tự. Các phương thức add, remove và contains của HashSet có độ phức tạp là O(1). TreeSet được cài đặt sử dụng cấu trúc cây (tree structure). Những phần tử trong TreeSet được sắp xếp, nên các phương thức add, remove và contains có độ phức tạp O(logn).