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 10

Xin chào! Mất bao nhiêu giờ để trở thành bậc thầy ở một lĩnh vực nào đó? Tôi thường nghe những câu như: “Để trở thành bậc thầy trong bất cứ việc gì, bạn cần phải dành 10.000 giờ”. Một con số đáng sợ phải không? Tuy nhiên, tôi tự hỏi liệu điều này có đúng không? Và tôi không ngừng cố gắng tính xem mình đã đầu tư bao nhiêu giờ để thành thạo nghệ thuật lập trình. Và khi tôi vượt qua 10.000 giờ ấp ủ đó và trở thành bậc thầy, liệu tôi có cảm nhận được sự khác biệt này không? Hay tôi đã bước qua chúng từ lâu rồi mà không nhận ra? Bằng cách này hay cách khác, để trở thành một lập trình viên, bạn không cần phải đầu tư một lượng thời gian lớn như vậy. Điều chính là sử dụng nó một cách khôn ngoan. Mục tiêu chính của bạn là vượt qua cuộc phỏng vấn. Và khi phỏng vấn người mới, điều đầu tiên họ hỏi là lý thuyết nên bạn phải giỏi về nó. Thực ra, khi chuẩn bị cho buổi phỏng vấn, nhiệm vụ của bạn là khám phá mọi lỗ hổng về lý thuyết cơ bản của một nhà phát triển Java và khắc phục chúng bằng kiến ​​thức. Và hôm nay tôi sẽ giúp bạn trong vấn đề này, vì tôi ở đây để tiếp tục phân tích những câu hỏi phổ biến nhất. Vậy chúng ta hãy tiếp tục!

89. ArrayList khác với LinkedList như thế nào?

Đây là một trong những câu hỏi được nhiều người thắc mắc cùng với câu hỏi về cấu trúc bên trong của HashMap . Không một cuộc phỏng vấn nào là hoàn thành nếu không có nó, và do đó, câu trả lời cho nó sẽ khiến bạn “khó chịu”. Ngoài những điều hiển nhiên - những cái tên khác nhau - chúng còn khác nhau về cấu trúc bên trong. Trước đây, chúng ta đã xem xét 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 cách triển khai chúng. Hãy để tôi nhắc bạn rằng ArrayList được triển khai dựa trên một mảng bên trong, mảng này sẽ được tăng lên khi cần thiết theo công thức:

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

Đồng thời, LinkedList được triển khai dựa trên danh sách liên kết đôi nội bộ, tức là mỗi phần tử có một liên kết đến phần trước và phần tử tiếp theo, loại trừ các giá trị đầu/cuối danh sách. Mọi người thích đặt câu hỏi này theo dạng: “Cái nào tốt hơn - ArrayList hay LinkedList ?”, Hy vọng sẽ hiểu được bạn. Suy cho cùng, nếu bạn chỉ vào một trong số đó làm câu trả lời thì đó sẽ là câu trả lời sai. Thay vào đó, bạn nên làm rõ tình huống cụ thể mà bạn đang nói đến - truy cập chỉ mục hoặc chèn vào giữa danh sách. Tùy thuộc vào câu trả lời, bạn sẽ có thể giải thích sự lựa chọn của mình. Trước đây tôi đã mô tả cách ArrayList và LinkedList hoạt động trong tình huống này hay tình huống khác. Hãy tóm tắt điều này bằng cách đặt chúng trên cùng một trang để so sánh: Thêm một phần tử (thêm)

1. Добавление нового element без указания индекса How местоположения будет происходить автоматически в конец обоих списков. В LinkedList новый элемент станет новым хвостом (происходит только перезаписывание пары ссылок — алгоритмическая сложность O(1)).

   В ArrayList будет добавлен новый элемент в последнюю пустую ячейку массива — O(1).

2. Добавление element по индексу How правило подразумевает вставку примерно в середину списка. В LinkedList сперва будет вестись поиск нужного места с помощью перебора элементов с “хвоста” и “головы” — O(n/2), а после — вставка значения путем переопределения ссылок элементов, между которыми вставляется новый — O(1). Суммарная алгоритмическая сложность данного действия будет O(n/2).

   ArrayList в данной ситуации по индексу находит элемент — O(1), и все элементы справа (включая элемент, который уже хранится по данному индексу) двигаются на одну единицу вправо (при этом возможно понадобится создание нового списка и копирование элементов в него) — O(n/2). Суммарная сложность — O(n/2).

