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

Bunga api! Menjadi seorang pengaturcara bukan mudah. Anda perlu sentiasa belajar, sentiasa belajar sesuatu yang baru. Tetapi, seperti dalam perniagaan lain, perkara yang paling sukar adalah untuk bermula, untuk mengambil langkah pertama ke arah matlamat anda. Dan kerana anda sedang duduk di laman web ini dan membaca artikel ini, anda telah menyelesaikan langkah pertama. Ini bermakna kini anda perlu bergerak secara sengaja ke arah matlamat anda, tanpa memperlahankan atau mematikan di sepanjang jalan. Jika saya faham dengan betul, matlamat anda adalah untuk menjadi pembangun Java atau meningkatkan pengetahuan anda jika anda seorang. Jika ya, maka anda berada di tempat yang betul, kerana kami akan terus menganalisis senarai luas 250+ soalan temuduga pembangun Java. Jom sambung!

Koleksi

84. Beritahu kami tentang iterator dan penggunaannya

Koleksi ialah salah satu topik kegemaran dalam mana-mana temu bual pembangun Java, dan apabila bercakap tentang hierarki koleksi, calon sering mengatakan bahawa ia bermula dengan antara muka Koleksi . Tetapi ini tidak benar, kerana di atas antara muka ini terdapat satu lagi - Iterable . Antara muka ini mewakili kaedah iterator() , yang membolehkan anda memanggil objek Iterator untuk koleksi semasa. Dan apakah sebenarnya objek Iterator ini ? Iterator ialah objek yang menyediakan keupayaan untuk bergerak melalui koleksi dan mengulang elemen tanpa pengguna perlu mengetahui pelaksanaan koleksi tertentu. Iaitu, ini adalah sejenis penunjuk kepada unsur-unsur koleksi, yang, seolah-olah, melihat tempat tertentu di dalamnya. Iterator mempunyai kaedah berikut:

• hasNext() - mengembalikan benar jika terdapat elemen yang terletak selepas penunjuk (kaedah ini membolehkan anda mengetahui sama ada penghujung koleksi telah dicapai);
• next() - mengembalikan elemen seterusnya selepas penunjuk. Jika tiada, NoSuchElementException dibuang . Iaitu, sebelum menggunakan kaedah ini, adalah lebih baik untuk memastikan bahawa elemen itu wujud - menggunakan hasNext() ;
• remove() - mengalih keluar elemen terakhir yang diterima daripada koleksi menggunakan kaedah next() . Jika next() tidak pernah dipanggil sebelum remove() dipanggil, pengecualian akan dilemparkan - IllegalStateException ;
• forEachRemaining(<Consumer>) - melakukan tindakan yang diluluskan dengan setiap elemen koleksi (kaedah itu muncul dalam Java 8).

Berikut ialah contoh kecil lelaran melalui senarai dan mengalih keluar semua elemennya menggunakan kaedah iterator yang dibincangkan:

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());

Konsol akan memaparkan: Ini bermakna pengalihan keluar elemen berjaya. Sebaik sahaja kami mempunyai iterator, kami boleh menggunakan kaedah untuk mencetak semua elemen ke skrin:

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

Tetapi selepas ini, iterator akan menjadi tidak sesuai untuk kegunaan selanjutnya, kerana ia akan merentasi keseluruhan senarai, dan iterator biasa tidak mempunyai kaedah untuk menjejak ke belakang. Di sini kita secara beransur-ansur mendekati LinkedList , iaitu, kaedah listIterator() , yang mengembalikan jenis iterator yang dimodenkan - ListIterator . Selain kaedah iterator biasa (standard), yang ini mempunyai kaedah tambahan:

• add(<Element>) - memasukkan elemen baharu ke dalam senarai;
• hasPrevious() - mengembalikan benar jika terdapat elemen yang terletak sebelum penunjuk (sama ada terdapat elemen sebelumnya);
• nextIndex() - mengembalikan indeks dalam senarai elemen seterusnya selepas penunjuk;
• previous() - mengembalikan elemen sebelumnya (sehingga penuding);
• previousIndex() - mengembalikan indeks elemen sebelumnya;
• set(<Element>) - Menggantikan elemen terakhir yang dikembalikan oleh kaedah next() atau previous() .

Seperti yang anda lihat, kefungsian iterator ini jauh lebih menarik: ia membolehkan anda bergerak ke kedua-dua arah dan membebaskan tangan anda apabila bekerja dengan elemen. Selain itu, apabila orang bercakap tentang iterator, mereka kadangkala bermaksud corak itu sendiri. Untuk mengelakkan masalah dan bercakap mengenainya dengan meyakinkan, baca artikel ini tentang corak Iterator .

