Analisis tanya jawab dari wawancara untuk pengembang Java. Bagian 10

Halo! Berapa jam yang dibutuhkan untuk menjadi ahli dalam suatu hal? Saya sering mendengar sesuatu seperti: “Untuk menjadi ahli dalam segala hal, Anda perlu menghabiskan 10.000 jam.” Angka yang menakutkan bukan? Namun, saya bertanya-tanya apakah ini benar? Dan saya terus-menerus mencoba mencari tahu berapa jam yang telah saya investasikan untuk menguasai seni pemrograman. Dan ketika saya melewati 10.000 jam berharga itu dan menjadi seorang master, akankah saya merasakan perbedaan ini? Atau apakah saya sudah lama melangkahinya tanpa menyadarinya? Bagaimanapun, untuk menjadi seorang programmer, Anda tidak perlu menginvestasikan banyak waktu. Yang utama adalah menggunakannya dengan bijak. Tujuan utama Anda adalah lulus wawancara. Dan saat wawancara untuk pendatang baru, yang pertama ditanyakan adalah teori, jadi harus kuat di dalamnya. Sebenarnya, saat mempersiapkan wawancara, tugas Anda adalah menemukan semua kesenjangan Anda dalam teori dasar seorang pengembang Java dan menutupinya dengan pengetahuan. Dan hari ini saya akan membantu Anda dalam hal ini, karena saya di sini untuk terus menganalisis pertanyaan paling populer. Jadi mari kita lanjutkan!

89. Apa perbedaan ArrayList dengan LinkedList?

Ini adalah salah satu pertanyaan paling populer bersama dengan pertanyaan tentang struktur internal HashMap . Tidak ada satu wawancara pun yang lengkap tanpanya, dan oleh karena itu jawabannya harus “sangat menarik”. Selain nama yang jelas - berbeda - mereka berbeda dalam struktur internal. Sebelumnya, kita memeriksa struktur internal ArrayList dan LinkedList , jadi saya tidak akan membahas detail implementasinya. Izinkan saya mengingatkan Anda bahwa ArrayList diimplementasikan berdasarkan array internal, yang ditingkatkan sesuai kebutuhan sesuai dengan rumus:

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

Pada saat yang sama, LinkedList diimplementasikan berdasarkan daftar tertaut ganda internal, yaitu setiap elemen memiliki tautan ke sebelumnya dan berikutnya, tidak termasuk nilai yang merupakan awal/akhir daftar. Orang-orang suka menanyakan pertanyaan ini dalam format: “Mana yang lebih baik - ArrayList atau LinkedList ?”, berharap dapat menangkap Anda. Lagi pula, jika Anda menunjuk salah satunya sebagai jawaban, itu adalah jawaban yang salah. Sebaliknya, Anda harus memperjelas situasi spesifik apa yang Anda bicarakan - akses indeks atau penyisipan ke tengah daftar. Tergantung pada jawabannya, Anda akan dapat menjelaskan pilihan Anda. Saya sebelumnya telah menjelaskan cara kerja ArrayList dan LinkedList dalam satu situasi atau lainnya. Mari kita rangkum dengan menempatkannya pada halaman yang sama sebagai perbandingan: Menambahkan elemen (menambahkan)

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).

Intinya: di LinkedList, kompleksitas algoritmik akan berkisar dari O(1) hingga O(n/2) . Artinya, semakin dekat penyisipan ke akhir atau awal daftar, semakin cepat pula penyisipannya. Pada saat yang sama, untuk ArrayList berkisar dari O(1) hingga O(n) : semakin dekat penyisipan ke akhir daftar, semakin cepat penyisipannya. Mengatur elemen (set) Operasi ini menulis elemen ke posisi tertentu dalam daftar, menimpa elemen sebelumnya, jika ada. Di LinkedList, operasi ini akan mirip dengan penambahan, karena Kesulitan terbesar di sini adalah menemukan elemennya. Penulisan ulang suatu elemen akan dilakukan dengan menulis ulang sepasang tautan, jadi di sini juga kompleksitas algoritmiknya akan berkisar dari O(1) hingga O(n/2) tergantung pada jarak posisi dari akhir atau awal daftar. Pada saat itu, sel yang diperlukan akan ditemukan di ArrayList untuk operasi indeks ini, dan elemen baru akan ditulis ke dalamnya. Pencarian indeks, seperti operasi ini, memiliki kompleksitas algoritmik O(1) . Ambil elemen berdasarkan indeks (dapatkan) Di LinkedList, pengambilan elemen akan terjadi sesuai dengan prinsip yang sama seperti mencari operasi lain - bergantung pada jarak dari akhir atau awal, yaitu. dari O(1) ke O(n/2) . Dalam ArrayList , seperti yang saya katakan sebelumnya, menemukan elemen dalam array berdasarkan indeks memiliki kompleksitas O(1) . Hapus elemen berdasarkan indeks (hapus) Untuk LinkedList, prinsip operasinya juga berfungsi di sini: pertama elemen ditemukan, dan kemudian tautan ditimpa - tetangga elemen mulai merujuk satu sama lain, kehilangan referensi ke elemen ini, yang mana selanjutnya akan dihapus oleh pengumpul sampah. Artinya, kompleksitas algoritmiknya masih sama - dari O(1) hingga O(n/2) . Untuk ArrayList , operasi ini lebih mirip dengan operasi penambahan elemen baru (add). Pertama, elemen yang diperlukan ditemukan - O(1) , kemudian dihapus, dan semua elemen di sebelah kanannya dipindahkan satu unit ke kiri untuk menutup celah yang dihasilkan. Operasi penghapusan akan memiliki kompleksitas algoritmik yang sama dengan operasi penambahan - dari O(1) hingga O(n) . Semakin dekat penghapusan ke akhir daftar, semakin sedikit kompleksitas algoritmik yang dimilikinya. Sebenarnya, ini semua adalah operasi utama. Izinkan saya mengingatkan Anda: ketika membandingkan kedua daftar ini, Anda perlu memperjelas situasi spesifik apa yang sedang kita bicarakan, dan kemudian Anda dapat menjawab pertanyaan yang diajukan dengan jelas.

