Họ có thể hỏi gì khi phỏng vấn: Cấu trúc dữ liệu trong Java. Phần 2

PHẦN 1 Bây giờ chúng ta đang nói về nền tảng mà mọi nhà phát triển Java nên biết. Về kiến ​​thức cổ điển mà từ đó mọi chuyện bắt đầu. Hôm nay tôi muốn đề cập đến một trong những chủ đề cơ bản của bất kỳ cuộc phỏng vấn nào - cấu trúc dữ liệu trong Java . Vì vậy, thay vì quanh co, hãy bắt đầu. Nắm bắt phần tiếp theo của danh sách các câu hỏi mà bạn có thể được hỏi về chủ đề này trong một cuộc phỏng vấn.

6. Hãy cho chúng tôi biết về Danh sách

Danh sách là một giao diện thể hiện cấu trúc có thứ tự của các đối tượng, được gọi là danh sách. “Thủ thuật” của cấu trúc này là các phần tử chứa trong List có thể được chèn, sửa đổi hoặc xóa theo chỉ mục, tức là mã định danh bên trong của List . Nói cách khác, chỉ mục có nghĩa là: “có bao nhiêu phần tử tính từ đầu danh sách”. Phần tử Danh sách đầu tiên có chỉ mục 0, phần tử thứ hai có chỉ mục 1, v.v. Vì vậy, phần tử thứ năm cách đầu danh sách bốn phần tử. Như đã đề cập ở trên, thứ tự các mục được thêm vào danh sách rất quan trọng. Đó là lý do tại sao cấu trúc dữ liệu được gọi là danh sách . Chúng tôi liệt kê các phương thức duy nhất cho cấu trúc này nhằm mục đích làm việc với các phần tử theo chỉ mục:

• get - trả về phần tử tại vị trí đã chỉ định (theo giá trị chỉ mục),
• loại bỏ - loại bỏ phần tử tại vị trí đã chỉ định,
• set - thay thế phần tử tại vị trí đã chỉ định bằng phần tử được chỉ định trong phương thức.

Việc triển khai chính là ArrayList và LinkedList . Chúng ta sẽ nói nhiều hơn về họ sau. Vector là một danh sách an toàn theo luồng, vì vậy mỗi phương thức trong lớp này đều được đồng bộ hóa. Nhưng hãy nhớ rằng nếu bạn muốn bảo mật một số hành động trong danh sách, bạn sẽ đồng bộ hóa toàn bộ chuỗi hoạt động. Và việc đồng bộ hóa các hoạt động riêng lẻ vừa kém an toàn vừa chậm hơn nhiều. Tất nhiên, Vector cũng có tính năng khóa trên cao, ngay cả khi bạn không cần khóa. Vì vậy, lớp này hiện được coi là lỗi thời và không được sử dụng. Nhân tiện: ArrayList tương tự như Vector , nhưng không sử dụng khóa nên nó được sử dụng ở mọi nơi. Stack là một lớp con của lớp Vector với một hàm tạo mặc định và tất cả các phương thức của lớp Vector , cộng thêm một số phương thức của chính nó (chúng ta sẽ nói về chúng sau). Ví dụ: bạn có thể tưởng tượng quy trình này như một chồng các thư mục chứa tài liệu. Bạn đặt một thư mục ở đầu ngăn xếp và bạn chỉ có thể lấy các thư mục này theo thứ tự ngược lại, bắt đầu từ trên cùng. Thực ra đây là cơ chế kiểu LIFO , tức là Last In First Out , người đến sau là người về trước. Ngăn xếp thực hiện các phương thức riêng của nó:

• đẩy - thêm phần tử đã truyền vào đầu ngăn xếp;
• nhìn trộm - trả về phần tử ở đầu ngăn xếp;
• pop - cũng trả về phần tử ở đầu ngăn xếp, nhưng loại bỏ nó;
• trống - kiểm tra xem ngăn xếp có trống không - đúng hay không - sai ;
• tìm kiếm - tìm kiếm ngăn xếp cho một phần tử nhất định. Nếu tìm thấy một phần tử, số thứ tự của nó so với đỉnh ngăn xếp sẽ được trả về. Nếu không tìm thấy phần tử thì trả về giá trị -1.

