Meneroka soalan dan jawapan daripada temu duga kerja untuk jawatan pembangun Java. Bahagian 9

Menjadi seorang pengaturcara bukan mudah. Sentiasa ada sesuatu yang baru untuk dipelajari. Dan, seperti dalam mana-mana usaha lain, perkara yang paling sukar adalah untuk memulakan, untuk mengambil langkah pertama ke arah matlamat anda. Tetapi kerana anda sudah berada di sini dan membaca artikel ini, anda telah menyelesaikan langkah pertama. Ini bermakna kini anda perlu bergerak ke arah matlamat anda dengan sengaja, tanpa memperlahankan atau melencong ke tepi. Saya menganggap matlamat anda adalah untuk menjadi pembangun Java atau meningkatkan pengetahuan anda jika anda sudah menjadi pembangun. Jika ya, mari kita teruskan menangani senarai luas soalan temu duga pembangun Java. Jom sambung!

Koleksi

84. Beritahu kami tentang iterator dan cara ia digunakan

Koleksi ialah topik kegemaran dalam mana-mana temu bual pembangun Java. Apabila menjawab soalan tentang hierarki koleksi, calon sering mengatakan bahawa ia bermula dengan antara muka Koleksi . Tetapi ini tidak begitu. Terdapat satu lagi antara muka satu tahap di atas: Iterable . Antara muka ini terdiri daripada kaedah iterator() , yang membolehkan anda mengakses objek Iterator untuk koleksi semasa. Dan apakah sebenarnya objek Iterator ini ? Objek Iterator menyediakan keupayaan untuk bergerak melalui koleksi dan mengulang elemennya, dan pengguna tidak perlu mengetahui butiran pelaksanaan khusus koleksi. Dalam erti kata lain, ia adalah sejenis penunjuk kepada elemen koleksi, seolah-olah ia mengintip ke dalam pada salah satu daripadanya. Iterator mempunyai kaedah seperti:

• hasNext() — mengembalikan benar jika lelaran mempunyai elemen lain (kaedah ini memberitahu anda apabila anda telah mencapai penghujung koleksi);

• next() — mengembalikan item seterusnya dalam lelaran. Jika tidak ada, maka NoSuchElementException dibuang. Ini bermakna sebelum anda menggunakan kaedah ini, sebaiknya gunakan kaedah hasNext() untuk memastikan unsur seterusnya wujud;

• remove() — mengalih keluar daripada koleksi elemen terakhir yang diterima menggunakan kaedah next() . Jika next() tidak pernah dipanggil, maka memanggil remove() akan menyebabkan IllegalStateException dibuang;

• forEachRemaining(<Consumer>) — melaksanakan tindakan yang diluluskan pada setiap elemen koleksi (kaedah ini muncul dalam Java 8).

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

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 perkara berikut: Ini bermakna unsur-unsur telah berjaya dialih keluar. Sebaik sahaja anda mendapat iterator, anda boleh menggunakan kaedah untuk memaparkan semua elemen pada skrin:

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

Tetapi sebaik sahaja kita melakukan ini, lelaran menjadi tidak sesuai untuk kegunaan selanjutnya: ia telah melintasi keseluruhan senarai, dan lelaran biasa tidak mempunyai kaedah untuk mengundur ke belakang. Dan itu menjadikan perbincangan yang bagus tentang LinkedList , khususnya, kaedah listIterator() nya , yang mengembalikan jenis iterator yang dipertingkatkan: ListIterator . Sebagai tambahan kepada kaedah iterator biasa (standard), jenis ini mempunyai yang berikut:

• add(<Element>) — menambah elemen baharu pada senarai;

• hasPrevious() — mengembalikan true jika terdapat elemen yang terletak sebelum elemen seterusnya (jika terdapat elemen sebelumnya);

• nextIndex() — mengembalikan indeks elemen seterusnya;

• previous() — mengembalikan elemen sebelumnya (yang sebelum elemen seterusnya);

• previousIndex mengembalikan indeks elemen sebelumnya.

• set(<Element>) — menggantikan elemen terakhir yang dikembalikan oleh next() atau previous() .

Seperti yang anda lihat, iterator ini mempunyai fungsi yang lebih menarik: ia membolehkan anda berjalan di kedua-dua arah dan memberikan kebebasan yang besar apabila bekerja dengan elemen. Anda juga harus tahu bahawa apabila orang bercakap tentang iterator, mereka kadangkala bermaksud corak reka bentuk itu sendiri.