85. Apakah hierarki koleksi dalam Rangka Kerja Koleksi Java?

Terdapat dua hierarki koleksi di Jawa. Hierarki pertama ialah hierarki Koleksi itu sendiri dengan struktur berikut: Ia, seterusnya, dibahagikan kepada subkoleksi berikut:

• Set ialah antara muka yang menerangkan struktur data sedemikian sebagai set yang mengandungi unsur unik (tidak berulang) tidak tertib. Antara muka mempunyai pelaksanaan standard - TreeSet , HashSet dan LinkedHashSet .
• Senarai ialah antara muka yang menerangkan struktur data yang menyimpan urutan objek yang tersusun. Kejadian yang terkandung dalam Senarai boleh disisipkan dan dipadamkan oleh indeksnya dalam koleksi ini (serupa dengan tatasusunan, tetapi dengan saiz semula dinamik). Antara muka mempunyai pelaksanaan standard - ArrayList , Vector ( dianggap usang dan tidak digunakan sebenarnya ) dan LinkedList .
• Baris gilir ialah antara muka yang menerangkan struktur data yang menyimpan elemen dalam bentuk baris gilir yang mengikut peraturan FIFO - Pertama Masuk Dahulu Keluar . Antara muka mempunyai pelaksanaan standard berikut: LinkedList (ya, ia juga melaksanakan Queue ) dan PriotityQueue .

Hierarki koleksi kedua ialah Map , yang mempunyai struktur berikut: Dalam koleksi ini tiada pembahagian kepada subkoleksi (kerana hierarki Peta itu sendiri adalah seperti subkoleksi, tetapi terletak secara berasingan). Pelaksanaan Peta Standard ialah Hashtable (dianggap tidak digunakan lagi), LinkedHashMap dan TreeMap . Sebenarnya, apabila ditanya tentang Koleksi , kedua-dua hierarki biasanya dimaksudkan.

86. Apakah struktur dalaman ArrayList?

ArrayList adalah serupa dengan tatasusunan, tetapi dengan keupayaan untuk berkembang secara dinamik. Apakah maksudnya? Faktanya ialah ArrayList berfungsi berdasarkan tatasusunan biasa, iaitu, ia menyimpan elemen dalam tatasusunan dalaman (saiz lalainya ialah 10 sel). Apabila tatasusunan dalaman penuh, tatasusunan baharu dicipta, saiznya ditentukan oleh formula:

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

Iaitu, jika saiz tatasusunan kami ialah 10, saiz tatasusunan baharu ialah: 10 * 3 / 2 + 1 = 16. Seterusnya, semua nilai daripada tatasusunan pertama (lama) disalin ke dalamnya menggunakan kaedah System.arraycopy () asli , dan tatasusunan pertama dipadamkan. Sebenarnya, ini adalah bagaimana kebolehlanjutan dinamik ArrayList dilaksanakan . Mari lihat kaedah ArrayList yang paling banyak digunakan : 1. add(<Elelement>) - menambah elemen pada penghujung tatasusunan (ke sel kosong terakhir), dan mula-mula menyemak sama ada terdapat ruang dalam tatasusunan ini. Jika ia tidak ada, tatasusunan baharu dicipta di mana unsur-unsur disalin. Kerumitan logaritma operasi ini ialah O(1). Terdapat kaedah yang serupa - add(<Index>,<Elelement>) . Ia menambahkan elemen bukan pada penghujung senarai (tatasusunan), tetapi pada sel tertentu dengan indeks yang datang sebagai hujah. Dalam kes ini, kerumitan logaritma akan berbeza bergantung pada tempat ia ditambah:

• jika ini adalah kira-kira permulaan senarai, kerumitan logaritma akan hampir dengan O(N), kerana semua elemen yang terletak di sebelah kanan yang baharu perlu dialihkan satu sel ke kanan;
• jika elemen dimasukkan di tengah - O(N/2) kerana kita perlu mengalihkan hanya separuh daripada elemen senarai satu sel ke kanan.