90. Apa perbedaan ArrayList dengan HashSet?

Jika ArrayList dan LinkedList dapat dibandingkan dalam hal operasi - mana yang lebih baik - maka tidak mudah untuk membandingkan ArrayList dengan HashSet , karena ini adalah koleksi yang sama sekali berbeda. Anda dapat membandingkan satu hidangan manis dengan hidangan lainnya, tetapi hidangan daging akan berhasil - keduanya terlalu berbeda. Namun, saya akan mencoba memberikan beberapa perbedaan di antara keduanya:

• ArrayList mengimplementasikan antarmuka Daftar , sementara HashSet mengimplementasikan antarmuka Set ;

• Dalam ArrayList, akses dimungkinkan dengan indeks elemen: operasi get memiliki kompleksitas algoritmik O(1) , dan dalam HashSet elemen yang diperlukan hanya dapat diperoleh dengan kekerasan, dan ini dari O(1) hingga O(n) ;

• ArrayList memungkinkan elemen duplikat. Dalam HashSet, semua elemen bersifat unik: menambahkan elemen ke HashSet yang analognya sudah ada dalam koleksi tidak akan berfungsi (duplikat diperiksa menggunakan kode hash, itulah nama koleksi ini);

• ArrayList diimplementasikan menggunakan array internal, dan HashSet diimplementasikan menggunakan HashMap internal ;

• ArrayList mempertahankan urutan penyisipan elemen, sedangkan HashSet adalah himpunan tidak berurutan dan tidak menjaga urutan elemen;

• ArrayList mengizinkan sejumlah nilai kosong (null), hanya satu nilai null yang dapat dimasukkan ke dalam HashSet (bagaimanapun juga, keunikan elemennya).

91. Mengapa ada begitu banyak variasi implementasi array dinamis di Java?

Ini lebih merupakan pertanyaan filosofis. Mengapa mereka memunculkan begitu banyak teknologi baru yang berbeda? Untuk kenyamanan. Sebenarnya, hal yang sama terjadi pada implementasi array dinamis dalam jumlah besar. Tak satu pun dari mereka bisa disebut yang terbaik atau ideal. Masing-masing mempunyai keunggulan dalam situasi tertentu. Dan tugas kita adalah mengetahui perbedaannya, kelebihan/kelemahannya: agar dapat menggunakan yang paling sesuai dalam situasi yang tepat.

92. Mengapa ada begitu banyak variasi implementasi penyimpanan nilai kunci di Java?

Di sini situasinya sama dengan implementasi array dinamis. Tidak ada yang terbaik: masing-masing memiliki kekuatan dan kelemahan. Dan tentu saja kita harus memanfaatkan kekuatan kita semaksimal mungkin. Contoh: paket serentak, yang berisi banyak teknologi multi-utas, memiliki koleksi serentak sendiri . ConcurrentHashMap yang sama memiliki keunggulan dalam keamanan pekerjaan multi-thread dengan data dibandingkan dengan HashMap biasa , tetapi dalam lingkungan non-multi-thread, kecepatannya berkurang. Nah, implementasi yang bukan merupakan yang terkuat dalam situasi apa pun, secara bertahap berhenti digunakan. Contoh: Hashtable awalnya dimaksudkan untuk menjadi HashMap yang aman untuk thread , tetapi ConcurrentHashMap mengunggulinya dalam lingkungan multi-thread dan Hashtable akhirnya dilupakan dan tidak lagi digunakan.

93. Bagaimana cara mengurutkan kumpulan elemen?

