Khám phá các câu hỏi và câu trả lời từ cuộc phỏng vấn xin việc cho vị trí nhà phát triển Java. Phần 9

Trở thành một lập trình viên không hề dễ dàng. Luôn luôn có một cái gì đó mới để học hỏi. Và, như trong bất kỳ nỗ lực nào khác, điều khó khăn nhất là bắt đầu, thực hiện bước đầu tiên hướng tới mục tiêu của bạn. Nhưng vì bạn đã ở đây và đọc bài viết này nên bạn đã hoàn thành bước đầu tiên. Điều này có nghĩa là bây giờ bạn cần phải cố tình tiến tới mục tiêu của mình mà không giảm tốc độ hoặc chệch sang một bên. Tôi cho rằng mục tiêu của bạn là trở thành nhà phát triển Java hoặc nâng cao kiến ​​thức nếu bạn đã là nhà phát triển. Nếu vậy, hãy tiếp tục giải quyết một danh sách đầy đủ các câu hỏi phỏng vấn nhà phát triển Java. Tiếp tục đi!

Bộ sưu tập

84. Hãy cho chúng tôi biết về các trình vòng lặp và cách chúng được sử dụng

Bộ sưu tập là chủ đề được yêu thích trong bất kỳ cuộc phỏng vấn nhà phát triển Java nào. Khi trả lời các câu hỏi về hệ thống phân cấp bộ sưu tập, thí sinh thường nói rằng nó bắt đầu bằng giao diện Bộ sưu tập . Nhưng nó không như vậy. Có một giao diện khác ở cấp độ trên: Iterable . Giao diện này bao gồm phương thức iterator() , cho phép bạn truy cập đối tượng Iterator cho bộ sưu tập hiện tại. Và chính xác thì đối tượng Iterator này là gì ? Đối tượng Iterator cung cấp khả năng di chuyển qua một bộ sưu tập và lặp lại các phần tử của nó và người dùng không cần biết chi tiết triển khai cụ thể của bộ sưu tập. Nói cách khác, nó là một loại con trỏ tới các phần tử của bộ sưu tập, như thể nó đang nhìn vào một trong số chúng. Trình vòng lặp có các phương thức như:

• hasNext() - trả về true nếu phép lặp có phần tử khác (phương thức này cho bạn biết khi nào bạn đã đến cuối bộ sưu tập);

• next() - trả về mục tiếp theo trong lần lặp. Nếu không có thì ngoại lệ NoSuchElementException sẽ được ném ra. Điều đó có nghĩa là trước khi bạn sử dụng phương pháp này, tốt nhất bạn nên sử dụng phương thức hasNext() để đảm bảo phần tử tiếp theo tồn tại;

• Remove() - xóa khỏi bộ sưu tập phần tử cuối cùng nhận được bằng phương thức next() . Nếu next() chưa bao giờ được gọi thì việc gọi Remove() sẽ khiến IllegalStateException bị ném ra;

• forEachRemaining(<Consumer>) - thực thi hành động được truyền trên từng thành phần của bộ sưu tập (phương thức này đã xuất hiện trong Java 8).

Đây là một ví dụ nhỏ về việc lặp qua một danh sách và loại bỏ tất cả các phần tử của nó bằng các phương thức lặp khác nhau mà chúng tôi đã xem xét:

List<String> list = new ArrayList<>();
list.add("Hello ");
list.add("World, ");
list.add("It's ");
list.add("Amigo!");
Iterator iterator = list.iterator();

while(iterator.hasNext()) {
   iterator.next();
   iterator.remove();
}
System.out.println(list.size());

Bảng điều khiển sẽ hiển thị như sau: Điều này có nghĩa là các phần tử đã được loại bỏ thành công. Khi bạn nhận được một trình vòng lặp, bạn có thể sử dụng một phương thức để hiển thị tất cả các thành phần trên màn hình:

iterator.forEachRemaining(x -> System.out.print(x));