85. Apakah hierarki koleksi yang wujud dalam Rangka Kerja Koleksi Java?

Terdapat dua hierarki koleksi di Jawa. Hierarki pertama ialah hierarki Koleksi, yang mempunyai struktur berikut: Ia dibahagikan kepada subkoleksi berikut:

• Set ialah antara muka yang menerangkan set, struktur data yang mengandungi unsur unik (tidak berulang) tidak tertib. Antara muka ini mempunyai beberapa pelaksanaan standard: TreeSet , HashSet dan LinkedHashSet .

• Senarai ialah antara muka yang menerangkan struktur data yang menyimpan urutan objek yang tersusun. Objek dalam Senarai boleh dimasukkan dan dialih keluar oleh indeksnya dalam senarai (seperti tatasusunan, tetapi dengan saiz semula dinamik). Antara muka ini juga mempunyai beberapa pelaksanaan standard: ArrayList , Vector ( tidak digunakan lagi dan tidak digunakan sebenarnya ), dan LinkedList .

• Baris gilir ialah antara muka yang menerangkan struktur data yang menyimpan item dalam baris gilir Mula-mula Keluar Dahulu (FIFO) . Antara muka ini mempunyai pelaksanaan standard berikut: LinkedList (betul, ia juga melaksanakan Queue ) dan PriotityQueue .

Hierarki koleksi kedua ialah hierarki Peta , yang mempunyai struktur berikut: Hierarki koleksi ini tidak mempunyai pembahagian kepada subkoleksi (kerana hierarki Peta itu sendiri adalah sesuatu daripada subkoleksi yang berdiri sendiri). Pelaksanaan Peta standard ialah Hashtable (ditamatkan), LinkedHashMap dan TreeMap . Dalam amalan, apabila orang bertanya tentang Koleksi , mereka biasanya bermaksud kedua-dua hierarki.

86. Apakah struktur dalaman ArrayList?

ArrayList adalah seperti tatasusunan, tetapi ia boleh berkembang secara dinamik . Apakah maksudnya? Di bawah tudung, ArrayList menggunakan tatasusunan biasa, iaitu ia menyimpan elemennya dalam tatasusunan dalaman yang saiz lalainya ialah 10 sel. Setelah tatasusunan dalaman penuh, tatasusunan baharu dicipta. Saiz tatasusunan baharu ditentukan oleh formula ini:

<size of the current array> * 3 / 2 + 1

Jadi, jika saiz tatasusunan kami ialah 10, maka saiz tatasusunan baharu ialah: 10 * 3 / 2 + 1 = 16. Kemudian semua nilai daripada tatasusunan asal (lama) disalin ke dalamnya menggunakan terbina dalam Kaedah System.arraycopy() dan tatasusunan asal dipadamkan. Secara ringkasnya, begitulah cara ArrayList melaksanakan pensaiz semula dinamik. Mari kita pertimbangkan kaedah ArrayList yang paling popular : 1. add(<Element>) — menambah elemen pada penghujung tatasusunan (dalam sel kosong terakhir), selepas mula-mula menyemak sama ada terdapat sel yang tersedia dalam tatasusunan. Jika tidak, tatasusunan baharu dibuat, dan unsur-unsur akan disalin ke dalamnya. Kerumitan masa operasi ini ialah O(1). Terdapat kaedah tambah(<Indeks>, <Elemen>) yang serupa . Ia menambahkan elemen bukan pada penghujung senarai (tatasusunan), tetapi pada sel khusus yang ditunjukkan oleh indeks yang masuk sebagai hujah. Dalam kes ini, kerumitan masa akan berbeza-beza bergantung pada tempat anda menambah:

• jika penambahan itu hampir dengan permulaan senarai, maka kerumitan masa 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, maka ia akan menjadi O(N/2), kerana kita hanya perlu mengalihkan separuh daripada item senarai satu sel ke kanan.