Hiện tại, lớp con Stack không thực sự được sử dụng do tính đơn giản và thiếu linh hoạt của nó, tuy nhiên, bạn có thể gặp phải nó. Ví dụ: khi bạn gặp một số lỗi và trong bảng điều khiển, bạn sẽ thấy một loạt thông báo về lỗi đó. Bạn có thể đọc thêm về ngăn xếp và hàng đợi trong bài viết này .

7. Hãy cho chúng tôi biết về Bản đồ

Như đã nêu ở trên, Bản đồ là một bộ sưu tập có cấu trúc giao diện riêng biệt và cách triển khai chúng. Nó tách biệt vì ở đây các giá trị không được lưu trữ từng giá trị một mà theo cặp “khóa-giá trị”. Các phương pháp bản đồ cơ bản :

• put(K key, V value) - thêm một phần tử vào Bản đồ;
• get(Object key) - tìm kiếm giá trị theo khóa;
• containsKey(Object key) - kiểm tra Bản đồ xem có khóa này không;
• containsValue(Object value) - kiểm tra Bản đồ xem có giá trị này không;
• Remove(Object key) - xóa một giá trị bằng khóa của nó.

Như bạn có thể thấy, hầu hết các thao tác đều hoạt động bằng cách sử dụng một phím. Theo quy định, các đối tượng bất biến được chọn làm khóa . Một ví dụ điển hình của đối tượng này là String . Triển khai bản đồ cơ bản :

1. HashMap - được thiết kế để lưu trữ các giá trị theo thứ tự ngẫu nhiên nhưng cho phép bạn nhanh chóng tìm kiếm các thành phần bản đồ. Cho phép bạn chỉ định một khóa bằng từ khóa null , nhưng không quá một lần, bởi vì các cặp có cùng khóa được viết chồng lên nhau. Điều kiện chính là tính duy nhất của các khóa: các giá trị có thể được lặp lại (có thể có một số giá trị null).
2. LinkedHashMap là một dạng tương tự của HashMap , lưu trữ các giá trị theo thứ tự chúng được thêm vào. Theo đó, giống như LinkedList , nó có tiêu đề - phần đầu của danh sách liên kết đôi. Khi khởi tạo, nó trỏ về chính nó.

   LinkedHashMap cũng có accessOrder chỉ định cách truy cập các phần tử khi sử dụng trình vòng lặp. Nếu accessOrder sai, quyền truy cập sẽ được thực hiện theo thứ tự các phần tử được chèn vào. Nếu đúng, các phần tử sẽ theo thứ tự được truy cập lần cuối (phần tử được truy cập lần cuối sẽ được đặt ở cuối).

3. TreeMap là Bản đồ sắp xếp các phần tử theo giá trị chính. Tương tự như TreeSet nhưng dành cho các cặp dựa trên giá trị khóa. Để đặt quy tắc sắp xếp TreeMap , các khóa phải triển khai giao diện Comparable . Mặt khác, cần có một Bộ so sánh hướng khóa (cái được chỉ định trong hàm tạo TreeMap ), một TreeSet - được triển khai với một đối tượng TreeMap bên trong, trong đó, trên thực tế, tất cả điều kỳ diệu đều xảy ra.

   Bạn có thể đọc thêm về cách sắp xếp trong TreeMap bằng cây đỏ đen trong bài viết về các tính năng của TreeMap .

4. Hashtable tương tự như HashMap , nhưng không cho phép lưu trữ null dưới dạng khóa hoặc giá trị. Nó được đồng bộ hóa cẩn thận theo quan điểm đa luồng, điều này có nghĩa là nó an toàn theo quan điểm đa luồng. Nhưng việc triển khai này đã lỗi thời và chậm, vì vậy bây giờ bạn sẽ không thấy Hashtable trong ít nhiều các dự án mới.