Nhưng một khi chúng ta làm điều này, trình vòng lặp sẽ trở nên không phù hợp để sử dụng tiếp: nó đã duyệt qua toàn bộ danh sách và một trình vòng lặp thông thường không có phương pháp lặp ngược lại. Và điều đó tạo nên một sự chuyển tiếp thú vị trong cuộc thảo luận về LinkedList , cụ thể là phương thức listIterator() của nó , trả về một kiểu lặp nâng cao: ListIterator . Ngoài các phương thức của một trình vòng lặp (tiêu chuẩn) thông thường, loại này còn có các phương thức sau:

• add(<Element>) - thêm một phần tử mới vào danh sách;

• hasPrevious() - trả về true nếu có một phần tử nằm trước phần tử tiếp theo (nếu có phần tử trước đó);

• nextIndex() - trả về chỉ mục của phần tử tiếp theo;

• trước() - trả về phần tử trước đó (phần tử trước phần tử tiếp theo);

• previousIndex trả về chỉ mục của phần tử trước đó.

• set(<Element>) - thay thế phần tử cuối cùng được trả về bởi next() hoặc previous() .

Như bạn có thể thấy, trình vòng lặp này có chức năng thú vị hơn nhiều: nó cho phép bạn đi theo cả hai hướng và mang lại sự tự do đáng kể khi làm việc với các phần tử. Bạn cũng nên biết rằng khi mọi người nói về iterator, đôi khi họ muốn nói đến chính mẫu thiết kế.

85. Hệ thống phân cấp bộ sưu tập nào tồn tại trong Khung công tác sưu tập Java?

Có hai hệ thống phân cấp bộ sưu tập trong Java. Hệ thống phân cấp đầu tiên là hệ thống phân cấp Bộ sưu tập, có cấu trúc sau: Nó được chia thành các bộ sưu tập con sau:

• Set là một giao diện mô tả một tập hợp, một cấu trúc dữ liệu chứa các phần tử duy nhất (không lặp lại) không có thứ tự. Giao diện này có một số triển khai tiêu chuẩn: TreeSet , HashSet và LinkedHashSet .

• Danh sách là một giao diện mô tả cấu trúc dữ liệu lưu trữ một chuỗi các đối tượng được sắp xếp. Các đối tượng trong Danh sách có thể được chèn và xóa theo chỉ mục của chúng trong danh sách (giống như một mảng, nhưng có khả năng thay đổi kích thước động). Giao diện này cũng có một số triển khai tiêu chuẩn: ArrayList , Vector ( không được dùng nữa và không thực sự được sử dụng ) và LinkedList .

• Hàng đợi là giao diện mô tả cấu trúc dữ liệu lưu trữ các mục trong hàng đợi Vào trước ra trước (FIFO) . Giao diện này có các cách triển khai tiêu chuẩn sau: LinkedList (đúng vậy, nó cũng triển khai Queue ) và PritityQueue .

Hệ thống phân cấp bộ sưu tập thứ hai là hệ thống phân cấp Bản đồ , có cấu trúc sau: Hệ thống phân cấp bộ sưu tập này không có sự phân chia thành các bộ sưu tập con (vì bản thân hệ thống phân cấp Bản đồ là một thứ gì đó thuộc về một bộ sưu tập con độc lập). Việc triển khai Bản đồ tiêu chuẩn là Hashtable (không được dùng nữa), LinkedHashMap và TreeMap . Trong thực tế, khi mọi người hỏi về Bộ sưu tập , họ thường muốn nói đến cả hai hệ thống phân cấp.

86. Cấu trúc bên trong của ArrayList là gì?

ArrayList giống như một mảng, nhưng nó có thể mở rộng một cách linh hoạt . Điều đó nghĩa là gì? Về cơ bản, ArrayList sử dụng một mảng thông thường, tức là nó lưu trữ các phần tử của nó trong một mảng bên trong có kích thước mặc định là 10 ô. Khi mảng bên trong đã đầy, một mảng mới sẽ được tạo. Kích thước của mảng mới được xác định theo công thức sau:

<size of the current array> * 3 / 2 + 1

Vì vậy, nếu kích thước của mảng của chúng ta là 10, thì kích thước của mảng mới sẽ là: 10 * 3/2 + 1 = 16. Sau đó, tất cả các giá trị từ mảng ban đầu (cũ) sẽ được sao chép vào mảng đó bằng cách sử dụng tính năng tích hợp sẵn Phương thức System.arraycopy() và mảng ban đầu sẽ bị xóa. Tóm lại, đó là cách ArrayList thực hiện thay đổi kích thước động. Hãy xem xét các phương thức ArrayList phổ biến nhất : 1. add(<Element>) — thêm một phần tử vào cuối mảng (trong ô trống cuối cùng), sau lần đầu tiên kiểm tra xem có ô nào có sẵn trong mảng hay không. Nếu không, một mảng mới sẽ được tạo và các phần tử sẽ được sao chép vào mảng đó. Độ phức tạp về thời gian của thao tác này là O(1). Có một phương thức add(<Index>, <Element>) tương tự . Nó thêm một phần tử không phải vào cuối danh sách (mảng), mà vào ô cụ thể được biểu thị bằng chỉ mục được đưa vào dưới dạng đối số. Trong trường hợp này, độ phức tạp về thời gian sẽ khác nhau tùy thuộc vào vị trí bạn thêm:

• nếu phần bổ sung ở gần đầu danh sách thì độ phức tạp về thời gian sẽ gần bằng O(N), bởi vì tất cả các phần tử nằm ở bên phải của phần tử mới sẽ phải được di chuyển sang bên phải một ô;
• nếu phần tử được chèn vào giữa thì nó sẽ là O(N/2), vì chúng ta chỉ cần dịch chuyển một nửa số mục trong danh sách sang phải một ô.

Nghĩa là, độ phức tạp về thời gian của phương pháp này nằm trong khoảng từ O(1) đến O(N), tùy thuộc vào vị trí phần tử được chèn vào. 2. set(<Index>, <Element>) — ghi một phần tử vào vị trí được chỉ định trong danh sách. Nếu một phần tử đã có mặt ở vị trí đó, phương thức sẽ ghi đè lên nó. Độ phức tạp về thời gian của thao tác này là O(1), vì nó không liên quan đến bất kỳ thao tác dịch chuyển nào: chúng ta chỉ sử dụng chỉ mục để tính địa chỉ của ô trong mảng, có độ phức tạp O(1), sau đó viết phần tử mới . 3. Remove(<index>) — xóa một phần tử theo chỉ mục của nó trong mảng bên trong. Khi xóa một mục không ở cuối danh sách, tất cả các mục ở bên phải của mục đã xóa phải được dịch chuyển sang trái một ô để thu hẹp khoảng cách do việc xóa. Theo đó, độ phức tạp về thời gian sẽ giống như đối với add(<Index>, <Element>) khi thêm một phần tử vào giữa: O(N/2). Rốt cuộc, bạn cần dịch chuyển một nửa số phần tử sang trái một ô. Và nếu chúng ta đang nói về sự khởi đầu thì O(N). Hoặc nếu ở cuối thì O(1), vì bạn không cần phải di chuyển bất cứ thứ gì.

87. Cấu trúc bên trong của LinkedList là gì?

