Phân tích các câu hỏi và câu trả lời từ các cuộc phỏng vấn dành cho nhà phát triển Java. Phần 9

Pháo hoa! Trở thành một lập trình viên không hề dễ dàng. Bạn cần không ngừng học hỏi, luôn học hỏi những điều mới mẻ. Tuy nhiên, cũng như bất kỳ hoạt động kinh doanh 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. Và vì bạn đang ngồi trên trang 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 bị chậm lại hoặc tắt máy trên đường đi. Nếu tôi hiểu chính xác thì 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à một nhà phát triển Java. Nếu vậy thì bạn đã đến đúng nơi rồi, vì chúng tôi sẽ tiếp tục phân tích danh sách phong phú gồm hơn 250 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 sử dụng chúng

Bộ sưu tập là một trong những chủ đề được yêu thích trong bất kỳ cuộc phỏng vấn nào của nhà phát triển Java và khi nói về hệ thống phân cấp bộ sưu tập, các ứng viên thường nói rằng nó bắt đầu bằng giao diện Bộ sưu tập . Nhưng điều này không đúng, vì phía trên giao diện này còn có một giao diện khác - Iterable . Giao diện này đại diện cho phương thức iterator() , cho phép bạn gọi một đố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ì ? Iterator là một đối tượng cung cấp khả năng di chuyển qua một bộ sưu tập và lặp qua các phần tử mà người dùng không cần biết cách triển khai một bộ sưu tập cụ thể. Nghĩa là, đây là một loại con trỏ nào đó tới các phần tử của bộ sưu tập, có vẻ như nhìn vào một vị trí nhất định trong đó. Trình vòng lặp có các phương thức sau:

• hasNext() - trả về true nếu có một phần tử nằm sau con trỏ (phương thức này cho phép bạn tìm hiểu xem đã đạt đến cuối bộ sưu tập chưa);
• next() - trả về phần tử tiếp theo sau con trỏ. Nếu không có, NoSuchElementException sẽ bị ném ra . Nghĩa là, trước khi sử dụng phương pháp này, tốt hơn là đảm bảo rằng phần tử đó tồn tại - sử dụng hasNext() ;
• Remove() - xóa phần tử cuối cùng nhận được từ bộ sưu tập bằng phương thức next() . Nếu next() chưa bao giờ được gọi trước khi delete() được gọi, một ngoại lệ sẽ được đưa ra - IllegalStateException ;
• forEachRemaining(<Consumer>) - thực hiện hành động được truyền với từng thành phần của bộ sưu tập (phương thức 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 đã thảo luận:

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ị: Điều này có nghĩa là việc loại bỏ các phần tử đã thành công. Khi đã có iterator, chúng ta có thể sử dụng một phương thức để in tất cả các phần tử ra màn hình:

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

Nhưng sau đó, trình vòng lặp sẽ không còn phù hợp để sử dụng tiếp vì nó sẽ duyệt 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 quay lui. Ở đây chúng ta dần dần tiếp cận LinkedList , cụ thể là phương thức listIterator() của nó , phương thức này trả về một kiểu lặp hiện đại hóa - ListIterator . Bên cạnh các phương thức lặp (tiêu chuẩn) thông thường, phương thức này còn có các phương thức bổ sung:

• add(<Element>) - chèn 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 con trỏ (cho dù có phần tử trước đó);
• nextIndex() - trả về chỉ mục trong danh sách phần tử tiếp theo sau con trỏ;
• trước() - trả về phần tử trước đó (tối đa con trỏ);
• trướcIndex() - 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 các phương thức next() hoặc previous() .

Như bạn có thể thấy, chức năng của trình vòng lặp này thú vị hơn nhiều: nó cho phép bạn di chuyển theo cả hai hướng và rảnh tay khi làm việc với các phần tử. Ngoài ra, khi mọi người nói về các trình vòng lặp, đôi khi họ muốn nói đến chính mẫu đó. Để tránh gặp rắc rối và nói về nó một cách thuyết phục, hãy đọc bài viết này về mẫu Iterator .

85. Hệ thống phân cấp bộ sưu tập trong Java Collection Framework là gì?

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 chính là hệ thống phân cấp Bộ sưu tập với cấu trúc sau: Lần lượt, nó được chia thành các bộ sưu tập con sau:

• Tập hợp là một giao diện mô tả cấu trúc dữ liệu như một tập hợp chứa các phần tử duy nhất (không lặp lại) không có thứ tự. Giao diện có các 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 phiên bản có trong Danh sách có thể được chèn và xóa theo chỉ mục của chúng trong bộ sưu tập này (tương tự như một mảng, nhưng có khả năng thay đổi kích thước động). Giao diện có các triển khai tiêu chuẩn - ArrayList , Vector ( được coi là lỗi thời và không thực sự được sử dụng ) và LinkedList .
• Hàng đợi là một giao diện mô tả cấu trúc dữ liệu lưu trữ các phần tử dưới dạng hàng đợi tuân theo quy tắc FIFO - First In First Out . Giao diện có các cách triển khai tiêu chuẩn sau: LinkedList (vâng, nó cũng triển khai Hàng đợi ) và PritityQueue .

Hệ thống phân cấp thứ hai của các bộ sưu tập là Map , có cấu trúc sau: Trong 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 Map giống như một bộ sưu tập con, nhưng nằm riêng biệt). Việc triển khai Bản đồ tiêu chuẩn là Hashtable (được coi là không dùng nữa), LinkedHashMap và TreeMap . Trên thực tế, khi được hỏi về Collection , cả hai hệ thống phân cấp thường có ý nghĩa như vậy.

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