8. ArrayList và LinkedList. Cái nào thích hợp hơn để sử dụng?

Câu hỏi này có lẽ là câu hỏi phổ biến nhất về cấu trúc dữ liệu và mang theo một số cạm bẫy. Trước khi trả lời, chúng ta hãy tìm hiểu thêm về các cấu trúc dữ liệu này. ArrayList triển khai giao diện Danh sách và hoạt động trên một mảng bên trong được mở rộng khi cần. Khi mảng bên trong được lấp đầy hoàn toàn và cần chèn một phần tử mới, một mảng mới sẽ được tạo với kích thước (oldSize * 1.5) +1. Sau đó, tất cả dữ liệu từ mảng cũ sẽ được sao chép sang phần tử mới + mới và dữ liệu cũ sẽ bị trình thu gom rác xóa . Phương thức add thêm một phần tử vào ô trống cuối cùng của mảng. Nghĩa là, nếu chúng ta đã có 3 phần tử ở đó, nó sẽ thêm phần tử tiếp theo vào ô thứ 4. Chúng ta hãy xem xét hiệu suất của các phương pháp cơ bản:

• get(int index) - lấy một phần tử trong mảng theo chỉ mục là nhanh nhất trong O(1) ;
• add(Object obj) - nếu có đủ không gian trong mảng bên trong cho một phần tử mới, thì thời gian chèn O(1) bình thường sẽ được sử dụng , vì phần bổ sung được nhắm mục tiêu đến ô cuối cùng.

  Nếu chúng ta cần tạo một mảng mới và sao chép nội dung vào đó thì thời gian của chúng ta sẽ tỉ lệ thuận với số phần tử trong mảng O(n) ;

• Remove(int index) - khi xóa một phần tử, chẳng hạn như ở giữa, chúng ta sẽ nhận được thời gian O(n/2), vì chúng ta sẽ cần di chuyển các phần tử sang bên phải của nó trở lại một ô. Theo đó, nếu xóa từ đầu danh sách thì O(n), từ cuối - O(1);
• add(int index, Object obj) - một tình huống tương tự như xóa: khi thêm vào giữa, chúng ta sẽ cần di chuyển các phần tử ở bên phải về phía trước một ô, nên thời gian là O(n/2). Tất nhiên, ngay từ đầu - O(n), từ cuối - O(1);
• set(int index, Object obj) - ở đây tình huống lại khác, vì bạn chỉ cần tìm phần tử mong muốn và viết lên nó mà không di chuyển phần còn lại, vì vậy O(1).

Đọc thêm về ArrayList trong bài viết này . LinkedList triển khai hai giao diện cùng một lúc - Danh sách và Hàng đợi , do đó có các thuộc tính và phương thức vốn có trong cả hai cấu trúc dữ liệu. Từ Danh sách, anh ấy có quyền truy cập vào một phần tử theo chỉ mục, từ Hàng đợi - sự hiện diện của “đầu” và “đuôi”. Trong nội bộ, nó được triển khai dưới dạng cấu trúc dữ liệu đại diện cho danh sách liên kết đôi. Nghĩa là, mỗi phần tử đều có một liên kết đến phần tử tiếp theo và phần tử trước đó, ngoại trừ phần “đuôi” và “phần đầu”.

• get(int index) - khi tìm kiếm một phần tử ở giữa danh sách, nó bắt đầu tìm kiếm qua tất cả các phần tử theo thứ tự cho đến khi tìm thấy phần tử mong muốn. Về mặt logic, việc tìm kiếm sẽ mất O(n/2) , nhưng LinkedList cũng có đuôi, do đó việc tìm kiếm được thực hiện đồng thời từ cả hai phía. Theo đó, thời gian giảm xuống còn O(n/4) .

  Nếu phần tử ở gần đầu hoặc cuối danh sách thì thời gian sẽ là O(1) ;