Một ArrayList chứa các phần tử trong mảng bên trong, nhưng LinkedList lưu trữ chúng trong danh sách liên kết đôi. Điều này có nghĩa là mỗi phần tử chứa một liên kết đến phần tử trước và phần tử tiếp theo . Phần tử đầu tiên không liên kết với phần tử trước đó (xét cho cùng, nó là phần tử đầu tiên). Nó cũng được coi là phần đầu của danh sách và đối tượng LinkedList có tham chiếu trực tiếp đến nó. Tương tự, phần tử cuối cùng không có phần tử tiếp theo vì nó là phần tử cuối của danh sách. Đối tượng LinkedList cũng tham chiếu trực tiếp đến nó. Điều này có nghĩa là độ phức tạp về thời gian của việc truy cập phần đầu hoặc phần cuối của danh sách là O(1). Trong ArrayList , nếu danh sách tăng lên thì mảng bên trong cũng tăng lên. Ở đây mọi thứ đều dễ dàng hơn: việc thêm một tham chiếu cũng đơn giản như thay đổi một vài liên kết. Hãy xem xét một số phương thức LinkedList được sử dụng nhiều nhất : 1. add(<Element>) — thêm một phần tử vào cuối danh sách, tức là sau phần tử cuối cùng (5), một liên kết đến phần tử mới sẽ được thêm vào như tiếp theo . Tham chiếu trước đó trong phần tử mới sẽ trỏ đến phần tử (5) hiện đứng trước nó trong danh sách. Độ phức tạp về thời gian của thao tác này là O(1), vì chúng ta chỉ cần liên kết đến phần tử cuối cùng và như bạn sẽ nhớ, đối tượng LinkedList có tham chiếu trực tiếp đến phần đuôi và việc truy cập nó có độ phức tạp về thời gian không đổi tối thiểu. 2. add(<Index>, <Element>) — thêm một phần tử theo chỉ mục. Giả sử khi thêm một phần tử vào giữa danh sách, phương pháp này trước tiên sẽ lặp lại các phần tử từ đầu và đuôi (theo cả hai hướng) cho đến khi tìm thấy vị trí mong muốn. Nếu chúng ta thêm một phần tử vào giữa phần tử thứ ba và thứ tư (trong hình trên), thì liên kết tiếp theo của phần tử thứ ba sẽ trỏ đến phần tử mới. Và phần trước của phần tử mới được thêm vào sẽ trỏ đến phần tử thứ ba. Đổi lại, liên kết trước của phần tử thứ tư cũ bây giờ sẽ trỏ đến phần tử mới và liên kết tiếp theo của phần tử mới sẽ trỏ đến phần tử thứ tư mới: Độ phức tạp về thời gian của phương pháp này phụ thuộc vào chỉ mục của phần tử mới:

• nếu nó ở gần đầu hoặc đuôi, thao tác sẽ tiến tới O(1), vì thực tế không cần thiết phải lặp lại các phần tử;
• nếu nó ở gần giữa thì chúng ta sẽ có O(N/2), vì phương thức sẽ tìm kiếm từ đầu và đuôi cùng lúc cho đến khi tìm thấy phần tử mong muốn.

3. set(<Index>, <Element>) — ghi một phần tử vào vị trí được chỉ định trong danh sách. Độ phức tạp về thời gian của thao tác này sẽ nằm trong khoảng từ O(1) đến O(N/2), một lần nữa tùy thuộc vào mức độ gần của phần tử mới với phần đầu, phần đuôi hoặc phần giữa. 4. Remove(<index>) — xóa một phần tử khỏi danh sách bằng cách làm cho nó sao cho phần tử trước phần tử đã xóa ( previous ) bây giờ đề cập đến phần tử sau phần tử đã xóa ( next ). Và ngược lại, tức là phần tử sau phần tử đã xóa bây giờ đề cập đến phần tử trước phần tử đã xóa: Quá trình này ngược lại với việc thêm theo chỉ mục ( add(<Index>, <Element>) ).

88. Cấu trúc bên trong của HashMap là gì?

Đây có thể là một trong những câu hỏi phỏng vấn phổ biến nhất dành cho các ứng viên phát triển Java. HashMap hoạt động với các cặp khóa-giá trị . Chúng được lưu trữ bên trong HashMap như thế nào? HashMap có một mảng nút bên trong:

Node<K,V>[] table

