Analisis soalan dan jawapan daripada temu bual untuk pembangun Java. Bahagian 10

hello! Berapa jam yang diperlukan untuk menjadi mahir dalam sesuatu? Saya sering mendengar sesuatu seperti: "Untuk menjadi mahir dalam apa sahaja, anda perlu menghabiskan 10,000 jam." Nombor yang menakutkan, bukan? Namun, saya tertanya-tanya adakah ini benar? Dan saya sentiasa cuba memikirkan berapa jam saya telah melabur dalam menguasai seni pengaturcaraan. Dan apabila saya melintasi 10,000 jam yang dihargai dan menjadi seorang tuan, adakah saya akan merasakan perbezaan ini? Atau adakah saya sudah lama melangkah ke atas mereka tanpa saya sedari? Satu cara atau yang lain, untuk menjadi seorang pengaturcara, anda tidak perlu melaburkan banyak masa. Perkara utama ialah menggunakannya dengan bijak. Matlamat utama anda adalah untuk lulus temu duga. Dan pada temuduga untuk pendatang baru, perkara pertama yang mereka tanya adalah teori, jadi anda mesti kuat di dalamnya. Sebenarnya, semasa membuat persediaan untuk temu duga, tugas anda adalah untuk menemui semua jurang anda dalam teori asas pembangun Java dan menutupnya dengan pengetahuan. Dan hari ini saya akan membantu anda dalam perkara ini, kerana saya di sini untuk terus menganalisis soalan yang paling popular. Jadi mari kita teruskan!

89. Bagaimanakah ArrayList berbeza daripada LinkedList?

Ini adalah salah satu soalan paling popular bersama-sama dengan soalan tentang struktur dalaman HashMap . Tiada satu temu bual yang lengkap tanpanya, dan oleh itu jawapan untuknya harus "memantul gigi anda." Sebagai tambahan kepada yang jelas - nama yang berbeza - mereka berbeza dalam struktur dalaman. Sebelum ini, kami telah memeriksa struktur dalaman kedua-dua ArrayList dan LinkedList , jadi saya tidak akan pergi ke butiran pelaksanaannya. Izinkan saya hanya mengingatkan anda bahawa ArrayList dilaksanakan berdasarkan tatasusunan dalaman, yang dinaikkan mengikut keperluan mengikut formula:

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