• add(Object obj) - khi thêm một phần tử mới, phần tử “đuôi” sẽ có liên kết đến phần tử tiếp theo được thêm vào, phần tử mới sẽ nhận được liên kết đến phần tử trước đó và trở thành “đuôi” mới. Theo đó, thời gian sẽ là O(1) ;
• Remove(int index) - logic tương tự như phương thức get(int index) . Để xóa một phần tử khỏi giữa danh sách, trước tiên bạn phải tìm nó. Đây lại là O(n/4) , trong khi việc xóa thực sự không mất gì, vì nó chỉ thay đổi con trỏ của các đối tượng lân cận (chúng bắt đầu tham chiếu lẫn nhau). Nếu phần tử ở đầu hoặc cuối thì - O(1) ;
• add(int index, Object obj) và set(int index, Object obj) - các phương thức sẽ có độ phức tạp về thời gian giống hệt get(int index) , vì phần lớn thời gian được dành cho việc tìm kiếm phần tử. Do đó, ở giữa danh sách - O(n/4) , ở đầu danh sách - O(1).

Thông tin thêm về cách làm việc với LinkedList được mô tả trong bài viết này . Chúng ta hãy xem xét tất cả điều này trong một bảng: Như bạn có thể đã hiểu, không thể trả lời câu hỏi này một cách rõ ràng. Rốt cuộc, trong những tình huống khác nhau, chúng hoạt động ở tốc độ khác nhau. Vì vậy, khi được hỏi một câu hỏi như thế này, bạn nên hỏi ngay danh sách này sẽ tập trung vào điều gì và những thao tác nào sẽ được thực hiện thường xuyên nhất. Bắt đầu từ đây, hãy đưa ra câu trả lời nhưng kèm theo lời giải thích tại sao lại như vậy. Hãy tóm tắt so sánh của chúng tôi: ArrayList:

• sự lựa chọn tốt nhất nếu thao tác thường xuyên nhất là tìm kiếm một phần tử, ghi đè một phần tử;
• sự lựa chọn tồi tệ nhất nếu thao tác chèn và xóa ở đầu-giữa, vì thao tác dịch chuyển của các phần tử bên phải sẽ diễn ra.

Danh sách liên kết:

• sự lựa chọn tốt nhất nếu hoạt động thường xuyên của chúng tôi là chèn và xóa ở đầu-giữa;
• lựa chọn tồi tệ nhất nếu hoạt động phổ biến nhất là tìm kiếm.

9. Các phần tử được lưu trữ trong HashMap như thế nào?

Bộ sưu tập HashMap chứa một bảng Node[] mảng bên trong , các ô của bảng này còn được gọi là nhóm . Nút chứa:

• chìa khóa - liên kết đến chìa khóa,
• giá trị - tham chiếu đến giá trị,
• hàm băm - giá trị băm,
• tiếp theo - liên kết tới Nút tiếp theo .

Một ô của mảng table[] có thể chứa tham chiếu đến một đối tượng Node có liên kết đến phần tử Node tiếp theo và nó có thể có liên kết đến một phần tử khác, v.v... Kết quả là, các phần tử Node này có thể tạo thành một danh sách liên kết đơn , với các phần tử có liên kết tới phần tiếp theo. Trong trường hợp này, giá trị băm của các phần tử trong cùng một chuỗi là như nhau. Sau một hồi lạc đề ngắn, hãy xem cách các phần tử được lưu trữ trong HashMap :

1. Khóa được kiểm tra null . Nếu là null thì khóa sẽ được lưu trong ô của bảng[0] vì mã băm cho null luôn là 0.
2. Nếu khóa không phải là null thì phương thức hashcode() của đối tượng khóa sẽ được gọi , phương thức này sẽ trả về mã băm của nó. Mã băm này được sử dụng để xác định ô mảng nơi đối tượng Node sẽ được lưu trữ.
3. Tiếp theo, mã băm này được đặt trong phương thức hash() bên trong để tính toán mã băm nhưng trong phạm vi kích thước của mảng table[] .
4. Tiếp theo, tùy thuộc vào giá trị băm, Node được đặt trong một ô cụ thể trong mảng table[] .
5. Nếu ô bảng [] được sử dụng để lưu phần tử Nút hiện tại không trống nhưng đã có một số phần tử thì các phần tử Nút sẽ được lặp qua giá trị tiếp theo cho đến khi đạt đến phần tử cuối cùng. Tức là trường có trường tiếp theo là null .

   Trong quá trình tìm kiếm này, khóa của đối tượng Node được bảo vệ được so sánh với khóa của đối tượng đang được tìm kiếm:

   • nếu tìm thấy kết quả khớp, tìm kiếm sẽ kết thúc và Nút mới sẽ ghi đè Nút trong đó tìm thấy kết quả khớp (chỉ trường giá trị của nó sẽ bị ghi đè );
   • nếu không tìm thấy khóa nào phù hợp thì Nút mới sẽ trở thành Nút cuối cùng trong danh sách này và Nút trước đó sẽ có liên kết tiếp theo với nó.

