
89. ArrayList khác với LinkedList như thế nào?
Đây là một trong những câu hỏi phổ biến nhất, cùng với câu hỏi về cấu trúc bên trong của HashMap . Không có cuộc phỏng vấn nào hoàn tất nếu không có nó, vì vậy câu trả lời của bạn sẽ dễ dàng khiến bạn thốt ra. Ngoài điều hiển nhiên (chúng có tên khác nhau), chúng còn khác nhau về cấu trúc bên trong. Trước đó, chúng ta đã thảo luận về cấu trúc bên trong của cả ArrayList và LinkedList , vì vậy tôi sẽ không đi sâu vào chi tiết triển khai của chúng. Tôi sẽ chỉ nhắc bạn rằng ArrayList được triển khai bằng cách sử dụng một mảng bên trong có kích thước tăng dần theo công thức sau:<size of the current array> * 3 / 2 + 1
Ngoài ra, việc triển khai LinkedList sử dụng danh sách liên kết đôi nội bộ, nghĩa là mỗi phần tử có một tham chiếu đến các phần tử trước và phần tử tiếp theo, ngoại trừ các phần tử ở đầu và cuối danh sách. Người phỏng vấn thích hỏi những câu hỏi như thế này, "Cái nào tốt hơn, ArrayList hay LinkedList ?" hy vọng bắt được bạn. Suy cho cùng, nếu bạn nói cái này hay cái kia tốt hơn thì bạn đã trả lời sai. 
-
Nếu chỉ mục không được chỉ định thì một mục mới sẽ tự động được thêm vào cuối cho cả hai loại danh sách. Trong LinkedList , phần tử mới sẽ trở thành đuôi mới (chỉ một cặp tham chiếu sẽ được viết lại, do đó độ phức tạp của thuật toán là O(1) ).
Phương thức add thêm một phần tử vào ô trống cuối cùng trong mảng ( O(1) ).
-
Thêm một mục theo chỉ mục thường có nghĩa là chèn nó vào đâu đó ở giữa danh sách. Trong LinkedList , trước tiên phương thức sẽ tìm kiếm vị trí mong muốn bằng cách lặp qua các phần tử từ đuôi và đầu ( O(n/2) ) và sau đó sẽ chèn giá trị bằng cách ghi đè tham chiếu của các phần tử ở cả hai phía của vị trí phần tử mới được chèn vào ( O(1) ). Độ phức tạp thuật toán tổng thể của thao tác này sẽ là O(n/2) .
Trong tình huống tương tự (thêm theo chỉ mục), ArrayList tìm vị trí mong muốn ( O(1) ) và sau đó dịch chuyển tất cả các phần tử nằm ở bên phải (bao gồm cả phần tử đã được lưu trữ tại chỉ mục đã chỉ định) sang phải một (điều này có thể yêu cầu tạo một mảng nội bộ mới và sao chép các phần tử vào đó) ( O(n/2) ). Độ phức tạp tổng thể là O(n/2) .
-
Thêm một phần tử vào đầu LinkedList cũng tương tự như thêm một phần tử vào cuối: phần tử mới trở thành phần đầu mới ( O(1) ). Nhưng đối với ArrayList, thao tác đó yêu cầu di chuyển tất cả các phần tử sang phải ( O(n) ).
90. ArrayList khác với HashSet như thế nào?
Nếu chúng ta có thể so sánh ArrayList và LinkedList trên cơ sở từng hoạt động để xác định cái nào tốt hơn, thì chúng ta sẽ không dễ dàng so sánh giữa ArrayList và HashSet vì chúng là các bộ sưu tập hoàn toàn khác nhau. Bạn có thể so sánh món tráng miệng này với món tráng miệng khác, nhưng so sánh món tráng miệng và món mặn là một thách thức - chúng hoàn toàn khác nhau. Tuy nhiên, tôi sẽ cố gắng chỉ ra một số khác biệt giữa chúng:-
ArrayList triển khai giao diện List trong khi HashSet triển khai giao diện Set .
-
ArrayList cho phép bạn truy cập một phần tử theo chỉ mục: thao tác get có độ phức tạp thuật toán O(1) , nhưng HashSet chỉ cho phép bạn truy cập phần tử mong muốn bằng phép lặp, điều này mang lại độ phức tạp thuật toán từ O(1) đến O(n) .
-
ArrayList cho phép các phần tử trùng lặp. Trong HashSet , tất cả các phần tử là duy nhất: mọi nỗ lực thêm phần tử đã có trong HashSet sẽ không thành công (các phần tử trùng lặp được kiểm tra bằng mã băm, do đó có tên của bộ sưu tập này).
-
ArrayList được triển khai bằng mảng nội bộ, nhưng HashSet được triển khai bằng HashMap nội bộ .
-
ArrayList duy trì thứ tự chèn của các phần tử, nhưng HashSet là tập hợp không có thứ tự và không duy trì thứ tự các phần tử.
-
ArrayList cho phép bất kỳ số lượng giá trị null nào, nhưng bạn chỉ có thể thêm một giá trị null vào HashSet (xét cho cùng, các phần tử phải là duy nhất).
91. Tại sao Java có nhiều cách triển khai mảng động khác nhau như vậy?
Đây là một câu hỏi triết học nhiều hơn. Chúng ta cũng có thể hỏi tại sao họ lại nghĩ ra nhiều công nghệ mới và đa dạng như vậy? Cho thuận tiện. Và điều tương tự cũng đúng đối với một số lượng lớn việc triển khai mảng động. Không ai trong số họ có thể được gọi là cách triển khai tốt nhất hoặc lý tưởng. Mỗi cái đều có ưu điểm riêng cho từng tình huống cụ thể. Công việc của chúng tôi là biết sự khác biệt cũng như điểm mạnh/điểm yếu của họ để có thể sử dụng bộ sưu tập phù hợp nhất cho mọi tình huống nhất định.92. Tại sao Java có nhiều triển khai lưu trữ khóa-giá trị khác nhau như vậy?
Ở đây tình huống cũng giống như việc triển khai mảng động. Chắc chắn không có cái nào tốt hơn những cái khác: mỗi cái đều có điểm mạnh và điểm yếu. Và tất nhiên chúng ta phải tận dụng tối đa điểm mạnh của họ. Ví dụ: gói đồng thời, có nhiều lớp đa luồng, có các bộ sưu tập Đồng thời riêng . Lớp ConcurrentHashMap có lợi thế hơn HashMap tiêu chuẩn về mặt an toàn khi làm việc với dữ liệu trong môi trường đa luồng, nhưng điều đó phải trả giá bằng hiệu năng chậm hơn. Và những triển khai không phải là lựa chọn tốt nhất trong mọi tình huống sẽ dần dần không còn được sử dụng. Ví dụ: Hashtable , ban đầu được dự định là HashMap an toàn theo luồng , đã bị lãng quên và không còn được sử dụng, vì ConcurrentHashMap thậm chí còn tốt hơn Hashtable khi làm việc trong môi trường đa luồng.93. Làm cách nào để sắp xếp một tập hợp các phần tử?
Điều đầu tiên cần nói là lớp đại diện cho các phần tử của bộ sưu tập phải triển khai giao diện Comparable , bao gồm phương thức so sánh . Hoặc bạn cần một lớp triển khai giao diện Comparator , bao gồm cả phương thức so sánh của nó . Cả hai phương pháp đều chỉ ra cách so sánh các đối tượng cùng loại. Điều này rất quan trọng khi sắp xếp, vì thuật toán sắp xếp cần hiểu nguyên tắc nào sẽ sử dụng để so sánh các phần tử. Điều này chủ yếu được thực hiện bằng cách triển khai Comparable trực tiếp trong lớp mà bạn muốn sắp xếp. Sử dụng Comparator ít phổ biến hơn. Giả sử bạn đang sử dụng một lớp từ thư viện nào đó và nó không triển khai Comparable nhưng bạn cần sắp xếp một tập hợp các đối tượng của nó. Vì bạn không thể thay đổi mã của lớp này (ngoại trừ bằng cách mở rộng nó), nên bạn có thể viết một phần triển khai của Comparator để chỉ ra cách so sánh các đối tượng của lớp. Và một ví dụ nữa. Nếu bạn cần sắp xếp các đối tượng cùng loại theo những cách khác nhau thì bạn có thể viết nhiều triển khai Bộ so sánh để sử dụng trong các tình huống khác nhau. Theo quy định, nhiều lớp có sẵn, ví dụ: String , đã triển khai giao diện Comparable . Điều đó có nghĩa là bạn không cần phải lo lắng về cách so sánh các lớp này. Bạn chỉ có thể tiếp tục và sử dụng chúng. Cách đầu tiên và rõ ràng nhất là sử dụng lớp TreeSet hoặc TreeMap . Các lớp này lưu trữ các phần tử theo thứ tự được sắp xếp dựa trên bộ so sánh được các phần tử lớp thực hiện. Đừng quên rằng TreeMap sắp xếp các khóa chứ không phải giá trị. Nếu bạn sử dụng Comparator thay vì Comparable thì bạn cần chuyển một đối tượng Comparator cho hàm tạo của bộ sưu tập khi bạn tạo nó:TreeSet treeSet = new TreeSet(customComparator);
Nhưng nếu bạn có một loại bộ sưu tập khác thì sao? Bạn sắp xếp nó như thế nào? Trong trường hợp này, cách thứ hai của lớp tiện ích Bộ sưu tập - phương thức sắp xếp() - là phù hợp. Phương thức này là tĩnh, vì vậy tất cả những gì bạn cần là thêm tên của lớp vào trước rồi chuyển vào danh sách cần sắp xếp. Ví dụ:
Collections.sort(someList);
Nếu bạn đang sử dụng cách triển khai Comparator thay vì Comparable thì bạn cần chuyển nó vào làm đối số thứ hai:
Collections.sort(someList, customComparator);
Thao tác này sẽ thay đổi thứ tự bên trong của các phần tử trong danh sách đã truyền: danh sách sẽ được sắp xếp bằng bộ so sánh. Lưu ý rằng danh sách được thông qua phải có thể thay đổi được, nếu không phương thức sẽ thất bại và ném ra ngoại lệ UnsupportedOperationException . Tùy chọn thứ ba là sử dụng phương thức được sắp xếp của lớp Stream để sắp xếp các phần tử của bộ sưu tập. Nếu chúng tôi đang sử dụng Comparable :
someList = someList.stream().sorted().collect(Collectors.toList());
Nếu chúng tôi đang sử dụng Comparator :
someList = someList.stream().sorted(customComparator).collect(Collectors.toList());
Cách thứ tư là triển khai thuật toán sắp xếp theo cách thủ công, ví dụ: sắp xếp bong bóng
hoặc sắp xếp hợp nhất
.
Lớp đối tượng. bằng() và hashCode()
94. Hãy mô tả ngắn gọn về lớp Object trong Java.
Trong phần thứ hai của bài đánh giá, chúng ta đã thảo luận về các phương thức của lớp Object . Ở đây tôi sẽ nhắc bạn rằng lớp Object là tổ tiên của mọi lớp trong Java. Nó có 11 phương thức được kế thừa bởi tất cả các lớp.
95. Equals() và hashCode() dùng để làm gì trong Java?
hashCode() là một phương thức của lớp Object được kế thừa bởi tất cả các lớp. Công việc của nó là tạo ra một số đại diện cho một đối tượng cụ thể. Bạn có thể tìm thấy một ví dụ về phương thức này đang hoạt động trong HashMap , trong đó nó được gọi trên các đối tượng chính để lấy mã băm cục bộ, mã này sẽ xác định nhóm nào (ô của mảng bên trong) mà cặp khóa-giá trị sẽ được lưu trữ. Ngoài ra, Phương thức này thường được sử dụng trong phương thức Equals() như một trong những cách chính để xác định đối tượng. Equals() là một phương thức của lớp Object có nhiệm vụ so sánh các đối tượng và xác định xem chúng có bằng nhau hay không. Phương thức này được sử dụng ở mọi nơi chúng ta cần so sánh các đối tượng, vì toán tử so sánh == tiêu chuẩn không phù hợp với các đối tượng, vì nó chỉ so sánh các tham chiếu đối tượng.96. Hãy cho chúng tôi biết về hợp đồng giữa Equals() và hashCode() trong Java?
Đầu tiên, hãy để tôi nói rằng để các phương thức bằng() và hashCode() hoạt động chính xác, chúng phải được ghi đè chính xác. Việc triển khai mới của họ phải tuân theo các quy tắc sau:- Các đối tượng giống hệt nhau trả về giá trị true phải có cùng mã băm.
- Các đối tượng có cùng mã băm không nhất thiết phải bằng nhau.
GO TO FULL VERSION