Pada masa yang sama, LinkedList dilaksanakan berdasarkan senarai pautan berganda dalaman, iaitu, setiap elemen mempunyai pautan ke sebelumnya dan seterusnya, tidak termasuk nilai yang merupakan permulaan/penghujung senarai. Orang suka bertanya soalan ini dalam format: "Mana yang lebih baik - ArrayList atau LinkedList ?", berharap dapat menangkap anda. Lagipun, jika anda menunjuk salah satu daripada mereka sebagai jawapan, ia akan menjadi jawapan yang salah. Sebaliknya, anda harus menjelaskan situasi khusus yang anda bincangkan - akses indeks atau sisipan ke tengah senarai. Bergantung pada jawapan, anda akan dapat menjelaskan pilihan anda. Saya sebelum ini telah menerangkan cara ArrayList dan LinkedList berfungsi dalam satu situasi atau yang lain. Mari kita ringkaskan ini dengan meletakkannya pada halaman yang sama untuk perbandingan: Menambah elemen (tambah)

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: dalam LinkedList, kerumitan algoritma akan berjulat dari O(1) hingga O(n/2) . Iaitu, semakin dekat sisipan dengan penghujung atau permulaan senarai, semakin cepat ia. Pada masa yang sama, untuk ArrayList ia berjulat dari O(1) hingga O(n) : semakin dekat sisipan dengan penghujung senarai, semakin pantas ia. Menetapkan elemen (set) Operasi ini menulis elemen ke kedudukan yang ditentukan dalam senarai, menimpa yang sebelumnya, jika ada. Dalam LinkedList, operasi ini akan serupa dengan menambah, kerana Kesukaran terbesar di sini ialah mencari elemen. Menulis semula elemen akan berlaku dengan menulis semula sepasang pautan, jadi di sini juga kerumitan algoritma akan berjulat dari O(1) hingga O(n/2) bergantung pada jarak kedudukan dari penghujung atau permulaan senarai. Pada masa itu, sel yang diperlukan akan ditemui dalam ArrayList untuk operasi indeks ini dan elemen baharu akan ditulis kepadanya. Carian indeks, seperti operasi ini, mempunyai kerumitan algoritma O(1) . Ambil elemen mengikut indeks (dapatkan) Dalam LinkedList, pengambilan elemen akan berlaku mengikut prinsip yang sama seperti mencari operasi lain - bergantung pada jarak dari penghujung atau permulaan, i.e. daripada O(1) kepada O(n/2) . Dalam ArrayList , seperti yang saya katakan sebelum ini, mencari elemen dalam array mengikut indeks mempunyai O(1) complexity . Alih keluar elemen mengikut indeks (alih keluar) Untuk LinkedList , prinsip operasinya juga berfungsi di sini: pertama elemen ditemui, dan kemudian pautan ditimpa - jiran elemen mula merujuk antara satu sama lain, kehilangan rujukan kepada elemen ini, yang kemudiannya akan dipadam oleh pemungut sampah. Iaitu, kerumitan algoritma masih sama - dari O(1) hingga O(n/2) . Untuk ArrayList , operasi ini lebih serupa dengan operasi menambah elemen baharu (tambah). Pertama, elemen yang diperlukan ditemui - O(1) , kemudian ia dikeluarkan, dan semua elemen yang berada di sebelah kanannya dialihkan satu unit ke kiri untuk menutup jurang yang terhasil. Operasi padam akan mempunyai kerumitan algoritma yang sama seperti operasi tambah - dari O(1) hingga O(n) . Semakin hampir pemadaman ke penghujung senarai, semakin kurang kerumitan algoritma yang dimilikinya. Sebenarnya, ini semua adalah operasi utama. Izinkan saya mengingatkan anda: apabila membandingkan kedua-dua senarai ini, anda perlu menjelaskan situasi khusus yang kita bincangkan, dan kemudian anda boleh menjawab soalan yang dikemukakan dengan jelas.

90. Bagaimanakah ArrayList berbeza daripada HashSet?

Jika ArrayList dan LinkedList boleh dibandingkan dari segi operasi - yang lebih baik - maka tidaklah begitu mudah untuk membandingkan ArrayList dengan HashSet , kerana ini adalah koleksi yang sama sekali berbeza. Anda boleh membandingkan satu hidangan manis dengan yang lain, tetapi ia akan berfungsi dengan hidangan daging - mereka terlalu berbeza. Walau bagaimanapun, saya akan cuba memberikan beberapa perbezaan antara mereka:

• ArrayList melaksanakan antara muka Senarai , manakala HashSet melaksanakan antara muka Set ;

• Dalam ArrayList, akses boleh dilakukan oleh indeks elemen: operasi get mempunyai kerumitan algoritma O(1) , dan dalam HashSet elemen yang diperlukan hanya boleh diperolehi dengan kekerasan, dan ini adalah dari O(1) hingga O(n) ;

• ArrayList membenarkan elemen pendua. Dalam HashSet, semua elemen adalah unik: menambah elemen pada HashSet yang analognya sudah ada dalam koleksi tidak akan berfungsi (pendua disemak menggunakan kod cincang, oleh itu nama koleksi ini);

• ArrayList dilaksanakan menggunakan tatasusunan dalaman, dan HashSet dilaksanakan menggunakan HashMap dalaman ;

• ArrayList mengekalkan susunan sisipan unsur, manakala HashSet ialah set tidak tertib dan tidak mengekalkan susunan unsur;