Iaitu, kerumitan masa kaedah ini berjulat dari O(1) hingga O(N), bergantung pada tempat elemen dimasukkan. 2. set(<Index>, <Element>) — menulis elemen ke kedudukan yang ditentukan dalam senarai. Jika elemen sudah ada pada kedudukan itu, kaedah akan menimpanya. Kerumitan masa operasi ini ialah O(1), kerana ia tidak melibatkan sebarang operasi anjakan: kami hanya menggunakan indeks untuk mengira alamat sel dalam tatasusunan, yang mempunyai kerumitan O(1), dan kemudian tulis elemen baharu . 3. remove(<index>) — mengalih keluar elemen mengikut indeksnya dalam tatasusunan dalaman. Apabila mengalih keluar item yang tidak berada di penghujung senarai, semua item di sebelah kanan item yang dipadam mesti dialihkan satu sel ke kiri untuk menutup jurang yang terhasil daripada pemadaman. Sehubungan itu, kerumitan masa akan sama seperti untuk add(<Index>, <Element>) apabila elemen ditambah di tengah: O(N/2). Lagipun, anda perlu mengalihkan separuh daripada elemen satu sel ke kiri. Dan jika kita bercakap tentang permulaan, maka O(N). Atau jika pada akhirnya, maka O(1), kerana anda tidak perlu memindahkan apa-apa.

87. Apakah struktur dalaman LinkedList?

ArrayList mengandungi elemen dalam tatasusunan dalaman, tetapi LinkedList menyimpannya dalam senarai berganda. Ini bermakna setiap elemen mengandungi pautan ke elemen sebelumnya dan ke elemen seterusnya . Elemen pertama tidak memaut ke elemen sebelumnya (lagipun, ia adalah yang pertama). Ia juga dianggap sebagai ketua senarai, dan objek LinkedList mempunyai rujukan langsung kepadanya. Begitu juga, elemen terakhir tidak mempunyai elemen seterusnya, kerana ia adalah ekor senarai. Objek LinkedList juga merujuknya secara langsung. Ini bermakna kerumitan masa untuk mengakses kepala atau ekor senarai ialah O(1). Dalam ArrayList , jika senarai bertambah, maka tatasusunan dalaman akan berkembang. Di sini semuanya lebih mudah: menambah rujukan adalah semudah menukar beberapa pautan. Mari lihat beberapa kaedah LinkedList yang paling banyak digunakan: 1. add(<Element>) — menambah elemen pada penghujung senarai, iaitu selepas elemen terakhir (5), pautan ke elemen baharu akan ditambah seperti seterusnya . Rujukan sebelumnya dalam elemen baharu akan menunjuk kepada elemen (5) yang kini mendahuluinya dalam senarai. Kerumitan masa operasi ini ialah O(1), kerana kami hanya memerlukan pautan ke elemen terakhir, dan seperti yang anda akan ingat, objek LinkedList mempunyai rujukan terus kepada ekor, dan mengaksesnya mempunyai kerumitan masa malar yang minimum. 2. add(<Index>, <Element>) — menambah elemen mengikut indeks. Apabila menambah elemen, katakan, di tengah-tengah senarai, kaedah ini mula-mula melelang ke atas elemen dari kepala dan ekor (pada kedua-dua arah) sehingga tempat yang dikehendaki ditemui. Jika kita menambah elemen antara elemen ketiga dan keempat (dalam gambar di atas), maka pautan seterusnya elemen ketiga akan menghala ke elemen baharu. Dan elemen yang baru ditambah sebelumnya akan menunjuk kepada yang ketiga. Seterusnya, pautan sebelumnya elemen keempat lama kini akan menghala ke elemen baharu, dan pautan seterusnya elemen baharu akan menghala ke elemen keempat baharu: Kerumitan masa kaedah ini bergantung pada indeks elemen baharu:

• jika ia hampir dengan kepala atau ekor, operasi akan menghampiri O(1), kerana ia sebenarnya tidak perlu untuk melelaran ke atas unsur;
• jika ia dekat dengan tengah, maka kita akan mempunyai O(N/2), kerana kaedah akan mencari dari kepala dan ekor pada masa yang sama sehingga elemen yang dikehendaki ditemui.

3. set(<Index>, <Element>) — menulis elemen ke kedudukan yang ditentukan dalam senarai. Kerumitan masa operasi ini akan berjulat dari O(1) hingga O(N/2), sekali lagi bergantung pada jarak elemen baharu dengan kepala, ekor atau tengah. 4. remove(<index>) — mengalih keluar elemen daripada senarai dengan menjadikannya supaya elemen sebelum yang dipadam ( sebelumnya ) kini merujuk kepada elemen selepas yang dipadamkan ( seterusnya ). Dan sebaliknya, iaitu elemen selepas yang dipadam kini merujuk kepada yang sebelum yang dipadam: Proses ini adalah bertentangan dengan penambahan mengikut indeks ( add(<Index>, <Element>) ).