Theo mặc định, kích thước của mảng là 16 và nó tăng gấp đôi mỗi khi nó chứa đầy các phần tử (nghĩa là khi đạt đến LOAD_FACTOR ; nó chỉ định ngưỡng cho mức độ đầy đủ của mảng - theo mặc định là 0,75 ) . Mỗi nút lưu trữ một hàm băm của khóa, khóa, giá trị và tham chiếu đến phần tử tiếp theo: Trong trường hợp này, "tham chiếu đến phần tử tiếp theo" có nghĩa là chúng ta đang xử lý một danh sách liên kết đơn, trong đó mỗi phần tử chứa một liên kết đến phần tiếp theo. Nói cách khác, HashMap lưu trữ dữ liệu của nó trong một mảng các danh sách liên kết đơn. Nhưng hãy để tôi nói ngay rằng khi một ô của mảng bảng có một danh sách liên kết đơn bao gồm nhiều hơn một phần tử thì điều đó là không tốt. Hiện tượng này được gọi là va chạm . Nhưng điều đầu tiên trước tiên. Hãy xem cách lưu một cặp mới bằng phương thức put . Đầu tiên, phương thức lấy hashCode() của khóa . Điều này ngụ ý rằng để HashMap hoạt động chính xác, các khóa bạn sử dụng phải là các lớp ghi đè phương thức này. Mã băm này sau đó được sử dụng trong phương thức hash() nội bộ để xác định chỉ mục của một số ô trong mảng bảng. Chỉ mục kết quả cho phép chúng ta truy cập vào một ô cụ thể của mảng bảng. Chúng tôi có hai trường hợp ở đây:

1. Ô trống - trong trường hợp này, giá trị Nút mới được lưu trữ trong đó.
2. Ô không trống — trong trường hợp này, giá trị của các khóa được so sánh. Nếu chúng bằng nhau thì giá trị Nút mới sẽ ghi đè giá trị cũ; nếu không bằng thì giá trị tiếp theo sẽ được truy cập và khóa của nó được so sánh... Và cứ như vậy, cho đến khi giá trị mới ghi đè một số giá trị cũ hoặc chúng ta đến cuối danh sách liên kết đơn và sau đó lưu giá trị mới ở đó dưới dạng phần tử cuối cùng.

Khi tìm kiếm một phần tử theo khóa (sử dụng phương thức get(<key>) ), hashCode() của khóa sẽ được tính toán và sau đó chỉ mục của nó trong mảng được tính bằng hash() . Số kết quả là chỉ mục của một ô trong mảng bảng , sau đó chúng tôi tìm kiếm bằng cách lặp qua các nút và so sánh khóa của nút mong muốn với khóa của nút hiện tại. Lý tưởng nhất là các phép toán Bản đồ có độ phức tạp về mặt thuật toán là O(1), bởi vì chúng ta đang truy cập vào một mảng và, như bạn sẽ nhớ, là O(1), bất kể số phần tử mà nó chứa. Nhưng chúng ta không giải quyết trường hợp lý tưởng. Khi ô không trống (2) và đã lưu trữ một số nút, thì độ phức tạp thuật toán sẽ trở thành O(N) (tuyến tính), bởi vì bây giờ cần phải lặp lại các phần tử trước khi chúng ta tìm đúng vị trí. Tôi không thể không đề cập rằng bắt đầu từ Java 8, nếu một nút ở dạng danh sách liên kết đơn có nhiều hơn 8 phần tử (va chạm), thì nó sẽ được chuyển đổi thành cây nhị phân. Trong trường hợp này, độ phức tạp của thuật toán không còn là O(N), mà là O(log(N)) — và đó hoàn toàn là một vấn đề khác, phải không? HashMap là một chủ đề lớn và mọi người thích đặt câu hỏi về nó trong các cuộc phỏng vấn xin việc. Vì vậy, tôi khuyên bạn nên biết nó như lòng bàn tay. Cá nhân tôi chưa bao giờ có cuộc phỏng vấn nào mà không có các câu hỏi về HashMap . Đó là tất cả cho ngày hôm nay. Còn tiếp...