ArrayList tương tự như mảng nhưng có khả năng mở rộng linh hoạt. Nó có nghĩa là gì? Thực tế là ArrayList hoạt động trên cơ sở một mảng thông thường, cụ thể là nó lưu trữ các phần tử trong một mảng bên trong (kích thước mặc định của nó 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 này được xác định theo công thức:

<размерТекущегоМассива> * 3 / 2  + 1

Tức là, nếu kích thước 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. Tiếp theo, tất cả các giá trị từ mảng đầu tiên (cũ) sẽ được sao chép vào đó bằng cách sử dụng hàm phương thức System.arraycopy () gốc và mảng đầu tiên sẽ bị xóa. Trên thực tế, đây là cách triển khai khả năng mở rộng động của ArrayList . Chúng ta hãy xem các phương thức ArrayList được sử dụng nhiều nhất : 1. add(<Element>) - thêm một phần tử vào cuối mảng (vào ô trống cuối cùng) và trước tiên hãy kiểm tra xem có khoảng trống trong mảng này hay không. Nếu không có, một mảng mới sẽ được tạo để sao chép các phần tử vào đó. Độ phức tạp logarit của phép toán này là O(1). Có một phương pháp tương tự - add(<Index>,<Element>) . Nó thêm một phần tử không phải vào cuối danh sách (mảng), mà vào một ô cụ thể với chỉ mục xuất hiện dưới dạng đối số. Trong trường hợp này, độ phức tạp logarit sẽ khác nhau tùy thuộc vào vị trí nó được thêm vào:

• nếu đây gần như là phần đầu của danh sách, thì độ phức tạp logarit 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 - O(N/2) vì chúng ta chỉ cần di chuyển một nửa số thành phần trong danh sách sang bên phải một ô.

Nghĩa là, độ phức tạp logarit của phương pháp này nằm trong khoảng từ O(N) đến O(1) 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 đã có một phần tử ở vị trí đó thì hãy ghi đè lên nó. Độ phức tạp logarit của thao tác này là O(1), vì không có sự thay đổi nào: chỉ tìm kiếm theo chỉ mục trong mảng, như chúng ta nhớ, có độ phức tạp là O(1) và ghi phần tử. 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, bạn phải di chuyển tất cả các mục sang bên phải của mục đó một ô sang trái để thu hẹp khoảng trống bên trái sau khi xóa mục đó. Do đó, độ phức tạp logarit sẽ giống như add(<Index>,<Element>) nếu phần tử ở giữa - O(N/2) - vì bạn cần dịch chuyển một nửa số phần tử sang trái. Theo đó, nếu ở đầu - O(N). Chà, nếu cuối cùng là O(1) thì không cần phải di chuyển gì cả. Đối với những người muốn tìm hiểu sâu hơn về chủ đề này, tôi sẽ để lại liên kết này đến một bài viết có phân tích về lớp ArrayList .

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

Nếu ArrayList chứa các phần tử trong một mảng bên trong thì LinkedList ở dạng 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 đó ( previous ) và phần tử tiếp theo ( next ). Phần tử đầu tiên không có liên kết đến phần tử trước đó (nó là phần tử đầu tiên), nhưng nó được coi là phần tử đứng đầu danh sách và LinkedList có liên kết trực tiếp đến phần tử đó. Trên thực tế, phần tử cuối cùng không có phần tử tiếp theo, nó là phần cuối của danh sách và do đó có một liên kết trực tiếp đến nó trong chính LinkedList . Do đó, độ phức tạp logarit 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, khi danh sách tăng lên, mảng bên trong cũng tăng lên, nhưng ở đây mọi thứ diễn ra đơn giản hơn - khi thêm một phần tử, một vài liên kết chỉ cần thay đổi. Hãy xem xét một số phương thức LinkedlList được sử dụng nhiều nhất : 1. add(<Element>) - thêm 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 dưới dạng next . Phần tử mới sẽ có liên kết đến phần tử cuối cùng (5) như phần tử trước đó . Độ phức tạp logarit của một thao tác như vậy sẽ là O(1), vì chỉ cần một liên kết đến phần tử cuối cùng và như bạn nhớ, phần đuôi có một liên kết trực tiếp từ LinkedList và độ phức tạp logarit khi truy cập nó là tối thiểu. 2. add(<Index>,<Element>) - thêm một phần tử theo chỉ mục. Ví dụ: khi thêm một phần tử vào giữa danh sách, các phần tử ở đầu và đuôi (ở cả hai bên) trước tiên được lặp lại cho đến khi tìm thấy vị trí mong muốn. Nếu chúng ta muốn chèn một phần tử vào giữa phần tử thứ ba và thứ tư (trong hình trên), thì khi tìm kiếm đúng vị trí, liên kết tiếp theo của phần tử thứ ba sẽ trỏ đến phần tử mới. Đối với cái mới, liên kết trước đó sẽ trỏ đến cái thứ ba. Theo đó, liên kết của phần tử thứ tư - trước đó - 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ư: Độ phức tạp logarit của phương pháp này sẽ phụ thuộc vào chỉ mục được cung cấp cho phần tử mới:

• nếu nó ở gần đầu hoặc đuôi, nó 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ì O(N/2) - các phần tử từ đầu và đuôi sẽ được sắp xếp đồng thời cho đến khi tìm thấy phần tử cần thiết.

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 logarit 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ử với đầu, đuôi hoặc giữa. 4. Remove(<index>) - xóa một phần tử khỏi danh sách, về cơ bản là làm cho phần tử đứng trước phần tử bị xóa ( previous ) tham chiếu đến phần tử đứng sau phần tử bị xóa ( next ). Và ngược lại: để phần tử xuất hiện sau phần tử bị xóa đề cập đến phần tử xuất hiện trước phần tử bị xóa: Kết quả là một quá trình nghịch đảo với việc thêm theo chỉ mục ( add(<Index>,<Element>) ). Đối với những ai muốn tìm hiểu thêm về cấu trúc bên trong của LinkedList , tôi khuyên bạn nên đọc bài viết này .

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

Có lẽ một trong những câu hỏi phổ biến nhất khi phỏng vấn một nhà phát triển Java. HashMap v hoạt động với các cặp khóa-giá trị . Chúng được lưu trữ bên trong HashMapv như thế nào ? Bên trong HashMap có một loạt các nút:

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 lần khi nó chứa đầy các phần tử (khi đạt đến LOAD_FACTOR - một tỷ lệ phần trăm đầy đủ nhất định, 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à liên kết đến phần tử tiếp theo: Trên thực tế, “liên kết đế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 cai tiêp theo. Nghĩa là, HashMap lưu trữ dữ liệu trong một mảng các danh sách liên kết đơn lẻ. Nhưng tôi sẽ lưu ý ngay: khi một ô của mảng bảng có liên kết đến một danh sách liên kết đơn tương tự bao gồm nhiều hơn một phần tử, điều này 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, hachCode() của khóa được lấy. Do đó, để hashmap hoạt động chính xác , bạn cần lấy các lớp trong đó phương thức này được ghi đè làm khóa. Mã băm này sau đó được sử dụng trong phương thức nội bộ - hash() - để xác định số trong kích thước của mảng bảng . Tiếp theo, bằng cách sử dụng số nhận được, một ô cụ thể của mảng bảng sẽ được truy cập . Ở đây chúng ta có hai trường hợp:

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

Khi tìm kiếm một phần tử theo khóa ( phương thức get(<key>) ), hashCode của khóa được tính toán, sau đó giá trị của nó trong mảng bằng cách sử dụng hash() và sử dụng số kết quả, ô của mảng bảng sẽ được tìm thấy , trong đó việc tìm kiếm đã được thực hiện bằng cách liệt kê 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. Các thao tác trong Bản đồ trong tình huống lý tưởng có độ phức tạp về mặt thuật toán là O(1), vì chúng đang truy cập vào một mảng và như bạn nhớ, bất kể số phần tử là bao nhiêu, các thao tác trên một mảng đều có độ phức tạp là O(1). Nhưng điều này là lý tưởng. Khi ô mảng đang được sử dụng không trống (2) và đã có một số nút ở đó, độ phức tạp thuật toán sẽ chuyển 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 tìm đúng vị trí. Tôi không thể không đề cập đến điều này: bắt đầu từ Java 8, nếu một nút danh sách liên kết đơn có nhiều hơn 8 phần tử (va chạm), nó sẽ biến thành cây nhị phân. Trong trường hợp này, độ phức tạp thuật toán sẽ không còn là O(N) nữa mà là O(log(N)) - đó lại 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. Vì vậy, tôi khuyên bạn nên hiểu nó một cách chi tiết (để nó bật ra khỏi răng của bạn). Cá nhân tôi chưa có cuộc phỏng vấn nào mà không có câu hỏi về HashMap . Bạn có thể tìm hiểu sâu hơn về HashMap trong bài viết này . Hôm nay chỉ vậy thôi, còn tiếp tục...