88. Apakah struktur dalaman HashMap?

Ini mungkin salah satu soalan temu duga paling popular untuk ditanya kepada calon pembangun Java. HashMap berfungsi dengan pasangan nilai kunci . Bagaimanakah ia disimpan di dalam HashMap itu sendiri? HashMap mempunyai tatasusunan dalaman nod :

Node<K,V>[] table

Secara lalai, saiz tatasusunan ialah 16, dan ia berganda setiap kali ia diisi dengan elemen (iaitu, apabila LOAD_FACTOR dicapai ; ia menentukan ambang untuk seberapa penuh tatasusunan boleh mendapat - secara lalai, ia adalah 0.75 ) . Setiap nod menyimpan cincang kunci, kunci, nilai dan rujukan kepada elemen seterusnya: Dalam kes ini, "rujukan kepada elemen seterusnya" bermakna kita sedang berurusan dengan senarai pautan tunggal, di mana setiap elemen mengandungi pautan ke seterusnya. Dalam erti kata lain, HashMap menyimpan datanya dalam pelbagai senarai pautan tunggal. Tetapi izinkan saya segera mengatakan bahawa apabila sel tatasusunan jadual mempunyai senarai pautan tunggal yang terdiri daripada lebih daripada satu elemen, itu tidak baik. Fenomena ini dipanggil perlanggaran . Tetapi perkara pertama dahulu. Mari lihat bagaimana pasangan baharu disimpan menggunakan kaedah put . Pertama, kaedah mendapat hashCode() kunci . Ini menunjukkan bahawa agar HashMap berfungsi dengan betul, kunci yang anda gunakan mestilah kelas yang mengatasi kaedah ini. Kod cincang ini kemudiannya digunakan dalam kaedah cincang dalaman() untuk menentukan indeks beberapa sel dalam tatasusunan jadual. Indeks yang terhasil membolehkan kita mengakses sel tertentu tatasusunan jadual. Kami mempunyai dua kes di sini:

1. Sel kosong — dalam kes ini, nilai Nod baharu disimpan di dalamnya.
2. Sel tidak kosong — dalam kes ini, nilai kekunci dibandingkan. Jika ia adalah sama, maka nilai Nod baharu akan menimpa nilai yang lama; jika tidak sama, maka seterusnya diakses , dan kuncinya dibandingkan... Dan seterusnya, sehingga nilai baharu sama ada menimpa beberapa nilai lama atau kita sampai ke penghujung senarai pautan tunggal dan kemudian menyimpan nilai baharu di sana sebagai elemen terakhir.

Apabila mencari elemen dengan kunci (menggunakan kaedah get(<key>) ), hashCode() kunci dikira, dan kemudian indeksnya dalam tatasusunan dikira menggunakan hash() . Nombor yang terhasil ialah indeks sel dalam tatasusunan jadual , yang kemudiannya kita cari dengan mengulangi nod dan membandingkan kekunci nod yang dikehendaki dengan kunci nod semasa. Sebaik-baiknya, operasi Peta mempunyai kerumitan algoritma O(1), kerana kami sedang mengakses tatasusunan, dan, seperti yang anda akan ingat, ialah O(1), tanpa mengira bilangan elemen yang terkandung di dalamnya. Tetapi kami tidak berurusan dengan kes yang ideal. Apabila sel tidak kosong (2) dan sudah menyimpan beberapa nod, maka kerumitan algoritmik menjadi O(N) (linear), kerana kini adalah perlu untuk mengulangi elemen sebelum kita mencari tempat yang betul. Saya tidak boleh tidak menyebut bahawa bermula di Java 8, jika nod dalam bentuk senarai berpaut tunggal mempunyai lebih daripada 8 elemen (perlanggaran), maka ia akan ditukar menjadi pokok binari. Dalam kes ini, kerumitan algoritma bukan lagi O(N), tetapi O(log(N)) — dan itu adalah perkara lain, bukan? HashMap ialah topik besar, dan orang suka bertanya soalan mengenainya dalam temu duga kerja. Jadi, saya cadangkan anda mengetahuinya seperti belakang tangan anda. Secara peribadi, saya tidak pernah mempunyai temu bual yang tidak termasuk soalan pada HashMap . Itu sahaja untuk hari ini. Akan bersambung...