Iaitu, kerumitan logaritma kaedah ini berjulat dari O(N) hingga O(1) bergantung pada tempat elemen dimasukkan. 2. set(<Indeks>,<Elemen>) - menulis elemen ke kedudukan yang ditentukan dalam senarai. Jika sudah ada elemen pada kedudukan itu, tulis gantinya. Kerumitan logaritma operasi ini ialah O(1), kerana tiada anjakan: hanya mencari mengikut indeks dalam tatasusunan, yang, seperti yang kita ingat, mempunyai kerumitan O(1), dan menulis elemen. 3. remove(<index>) - mengalih keluar elemen mengikut indeksnya dalam tatasusunan dalaman. Apabila memadamkan item yang tidak berada di penghujung senarai, anda mesti mengalihkan semua item ke kanan satu sel ke kiri untuk menutup jurang kiri selepas memadamkan item. Oleh itu, kerumitan logaritma akan sama seperti add(<Index>,<Elemen>) jika elemen berada di tengah - O(N/2) - kerana anda perlu mengalihkan separuh daripada elemen satu ke kiri. Sehubungan itu, jika ia pada mulanya - O(N). Nah, jika pada akhirnya ia O(1), maka anda tidak perlu mengalihkan apa-apa. Bagi mereka yang ingin mendalami topik ini, saya akan meninggalkan pautan ini ke artikel dengan analisis kelas ArrayList .

87. Apakah struktur dalaman LinkedList?

Jika ArrayList mengandungi elemen dalam tatasusunan dalaman, maka LinkedList adalah dalam bentuk senarai terpaut dua kali. Ini bermakna setiap elemen mengandungi pautan ke elemen sebelumnya ( sebelumnya ) dan yang seterusnya ( seterusnya ). Elemen pertama tidak mempunyai pautan ke yang sebelumnya (ia adalah yang pertama), tetapi ia dianggap sebagai ketua senarai, dan LinkedList mempunyai pautan terus kepadanya. Elemen terakhir, sebenarnya, tidak mempunyai elemen seterusnya, ia adalah ekor senarai, dan oleh itu terdapat pautan terus kepadanya dalam LinkedList itu sendiri . Oleh itu, kerumitan logaritma untuk mengakses kepala atau ekor senarai ialah O(1). Dalam ArrayList, apabila senarai bertambah, tatasusunan dalaman meningkat, tetapi di sini semuanya berlaku dengan lebih mudah - apabila menambah elemen, beberapa pautan hanya berubah. Mari lihat beberapa kaedah LinkedlList yang paling banyak digunakan : 1. tambah(<Elemen>) - tambah pada penghujung senarai, i.e. selepas elemen terakhir (5) pautan ke elemen baharu akan ditambah sebagai seterusnya . Elemen baharu akan mempunyai pautan ke yang terakhir (5) sebagai elemen sebelumnya . Kerumitan logaritma bagi operasi sedemikian ialah O(1), kerana hanya pautan ke elemen terakhir diperlukan, dan seperti yang anda ingat, ekor mempunyai pautan terus dari LinkedList dan kerumitan logaritma untuk mengaksesnya adalah minimum. 2. tambah(<Indeks>,<Elemen>) - menambah elemen mengikut indeks. Apabila menambah elemen, sebagai contoh, ke tengah senarai, elemen dari kepala dan ekor (di kedua-dua belah) mula-mula diulang sehingga tempat yang dikehendaki ditemui. Jika kita ingin memasukkan elemen antara ketiga dan keempat (dalam rajah di atas), maka apabila mencari tempat yang betul, pautan seterusnya elemen ketiga sudah pun menunjuk kepada yang baharu. Untuk yang baharu, pautan sebelumnya akan menghala ke yang ketiga. Sehubungan itu, pautan elemen keempat - sebelumnya - sudah pun menunjuk ke elemen baharu, dan pautan seterusnya elemen baharu akan menghala ke elemen keempat: Kerumitan logaritma kaedah ini akan bergantung pada indeks yang diberikan kepada elemen baharu:

• jika ia hampir dengan kepala atau ekor, ia akan menghampiri O(1), kerana ia sebenarnya tidak perlu untuk melelang ke atas unsur;
• jika ia dekat dengan tengah, maka O(N/2) - elemen dari kepala dan ekor akan diisih serentak sehingga elemen yang diperlukan ditemui.

3. set(<Indeks>,<Elemen>) - menulis elemen ke kedudukan yang ditentukan dalam senarai. Kerumitan logaritma operasi ini akan berjulat dari O(1) hingga O(N/2), sekali lagi bergantung pada jarak elemen itu dengan kepala, ekor atau tengah. 4. remove(<index>) - mengalih keluar elemen daripada senarai, pada asasnya menjadikan elemen yang datang sebelum yang dialih keluar ( sebelumnya ) merujuk kepada elemen yang datang selepas yang dialih keluar ( seterusnya ). Dan sebaliknya: supaya elemen yang datang selepas yang dipadamkan merujuk kepada yang datang sebelum yang dipadamkan: Hasilnya ialah proses songsang untuk menambah mengikut indeks ( add(<Index>,<Elelement>) ). Bagi mereka yang ingin mengetahui lebih lanjut tentang struktur dalaman LinkedList , saya syorkan membaca artikel ini .