Câu hỏi thường xuất hiện trong các cuộc phỏng vấn: xung đột là gì ? Tình huống khi một ô của mảng table[] lưu trữ không phải một phần tử mà là một chuỗi gồm hai phần tử trở lên, được gọi là xung đột . Trong các trường hợp thông thường khi chỉ có một phần tử được lưu trữ trong một ô bảng [] , việc truy cập các phần tử của HashMap có độ phức tạp về thời gian là O(1) không đổi . Nhưng khi một ô có phần tử mong muốn chứa một chuỗi phần tử ( va chạm ), thì O(n) , vì trong trường hợp này thời gian tỷ lệ thuận với số phần tử được sắp xếp.

10. Giải thích iterator

Trong sơ đồ ánh xạ phân cấp Bộ sưu tập ở trên, giao diện Bộ sưu tập là nơi bắt đầu toàn bộ hệ thống phân cấp, nhưng trên thực tế, nó không hoàn toàn như vậy. Bộ sưu tập kế thừa từ một giao diện có phương thức iterator() , phương thức này trả về một đối tượng triển khai giao diện Iterator<E> . Giao diện Iterator trông như thế này:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - bằng cách gọi phương thức này, bạn có thể lấy phần tử tiếp theo. hasNext() - cho phép bạn tìm hiểu xem có phần tử tiếp theo hay không và liệu đã đạt đến phần cuối của bộ sưu tập chưa. Và khi vẫn còn phần tử, hasNext() sẽ trả về true . Thông thường, hasNext() được gọi trước phương thức next() vì next() sẽ ném ra ngoại lệ NoSuchElementException khi nó đến cuối bộ sưu tập . Remove() - Xóa phần tử đã được truy xuất trong lần gọi cuối cùng tới next() . Mục đích của Iterator là lặp lại các phần tử. Ví dụ:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Trên thực tế, vòng lặp for-each được triển khai bên trong bằng cách sử dụng một trình vòng lặp. Bạn có thể đọc thêm về điều này ở đây . List cung cấp phiên bản iterator riêng của nó, nhưng một phiên bản thú vị hơn và phức tạp hơn - ListIterator . Giao diện này mở rộng Iterator và có các phương thức bổ sung:

• hasPrevious sẽ trả về true nếu có phần tử trước đó trong bộ sưu tập, ngược lại là false;
• trước trả về phần tử hiện tại và di chuyển về phần tử trước đó; nếu không có thì ngoại lệ NoSuchElementException sẽ được ném ra;
• add sẽ chèn đối tượng đã truyền vào trước phần tử được trả về trong lệnh gọi tiếp theo tới next() ;
• set gán cho phần tử hiện tại một tham chiếu đến đối tượng được truyền;
• nextIndex trả về chỉ mục của phần tử tiếp theo. Nếu không có thứ đó thì kích thước của danh sách sẽ được trả về;
• previousIndex trả về chỉ mục của phần tử trước đó. Nếu không có thì trả về số -1.

Vâng, đó là tất cả đối với tôi ngày hôm nay. Tôi hy vọng rằng sau khi đọc bài viết này, bạn thậm chí còn tiến gần hơn đến ước mơ ấp ủ của mình - trở thành một nhà phát triển.