• ArrayList membenarkan sebarang bilangan nilai kosong (null), hanya satu nilai null boleh dimasukkan ke dalam HashSet (lagipun, keunikan elemen).

91. Mengapakah terdapat pelbagai jenis pelaksanaan tatasusunan dinamik dalam Java?

Nah, ini lebih kepada soalan falsafah. Nah, mengapa mereka menghasilkan begitu banyak teknologi baharu yang berbeza? Untuk keselesaan. Sebenarnya, ia adalah sama dengan sejumlah besar pelaksanaan tatasusunan dinamik. Tiada satu pun daripada mereka boleh dipanggil yang terbaik atau ideal. Masing-masing mempunyai kelebihan dalam beberapa situasi tertentu. Dan tugas kita adalah untuk mengetahui perbezaan mereka, kekuatan/kelemahan mereka: agar dapat menggunakan yang paling sesuai dalam situasi yang betul.

92. Mengapakah terdapat kepelbagaian pelaksanaan storan nilai kunci dalam Java?

Di sini keadaannya adalah sama seperti pelaksanaan tatasusunan dinamik. Tidak ada yang terbaik: masing-masing mempunyai kekuatan dan kelemahan. Dan kita, sudah tentu, mesti menggunakan kekuatan kita sepenuhnya. Contoh: pakej serentak, yang mengandungi banyak teknologi berbilang benang, mempunyai koleksi Serentak sendiri . ConcurrentHashMap yang sama mempunyai kelebihan dalam keselamatan kerja berbilang benang dengan data berbanding HashMap biasa , tetapi dalam persekitaran bukan berbilang benang, ia kehilangan kelajuan. Nah, pelaksanaan, yang bukan yang paling kuat dalam apa jua keadaan, secara beransur-ansur dihentikan digunakan. Contoh: Hashtable pada asalnya bertujuan untuk menjadi HashMap selamat benang , tetapi ConcurrentHashMap mengatasinya dalam persekitaran berbilang benang dan Hashtable akhirnya dilupakan dan tidak lagi digunakan.

93. Bagaimana untuk mengisih koleksi elemen?

Perkara pertama yang perlu dikatakan ialah kelas elemen koleksi mesti melaksanakan antara muka Sebanding dan kaedah compareTonya . Atau anda memerlukan kelas yang melaksanakan Comaprator dengan kaedah pembandingnya . Anda boleh membaca lebih lanjut tentang mereka dalam siaran ini . Kedua-dua kaedah menentukan cara objek bagi jenis tertentu harus dibandingkan. Apabila menyusun, ini sangat penting, kerana anda perlu memahami prinsip yang mana elemen boleh dibandingkan. Cara utama untuk melakukan ini ialah dengan melaksanakan Comparable , dilaksanakan secara langsung dalam kelas yang anda ingin isikan. Pada masa yang sama, penggunaan Comparator adalah kurang biasa. Katakan anda menggunakan kelas daripada sesetengah pustaka yang tidak mempunyai Comparable implementation , tetapi anda perlu mengisihnya entah bagaimana. Tanpa dapat menukar kod kelas ini (kecuali dengan melanjutkannya), anda boleh menulis pelaksanaan Comparator , di mana anda menunjukkan prinsip apa yang anda ingin bandingkan objek kelas ini. Dan satu lagi contoh. Katakan anda memerlukan prinsip yang berbeza untuk mengisih objek daripada jenis yang sama, jadi anda menulis beberapa Pembanding yang anda gunakan dalam situasi yang berbeza. Sebagai peraturan, banyak kelas di luar kotak sudah melaksanakan antara muka Sebanding - String yang sama . Sebenarnya, apabila menggunakannya, anda tidak perlu risau tentang cara membandingkannya. Anda hanya mengambilnya dan menggunakannya. Cara pertama dan paling jelas ialah menggunakan koleksi seperti TreeSet atau TreeMap , yang menyimpan elemen dalam susunan yang telah diisih mengikut pembanding kelas elemen. Ingat bahawa TreeMap mengisih kunci, tetapi bukan nilai. Jika anda menggunakan pelaksanaan Comparator dan bukannya Comparable , anda perlu menghantar objeknya kepada pembina koleksi apabila dibuat:

TreeSet treeSet = new TreeSet(customComparator);

Tetapi bagaimana jika anda mempunyai jenis koleksi yang berbeza? Bagaimana untuk menyusunnya? Dalam kes ini, kaedah kedua kelas utiliti Koleksi adalah sesuai - kaedah sort() . Ia statik, jadi semua yang anda perlukan ialah nama kelas dan kaedah yang mana senarai yang diperlukan diluluskan. Sebagai contoh:

Collections.sort(someList);

Jika anda tidak menggunakan Comparable , tetapi sebaliknya pelaksanaan Comparator , anda perlu menghantarnya sebagai parameter kedua:

Collections.sort(someList, customComparator);

Akibatnya, susunan dalaman elemen senarai yang diluluskan akan berubah: ia akan diisih mengikut pembanding elemen. Saya perhatikan bahawa senarai elemen yang dipindahkan mestilah boleh berubah, i.e. boleh ubah, jika tidak kaedah itu tidak akan berfungsi dan UnsupportedOperationException akan dibuang . Sebagai cara ketiga , anda boleh menggunakan operasi Isih Strim , yang mengisih elemen koleksi jika pelaksanaan Sebanding digunakan :

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

jika Pembanding :

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

Anda boleh membaca lebih lanjut mengenai Strim dalam artikel ini . Kaedah keempat ialah melaksanakan pengisihan secara manual, seperti isihan gelembung atau isihan gabungan .

ClassObject. Equals dan HashCode

94. Berikan penerangan ringkas tentang objek kelas di Jawa

Dalam bahagian kedua analisis, kita sudah bercakap tentang kaedah kelas Object , dan saya akan mengingatkan anda bahawa kelas Object ialah nenek moyang semua kelas di Jawa. Ia mempunyai 11 kaedah, yang, sewajarnya, diwarisi oleh semua kelas. Maklumat tentang kesemua 11 kaedah boleh didapati di bahagian kedua perbincangan.

95. Apakah Equals dan HashCode digunakan dalam Java?

hashCode() ialah kaedah kelas Objek yang diwarisi oleh semua kelas. Tugasnya adalah untuk menjana beberapa nombor yang mewakili objek tertentu. Contoh menggunakan kaedah ini ialah penggunaannya dalam HashMap pada objek utama untuk menentukan lebih lanjut kod cincang tempatan, yang akan menentukan sel tatasusunan dalaman (baldi) di mana pasangan itu akan disimpan. Kami bercakap secara terperinci tentang kerja HashMap dalam bahagian 9 analisis , jadi kami tidak akan terlalu memikirkan perkara ini. Juga, sebagai peraturan, kaedah ini digunakan dalam kaedah equals() sebagai salah satu alat utamanya untuk menentukan identiti objek. equals() ialah kaedah kelas Objek yang tugasnya adalah untuk membandingkan objek dan menentukan sama ada ia sama atau tidak. Kaedah ini digunakan di mana-mana di mana kita perlu membandingkan objek, kerana perbandingan biasa menggunakan == tidak sesuai untuk objek, kerana membandingkan hanya pautan kepada mereka.

96. Beritahu kami tentang kontrak antara Equals dan HashCode di Java?

Perkara pertama yang saya akan katakan ialah untuk kaedah equals() dan hashCode() berfungsi dengan betul , ia perlu ditimpa dengan betul. Selepas ini mereka mesti mematuhi peraturan:

• objek yang sama yang perbandingan melalui equals mengembalikan benar mesti mempunyai kod cincang yang sama;
• objek dengan kod cincang yang sama mungkin tidak selalu sama.

Pada ketika ini kita akan berhenti seketika sehingga bahagian analisis seterusnya!