3. Добавление element в начало списка в LinkedList будет ситуация схожая с добавлением в конец: новый элемент станет новой “головой” — O(1), в то же время когда ArrayList-у нужно будет двигать все элементы вправо — O(n).

Điểm mấu chốt: trong LinkedList, độ phức tạp của thuật toán sẽ nằm trong khoảng từ O(1) đến O(n/2) . Nghĩa là, việc chèn càng gần cuối hoặc đầu danh sách thì càng nhanh. Đồng thời, đối với ArrayList , nó nằm trong khoảng từ O(1) đến O(n) : việc chèn càng gần cuối danh sách thì càng nhanh. Thiết lập một phần tử (bộ) Thao tác này ghi một phần tử vào vị trí đã chỉ định trong danh sách, ghi đè phần tử trước đó, nếu có. Trong LinkedList, thao tác này sẽ tương tự như việc cộng, vì Khó khăn lớn nhất ở đây là tìm ra nguyên tố. Việc viết lại một phần tử sẽ diễn ra bằng cách viết lại một cặp liên kết, do đó, ở đây độ phức tạp thuật toán sẽ nằm trong khoảng từ O(1) đến O(n/2) tùy thuộc vào khoảng cách của vị trí từ cuối hoặc đầu danh sách. Vào thời điểm đó, ô cần thiết sẽ được tìm thấy trong ArrayList cho thao tác chỉ mục này và một phần tử mới sẽ được ghi vào ô đó. Tìm kiếm chỉ mục, giống như thao tác này, có độ phức tạp thuật toán là O(1) . Lấy một phần tử theo chỉ mục (get) Trong LinkedList, việc lấy một phần tử sẽ diễn ra theo nguyên tắc giống như tìm kiếm các thao tác khác - tùy thuộc vào khoảng cách từ đầu hoặc cuối, tức là. từ O(1) đến O(n/2) . Trong ArrayList , như tôi đã nói trước đó, việc tìm một phần tử trong một mảng theo chỉ mục có độ phức tạp O(1) . Xóa một phần tử theo chỉ mục (remove) Đối với LinkedList , nguyên tắc hoạt động của nó cũng hoạt động ở đây: đầu tiên phần tử được tìm thấy, sau đó các liên kết bị ghi đè - các phần tử lân cận của phần tử bắt đầu tham chiếu lẫn nhau, mất tham chiếu đến phần tử này, sau đó sẽ bị xóa bởi người thu gom rác. Nghĩa là, độ phức tạp của thuật toán vẫn giữ nguyên - từ O(1) đến O(n/2) . Đối với ArrayList , thao tác này giống với thao tác thêm một phần tử mới (add) hơn. Đầu tiên, phần tử bắt buộc được tìm thấy - O(1) , sau đó nó bị xóa và tất cả các phần tử ở bên phải của nó được di chuyển sang trái một đơn vị để thu hẹp khoảng cách kết quả. Thao tác xóa sẽ có độ phức tạp về thuật toán tương tự như thao tác thêm - từ O(1) đến O(n) . Việc xóa càng gần cuối danh sách thì độ phức tạp về mặt thuật toán càng ít. Trên thực tế, đây đều là những hoạt động chính. Để tôi nhắc bạn: khi so sánh hai danh sách này, bạn cần làm rõ tình huống cụ thể mà chúng ta đang nói đến là gì, từ đó bạn mới có thể trả lời rõ ràng câu hỏi được đặt ra.

90. ArrayList khác với HashSet như thế nào?

Nếu ArrayList và LinkedList có thể được so sánh về mặt hoạt động - tốt hơn - thì không dễ để so sánh ArrayList với HashSet , vì đây là những bộ sưu tập hoàn toàn khác nhau. Bạn có thể so sánh món ngọt này với món ngọt khác, nhưng nó sẽ hiệu quả với món thịt - chúng quá khác nhau. Tuy nhiên, tôi sẽ cố gắng đưa 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 ;