88. Apakah struktur dalaman HashMap?

Mungkin salah satu soalan paling popular semasa menemu bual pembangun Java. HashMap v berfungsi dengan pasangan nilai kunci . Bagaimanakah ia disimpan di dalam HashMapv itu sendiri ? Di dalam HashMap terdapat pelbagai nod:

Node<K,V>[] table

Secara lalai, saiz tatasusunan ialah 16, dan ia berganda setiap kali kerana ia dipenuhi dengan elemen (apabila LOAD_FACTOR dicapai - peratusan kepenuhan tertentu, secara lalai ialah 0.75 ). Setiap nod menyimpan cincang kunci, kunci, nilai dan pautan ke elemen seterusnya: Sebenarnya, "pautan ke elemen seterusnya" bermakna kita sedang berurusan dengan senarai terpaut tunggal, di mana setiap elemen mengandungi pautan ke yang seterusnya. Iaitu, HashMap menyimpan data dalam pelbagai senarai terpaut tunggal. Tetapi saya akan ambil perhatian segera: apabila satu sel tatasusunan jadual mempunyai pautan ke senarai pautan tunggal serupa yang terdiri daripada lebih daripada satu elemen, ini tidak bagus. Fenomena ini dipanggil perlanggaran . Tetapi perkara pertama dahulu. Mari lihat bagaimana pasangan baharu disimpan menggunakan kaedah put . Pertama, hachCode() kunci diambil. Oleh itu, untuk hashmap berfungsi dengan betul , anda perlu mengambil kelas yang kaedah ini ditindih sebagai kunci. Kod cincang ini kemudiannya digunakan dalam kaedah dalaman - hash() - untuk menentukan nombor dalam saiz tatasusunan jadual . Seterusnya, menggunakan nombor yang diterima, sel tertentu tatasusunan jadual diakses . Di sini kita mempunyai dua kes:

1. Sel kosong - nilai Nod baharu disimpan di dalamnya .
2. Sel tidak kosong - nilai kekunci dibandingkan. Jika ia sama, nilai Nod baharu akan menimpa yang lama, jika ia tidak sama, elemen seterusnya diakses dan dibandingkan dengan kuncinya... Dan seterusnya sehingga nilai baharu menimpa beberapa yang lama atau mencapai penghujung senarai pautan tunggal dan akan disimpan di sana sebagai elemen terakhir.

Apabila mencari elemen dengan kunci ( kaedah get(<key>) ), kod hash kunci dikira, kemudian nilainya dalam tatasusunan menggunakan hash() , dan menggunakan nombor yang terhasil, sel tatasusunan jadual ditemui , di mana carian telah dijalankan dengan menghitung nod dan membandingkan kunci nod yang dikehendaki dengan kunci nod semasa. Operasi dalam Peta dalam situasi yang ideal mempunyai kerumitan algoritma O(1), kerana ia mengakses tatasusunan, dan seperti yang anda ingat, tanpa mengira bilangan elemen, operasi pada tatasusunan mempunyai kerumitan O(1). Tetapi ini adalah ideal. Apabila sel tatasusunan yang digunakan tidak kosong (2) dan sudah ada beberapa nod di sana, kerumitan algoritmik bertukar menjadi linear O(N), kerana kini adalah perlu untuk mengulangi elemen sebelum mencari tempat yang betul. Saya tidak boleh tidak menyebut perkara ini: bermula dengan Java 8, jika nod senarai terpaut tunggal mempunyai lebih daripada 8 elemen (perlanggaran), ia bertukar menjadi pokok binari. Dalam kes ini, kerumitan algoritma tidak lagi menjadi O(N), tetapi O(log(N)) - itu perkara lain, bukan? HashMap ialah topik besar, dan orang suka bertanya soalan mengenainya dalam temu bual. Oleh itu, saya menasihati anda untuk memahaminya secara terperinci (supaya ia melantun dari gigi anda). Secara peribadi, saya tidak pernah menjalani temu duga tanpa soalan HashMap . Anda boleh menemui penyelaman mendalam ke dalam HashMap dalam artikel ini . Itu sahaja untuk hari ini, bersambung...