Hal pertama yang harus dikatakan adalah bahwa kelas elemen koleksi harus mengimplementasikan antarmuka Comparable dan metode CompareTo -nya . Atau Anda memerlukan kelas yang mengimplementasikan Comaprator dengan metode komparatornya . Anda dapat membaca lebih lanjut tentang mereka di postingan ini . Kedua metode menentukan bagaimana objek dari tipe tertentu harus dibandingkan. Saat menyortir, hal ini sangat penting, karena Anda perlu memahami prinsip perbandingan elemen. Cara utama untuk melakukan ini adalah dengan mengimplementasikan Comparable , yang diimplementasikan langsung di kelas yang ingin Anda urutkan. Pada saat yang sama, penggunaan Komparator kurang umum. Katakanlah Anda menggunakan kelas dari beberapa perpustakaan yang tidak memiliki implementasi Comparable , tetapi Anda harus mengurutkannya. Tanpa dapat mengubah kode kelas ini (kecuali dengan memperluasnya), Anda dapat menulis implementasi Comparator , di mana Anda menunjukkan prinsip apa yang ingin Anda bandingkan objek kelas ini. Dan satu contoh lagi. Katakanlah Anda memerlukan prinsip berbeda untuk mengurutkan objek dengan tipe yang sama, jadi Anda menulis beberapa Pembanding yang Anda gunakan dalam situasi berbeda. Sebagai aturan, banyak kelas di luar kotak sudah mengimplementasikan antarmuka Comparable - String yang sama . Sebenarnya saat menggunakannya, Anda tidak perlu khawatir bagaimana membandingkannya. Anda tinggal mengambilnya dan menggunakannya. Cara pertama dan paling jelas adalah dengan menggunakan kumpulan tipe TreeSet atau TreeMap , yang menyimpan elemen dalam urutan yang sudah diurutkan menurut pembanding kelas elemen. Ingatlah bahwa TreeMap mengurutkan kunci, bukan nilai. Jika Anda menggunakan implementasi Comparator dan bukan Comparable , Anda harus meneruskan objeknya ke konstruktor koleksi saat pembuatan:

TreeSet treeSet = new TreeSet(customComparator);

Namun bagaimana jika Anda memiliki jenis koleksi yang berbeda? Bagaimana cara mengurutkannya? Dalam hal ini, metode kedua dari kelas utilitas Koleksi cocok - metode sort() . Ini statis, jadi yang Anda perlukan hanyalah nama kelas dan metode yang meneruskan daftar yang diperlukan. Misalnya:

Collections.sort(someList);

Jika Anda tidak menggunakan Comparable , melainkan implementasi Comparator , Anda harus meneruskannya sebagai parameter kedua:

Collections.sort(someList, customComparator);

Akibatnya, urutan internal elemen daftar yang diteruskan akan berubah: urutannya akan diurutkan menurut pembanding elemen. Saya perhatikan bahwa daftar elemen yang ditransfer harus bisa berubah, mis. bisa berubah, jika tidak, metode ini tidak akan berfungsi dan UnsupportedOperationException akan dilempar . Sebagai cara ketiga , Anda dapat menggunakan operasi pengurutan aliran , yang mengurutkan elemen koleksi jika implementasi Sebanding digunakan :

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

jika Pembanding :

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

Anda dapat membaca lebih lanjut tentang Stream di artikel ini . Cara keempat adalah dengan menerapkan pengurutan secara manual, seperti bubble sort atau merge sort .

Objek Kelas. Sama dengan dan HashCode

94. Berikan gambaran singkat tentang objek kelas di Java

Pada analisis bagian kedua, kita telah membicarakan tentang metode kelas Object , dan saya akan mengingatkan Anda bahwa kelas Object adalah nenek moyang dari semua kelas di Java. Ini memiliki 11 metode, yang karenanya diwarisi oleh semua kelas. Informasi tentang ke-11 metode tersebut dapat ditemukan pada pembahasan bagian kedua.

95. Untuk apa Equals dan HashCode digunakan di Java?

hashCode() adalah metode kelas Object yang diwarisi oleh semua kelas. Tugasnya adalah menghasilkan sejumlah angka yang mewakili objek tertentu. Contoh penggunaan metode ini adalah penggunaannya dalam HashMap pada objek kunci untuk menentukan lebih lanjut kode hash lokal, yang akan menentukan sel array internal (bucket) di mana pasangan akan disimpan. Kami berbicara secara rinci tentang cara kerja HashMap di bagian 9 analisis , jadi kami tidak akan terlalu memikirkan hal ini. Selain itu, sebagai aturan, metode ini digunakan dalam metode sama dengan() sebagai salah satu alat utamanya untuk menentukan identitas objek. sama dengan() adalah metode kelas Object yang tugasnya membandingkan objek dan menentukan apakah objek tersebut sama atau tidak. Metode ini digunakan dimanapun kita perlu membandingkan objek, karena perbandingan biasa menggunakan == tidak cocok untuk objek, karena hanya membandingkan tautan ke mereka.

96. Ceritakan tentang kontrak antara Equals dan HashCode di Java?

Hal pertama yang akan saya katakan adalah agar metode sama dengan() dan hashCode() berfungsi dengan benar , metode tersebut harus diganti dengan benar. Setelah ini mereka harus mengikuti peraturan:

• objek identik yang perbandingannya melalui nilai sama dengan mengembalikan nilai true harus memiliki kode hash yang sama ;
• objek dengan kode hash yang sama mungkin tidak selalu sama.

Pada titik ini kita akan berhenti sejenak hingga analisis bagian selanjutnya!