• Trong ArrayList, có thể truy cập theo chỉ mục phần tử: thao tác get có độ phức tạp về mặt thuật toán là O(1) và trong HashSet , phần tử được yêu cầu chỉ có thể được lấy bằng bạo lực và đây là 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: việc thêm một phần tử vào HashSet có phần tử tương tự đã có trong bộ sưu tập sẽ không hoạt độ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ộ và 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ử, trong khi HashSet là tập hợp không có thứ tự và không duy trì thứ tự của các phần tử;

• ArrayList cho phép bất kỳ số lượng giá trị trống (null), chỉ có thể chèn một giá trị null vào HashSet (xét cho cùng là tính duy nhất của các phần tử).

91. Tại sao có nhiều cách triển khai mảng động như vậy trong Java?

Vâng, đây là một câu hỏi triết học nhiều hơn. Chà, tại sao họ lại nghĩ ra nhiều công nghệ mới khác nhau như vậy? Để thoải mái. Trên thực tế, điều này cũng tương tự với một số lượng lớn cách triển khai mảng động. Không ai trong số họ có thể được gọi là tốt nhất hoặc lý tưởng. Mỗi người đều có một lợi thế trong một số tình huống cụ thể. Và nhiệm vụ của chúng ta là phải biết sự khác biệt, điểm mạnh/điểm yếu của họ: để có thể sử dụng cái phù hợp nhất trong đúng hoàn cảnh.

92. Tại sao lại có nhiều cách triển khai lưu trữ khóa-giá trị như vậy trong Java?

Ở đây tình huống cũng giống như khi triển khai mảng động. Không có ai giỏi nhất: mỗi ngườ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 thế mạnh của mình. Ví dụ: gói đồng thời chứa nhiều công nghệ đa luồng, có các bộ sưu tập Đồng thời riêng . ConcurrentHashMap tương tự có lợi thế hơn về tính an toàn khi làm việc đa luồng với dữ liệu so với HashMap thông thường , nhưng trong môi trường không đa luồng, nó sẽ mất tốc độ. Chà, những triển khai không phải là mạnh nhất trong mọi tình huống, 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 , nhưng ConcurrentHashMap đã vượt trội hơn nó trong môi trường đa luồng và Hashtable cuối cùng đã bị lãng quên và không còn được sử dụng nữa.

93. Làm thế 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 phần tử bộ sưu tập phải triển khai giao diện Comparable và phương thức so sánh của nó . Hoặc bạn cần một lớp triển khai Comaprator với phương thức so sánh của nó . Bạn có thể đọc thêm về họ trong bài viết này . Cả hai phương pháp đều chỉ định cách so sánh các đối tượng của một loại nhất định. Khi sắp xếp, điều này cực kỳ quan trọng vì bạn cần hiểu nguyên tắc mà các phần tử có thể được so sánh. Cách chính để thực hiện việc này là triển khai Comparable , được triển khai trực tiếp trong lớp bạn muốn sắp xếp. Đồng thời, việc sử dụng Comparator ít phổ biến hơn. Giả sử bạn đang sử dụng một lớp từ một thư viện nào đó không có triển khai Comparable nhưng bạn sẽ cần sắp xếp nó bằng cách nào đó. Nếu không thể thay đổi mã của lớp này (ngoại trừ bằng cách mở rộng nó), bạn có thể viết một triển khai Comparator , trong đó bạn chỉ ra nguyên tắc nào bạn muốn so sánh các đối tượng của lớp này. Và một ví dụ nữa. Giả sử bạn cần các nguyên tắc khác nhau để sắp xếp các đối tượng cùng loại, vì vậy bạn viết một số Bộ so sánh mà bạn sử dụng trong các tình huống khác nhau. Theo quy định, nhiều lớp sẵn có đã triển khai giao diện Comparable - cùng một String . Thực ra, khi sử dụng chúng, bạn không phải lo lắng về việc so sánh chúng như thế nào. Bạn chỉ cần lấy chúng và sử dụng chúng. Cách đầu tiên và rõ ràng nhất là sử dụng một bộ sưu tập như TreeSet hoặc TreeMap , lưu trữ các phần tử theo thứ tự đã được sắp xếp theo bộ so sánh lớp phần tử. Hãy nhớ rằng TreeMap sắp xếp các khóa chứ không phải các giá trị. Nếu bạn sử dụng triển khai Comparator thay vì Comparable , bạn sẽ cần chuyển đối tượng của nó cho hàm tạo bộ sưu tập khi tạo:

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? Làm thế nào để sắp xếp nó? Trong trường hợp này, phương thức thứ hai của lớp tiện ích Bộ sưu tập là phù hợp - phương thức Sort() . Nó là tĩnh, vì vậy tất cả những gì bạn cần là tên của lớp và một phương thức mà danh sách bắt buộc được chuyển vào. Ví dụ:

Collections.sort(someList);

Nếu bạn không sử dụng Comparable mà thay vào đó là triển khai Comparator , bạn cần chuyển nó làm tham số thứ hai:

Collections.sort(someList, customComparator);

Kết quả là thứ tự bên trong của các phần tử trong danh sách được truyền sẽ thay đổi: nó sẽ được sắp xếp theo bộ so sánh phần tử. Tôi lưu ý rằng danh sách các phần tử được chuyển phải có thể thay đổi được, tức là có thể thay đổi, nếu không phương thức sẽ không hoạt động và một ngoại lệ UnsupportedOperationException sẽ được ném ra . Theo cách thứ ba , bạn có thể sử dụng thao tác Sắp xếp luồng để sắp xếp các thành phần của bộ sưu tập nếu sử dụng triển khai Comparable :

someList = someList.stream().sorted().collect(Collectors.toList());

nếu Bộ so sánh :

someList = someList.stream().sorted(customComparator).collect(Collectors.toList());

Bạn có thể đọc thêm về Stream trong bài viết này . Phương pháp thứ tư là triển khai sắp xếp theo cách thủ công, chẳng hạn như sắp xếp bong bóng hoặc sắp xếp hợp nhất .

LớpObject. Bằng và HashCode

94. Đưa ra mô tả ngắn gọn về đối tượng lớp trong Java

Trong phần phân tích thứ hai, chúng ta đã nói về các phương thức của lớp Object và tôi sẽ nhắc bạn rằng lớp Object là tiền thân của tất cả các lớp trong Java. Nó có 11 phương thức, theo đó, được kế thừa bởi tất cả các lớp. Thông tin về tất cả 11 phương pháp có thể được tìm thấy trong phần thứ hai của cuộc thảo luận.

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. Nhiệm vụ của nó là tạo ra một số đại diện cho một đối tượng cụ thể. Một ví dụ về việc sử dụng phương pháp này là việc sử dụng nó trong HashMap trên một đối tượng chính để xác định thêm mã băm cục bộ, mã này sẽ xác định ô của mảng bên trong (nhóm) nơi cặp sẽ được lưu trữ. Chúng tôi đã nói chi tiết về hoạt động của HashMap trong phần 9 của bài phân tích , vì vậy chúng tôi sẽ không tập trung quá nhiều vào vấn đề này. Ngoài ra, theo quy định, phương thức này được sử dụng trong phương thức Equals() như một trong những công cụ chính để xác định danh tính của các đố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 mà chúng ta cần so sánh các đối tượng, vì cách so sánh thông thường sử dụng == không phù hợp với các đối tượng, bởi vì chỉ so sánh các liên kết với chúng.

96. Hãy cho chúng tôi biết về hợp đồng giữa Equals và HashCode trong Java?

Điều đầu tiên tôi sẽ nói là để các phương thức Equals() và hashCode() hoạt động chính xác , chúng cần được ghi đè chính xác. Sau đó họ phải tuân theo các quy tắc:

• các đối tượng giống hệt nhau mà so sánh bằng bằng trả về true phải có mã băm giống hệt nhau;
• các đối tượng có cùng mã băm có thể không phải lúc nào cũng bằng nhau.

Tại thời điểm này, chúng tôi sẽ tạm dừng cho đến phần phân tích tiếp theo!