Perkara yang mungkin mereka tanya semasa temu bual: Struktur data di Jawa. Bahagian 2

BAHAGIAN 1 Sekarang kita bercakap tentang asas yang perlu diketahui oleh setiap pembangun Java. Mengenai pengetahuan klasik dari mana semuanya bermula. Hari ini saya ingin menyentuh salah satu topik asas mana-mana temu bual - struktur data di Jawa . Jadi, daripada berdebar-debar, mari kita mulakan. Saksikan sambungan senarai soalan yang mungkin ditanya kepada anda mengenai topik ini semasa temu duga.

6. Beritahu kami tentang Senarai

Senarai ialah antara muka yang mewakili struktur tertib objek, yang dipanggil senarai. "Helah" struktur ini ialah unsur-unsur yang terkandung dalam Senarai boleh dimasukkan, diubah suai atau dipadamkan oleh indeks, iaitu, pengecam dalaman Senarai . Dalam erti kata lain, indeks bermaksud: "berapa banyak elemen dari permulaan senarai." Elemen Senarai pertama mempunyai indeks 0, yang kedua mempunyai indeks 1, dan seterusnya. Jadi elemen kelima adalah empat elemen dari permulaan senarai. Seperti yang dinyatakan di atas, susunan item yang ditambahkan pada senarai adalah penting. Itulah sebabnya struktur data dipanggil senarai . Kami menyenaraikan kaedah unik untuk struktur ini yang bertujuan untuk bekerja dengan elemen mengikut indeks:

• get - mengembalikan elemen pada kedudukan yang ditentukan (mengikut nilai indeks),
• keluarkan - mengalih keluar elemen pada kedudukan yang ditentukan,
• set - menggantikan elemen pada kedudukan yang ditentukan dengan elemen yang dinyatakan dalam kaedah.

Pelaksanaan utama ialah ArrayList dan LinkedList . Kami akan bercakap lebih lanjut tentang mereka sedikit kemudian. Vektor ialah senarai yang selamat untuk benang, jadi setiap kaedah dalam kelas ini disegerakkan. Tetapi perlu diingat bahawa jika anda ingin mendapatkan beberapa tindakan senarai, anda akan menyegerakkan keseluruhan urutan operasi. Dan menyegerakkan operasi individu adalah kurang selamat dan lebih perlahan. Sudah tentu, Vector juga mempunyai overhed penguncian, walaupun anda tidak memerlukan kunci itu. Oleh itu, kelas ini kini dianggap usang dan tidak digunakan. By the way: ArrayList adalah serupa dengan Vector , tetapi tidak menggunakan penguncian, jadi ia digunakan di mana-mana sahaja. Stack ialah subkelas kelas Vektor dengan satu pembina lalai dan semua kaedah kelas Vector , ditambah dengan beberapa kelasnya sendiri (kita akan membincangkannya kemudian). Sebagai contoh, anda boleh bayangkan proses itu sebagai timbunan folder dengan dokumen. Anda meletakkan satu folder di bahagian atas timbunan dan anda hanya boleh mengambil folder ini dalam susunan terbalik, bermula dari atas. Sebenarnya, ini adalah mekanisme jenis LIFO , iaitu, Last In First Out , yang terakhir datang ialah yang pertama keluar. Tindanan melaksanakan kaedahnya sendiri:

• tolak - menambah elemen yang diluluskan ke bahagian atas timbunan;
• mengintip - mengembalikan elemen yang berada di bahagian atas timbunan;
• pop - juga mengembalikan elemen yang berada di bahagian atas timbunan, tetapi mengeluarkannya;
• kosong - menyemak sama ada timbunan kosong - benar atau tidak - palsu ;
• carian - mencari timbunan untuk elemen tertentu. Jika elemen ditemui, nombor jujukannya berbanding bahagian atas timbunan dikembalikan. Jika elemen tidak dijumpai, nilai -1 dikembalikan.

Pada masa ini, subkelas Stack sebenarnya tidak digunakan kerana kesederhanaan dan ketidakfleksibelannya, tetapi, bagaimanapun, anda mungkin menemuinya. Contohnya, apabila anda menerima beberapa ralat dan dalam konsol anda melihat timbunan mesej mengenainya. Anda boleh membaca lebih lanjut mengenai tindanan dan baris gilir dalam artikel ini .

7. Beritahu kami tentang Peta

Seperti yang dinyatakan di atas, Peta ialah koleksi yang mempunyai struktur antara muka yang berasingan dan pelaksanaannya. Ia berasingan kerana di sini nilai tidak disimpan satu demi satu, tetapi dalam pasangan "nilai-kunci". Kaedah Peta Asas :

• put(K kunci, nilai V) - menambah elemen pada Peta;
• get(Object key) - cari nilai dengan kunci;
• containsKey(Object key) — menyemak Peta untuk kehadiran kunci ini;
• containsValue(Nilai objek) - menyemak Peta untuk kehadiran nilai ini;
• remove(Object key) - mengalih keluar nilai dengan kuncinya.

Seperti yang anda lihat, kebanyakan operasi berfungsi dengan menggunakan kunci. Sebagai peraturan, objek tidak berubah dipilih sebagai kunci . Contoh tipikal objek ini ialah String . Pelaksanaan Peta Asas :

1. HashMap - direka untuk menyimpan nilai dalam susunan rawak, tetapi membolehkan anda mencari elemen peta dengan cepat. Membolehkan anda menentukan kunci menggunakan kata kunci nol , tetapi tidak lebih daripada sekali, kerana pasangan dengan kekunci yang sama ditulis di atas satu sama lain. Syarat utama ialah keunikan kunci: nilai boleh diulang (mungkin terdapat beberapa nilai nol).
2. LinkedHashMap ialah analog HashMap yang menyimpan nilai mengikut susunan ia ditambahkan. Sehubungan itu, seperti LinkedList , ia mempunyai pengepala - ketua senarai terpaut berganda. Apabila dimulakan, ia menunjuk kepada dirinya sendiri.

   LinkedHashMap juga mempunyai accessOrder yang menentukan cara elemen akan diakses apabila iterator digunakan. Jika accessOrder adalah palsu, akses akan dilakukan mengikut susunan elemen dimasukkan. Jika benar, elemen akan berada dalam susunan akses terakhir (elemen akses terakhir akan diletakkan pada penghujung).

3. TreeMap ialah Peta yang menyusun elemen mengikut nilai utama. Sama seperti TreeSet , tetapi untuk pasangan berdasarkan nilai utama. Untuk menetapkan peraturan pengisihan TreeMap , kunci mesti melaksanakan antara muka Sebanding . Jika tidak, perlu ada Pembanding Berorientasikan Kunci (yang dinyatakan dalam TreeMap constructor ), TreeSet - dilaksanakan dengan objek TreeMap di dalamnya, di mana, sebenarnya, semua keajaiban berlaku.

   Anda boleh membaca lebih lanjut tentang menyusun dalam TreeMap menggunakan pokok merah-hitam dalam artikel tentang ciri TreeMap .

4. Hashtable adalah serupa dengan HashMap , tetapi tidak membenarkan null disimpan sama ada sebagai kunci atau nilai. Ia disegerakkan dengan teliti dari sudut pandangan berbilang benang, yang seterusnya bermakna ia selamat dari sudut pandangan berbilang benang. Tetapi pelaksanaan ini sudah lapuk dan perlahan, jadi kini anda tidak akan melihat Hashtable dalam lebih kurang projek baharu.

8. ArrayList lwn LinkedList. Mana satu lebih baik digunakan?

Soalan ini mungkin yang paling popular pada struktur data dan membawa bersamanya beberapa perangkap. Sebelum menjawabnya, mari kita ketahui lebih lanjut tentang struktur data ini. ArrayList melaksanakan antara muka Senarai dan beroperasi pada tatasusunan dalaman yang dikembangkan mengikut keperluan. Apabila tatasusunan dalaman diisi sepenuhnya, dan elemen baharu perlu dimasukkan, tatasusunan baharu dicipta dengan saiz (oldSize * 1.5) +1. Selepas ini, semua data daripada tatasusunan lama disalin ke elemen baharu + baharu, dan yang lama akan dipadamkan oleh pengumpul sampah . Kaedah tambah menambah elemen pada sel kosong terakhir tatasusunan. Iaitu, jika kita sudah mempunyai 3 elemen di sana, ia akan menambah yang seterusnya ke sel ke-4. Mari kita lihat prestasi kaedah asas:

• get(int index) - mengambil elemen dalam tatasusunan mengikut indeks adalah yang terpantas dalam O(1) ;
• add(Object obj) - jika terdapat ruang yang mencukupi dalam tatasusunan dalaman untuk elemen baharu, maka dengan sisipan biasa O(1) masa akan dibelanjakan , kerana penambahan disasarkan ke sel terakhir.

  Jika kita perlu mencipta tatasusunan baharu dan menyalin kandungan ke dalamnya, maka masa kita akan berkadar terus dengan bilangan elemen dalam tatasusunan O(n) ;

• remove(int index) - apabila mengalih keluar elemen, contohnya, dari tengah, kita akan mendapat masa O(n/2), kerana kita perlu mengalihkan elemen ke sebelah kanannya satu sel ke belakang. Sehubungan itu, jika memadam dari permulaan senarai, maka O(n), dari hujung - O(1);
• add(int index, Object obj) - situasi yang serupa dengan pemadaman: apabila menambah ke tengah, kita perlu mengalihkan elemen di sebelah kanan satu sel ke hadapan, jadi masanya ialah O(n/2). Sudah tentu, dari awal - O(n), dari akhir - O(1);
• set(int index, Object obj) - di sini keadaannya berbeza, kerana anda hanya perlu mencari elemen yang diingini dan menulis di atasnya tanpa memindahkan yang lain, jadi O(1).

Baca lebih lanjut mengenai ArrayList dalam artikel ini . LinkedList melaksanakan dua antara muka sekali gus - List dan Queue , dan oleh itu mempunyai sifat dan kaedah yang wujud dalam kedua-dua struktur data. Dari Senarai dia mengambil akses kepada elemen mengikut indeks, dari Queue - kehadiran "kepala" dan "ekor". Secara dalaman, ia dilaksanakan sebagai struktur data yang mewakili senarai terpaut dua kali. Iaitu, setiap elemen mempunyai pautan ke yang seterusnya dan sebelumnya, kecuali untuk "ekor" dan "kepala".

• get(int index) - apabila mencari elemen yang berada di tengah-tengah senarai, ia mula mencari semua elemen mengikut urutan sehingga yang dikehendaki ditemui. Secara logiknya, carian harus mengambil O(n/2) , tetapi LinkedList juga mempunyai ekor, jadi carian dijalankan secara serentak dari kedua-dua belah pihak. Sehubungan itu, masa dikurangkan kepada O(n/4) .

  Jika elemen itu hampir dengan permulaan senarai atau penghujung, maka masanya ialah O(1) ;

• add(Object obj) - apabila menambah elemen baharu, elemen "ekor" akan mempunyai pautan ke elemen seterusnya ditambah, dan elemen baharu akan menerima pautan ke elemen sebelumnya ini dan menjadi "ekor" baharu. Sehubungan itu, masanya ialah O(1) ;
• remove(int index) - logik serupa dengan kaedah get(int index) . Untuk mengalih keluar elemen daripada bahagian tengah senarai, anda mesti mencarinya terlebih dahulu. Ini sekali lagi O(n/4) , manakala pemadaman itu sendiri sebenarnya tidak mengambil apa-apa, kerana ia hanya mengubah penunjuk objek jiran (mereka mula merujuk antara satu sama lain). Jika elemen berada di permulaan atau di penghujung, sekali lagi - O(1) ;
• add(int index, Object obj) dan set(int index, Object obj) - kaedah akan mempunyai kerumitan masa yang sama untuk get(int index) , kerana kebanyakan masa dihabiskan untuk mencari elemen. Oleh itu, untuk bahagian tengah senarai - O(n/4) , untuk permulaan - O(1).

Maklumat lanjut tentang bekerja dengan LinkedList diterangkan dalam artikel ini . Mari kita lihat semua ini dalam jadual: Seperti yang anda mungkin sudah faham, adalah mustahil untuk menjawab soalan ini dengan jelas. Lagipun, dalam situasi yang berbeza mereka bekerja pada kelajuan yang berbeza. Oleh itu, apabila anda ditanya soalan seperti ini, anda harus segera bertanya apakah senarai ini akan difokuskan dan operasi yang paling kerap dilakukan. Bermula dari ini, berikan jawapan, tetapi dengan penjelasan mengapa ini berlaku. Mari ringkaskan perbandingan kami: ArrayList:

• pilihan terbaik jika operasi yang paling kerap adalah mencari elemen, menimpa elemen;
• pilihan yang paling teruk jika operasi adalah sisipan dan pemadaman pada permulaan-tengah, kerana operasi peralihan elemen di sebelah kanan akan berlaku.

Senarai Terpaut:

• pilihan terbaik jika operasi kerap kami adalah sisipan dan pemadaman pada permulaan-tengah;
• pilihan terburuk jika operasi yang paling biasa adalah mencari.

9. Bagaimanakah elemen disimpan dalam HashMap?

Koleksi HashMap mengandungi jadual Node[] tatasusunan dalaman , sel yang turut dipanggil baldi . Nod mengandungi:

• kunci - pautan ke kunci,
• nilai - merujuk kepada nilai,
• hash - nilai hash,
• pautan seterusnya ke Nod seterusnya .

Satu sel tatasusunan table[] mungkin mengandungi rujukan kepada objek Nod dengan pautan ke elemen Nod seterusnya , dan ia mungkin mempunyai pautan kepada yang lain, dan seterusnya... Akibatnya, elemen Nod ini boleh membentuk senarai pautan tunggal , dengan elemen dengan pautan ke seterusnya. Dalam kes ini, nilai cincang bagi elemen rantaian yang sama adalah sama. Selepas penyimpangan yang singkat, mari kita lihat bagaimana elemen disimpan dalam HashMap :

1. Kekunci disemak untuk nol . Jika ia adalah null , maka kunci akan disimpan dalam sel table[0] kerana kod cincang untuk null sentiasa 0.
2. Jika kuncinya bukan null , maka kaedah hashcode() objek utama dipanggil , yang akan mengembalikan kod cincangnya. Kod cincang ini digunakan untuk menentukan sel tatasusunan di mana objek Node akan disimpan.
3. Seterusnya, kod cincang ini diletakkan dalam kaedah hash() dalaman , yang mengira kod cincang, tetapi dalam saiz tatasusunan jadual[] .
4. Seterusnya, bergantung pada nilai cincang, Node diletakkan dalam sel tertentu dalam tatasusunan table[] .
5. Jika sel jadual[] yang digunakan untuk menyimpan elemen Nod semasa tidak kosong, tetapi sudah mempunyai beberapa elemen, maka elemen Nod akan diulang pada nilai seterusnya sehingga elemen terakhir dicapai. Iaitu, bidang yang seterusnya adalah null .

   Semasa carian ini, kunci objek Node yang dilindungi dibandingkan dengan kekunci yang sedang dicari:

   • jika padanan ditemui, carian akan ditamatkan dan Nod baharu akan menimpa Nod di mana padanan ditemui (hanya medan nilainya akan ditimpa );
   • jika tiada padanan utama ditemui, maka Nod baharu akan menjadi yang terakhir dalam senarai ini, dan yang sebelumnya akan mempunyai pautan seterusnya kepadanya.

Soalan sering timbul semasa temu bual: apakah konflik ? Keadaan apabila sel tatasusunan jadual[] tidak menyimpan satu elemen, tetapi rantaian dua atau lebih, dipanggil perlanggaran . Dalam kes biasa di mana hanya satu elemen disimpan dalam satu jadual[] sel , mengakses elemen HashMap mempunyai kerumitan masa O(1) yang tetap . Tetapi apabila sel dengan elemen yang diingini mengandungi rantaian unsur ( collision ), maka O(n) , kerana dalam kes ini masa adalah berkadar terus dengan bilangan elemen yang diisih.

10. Terangkan iterator

Dalam rajah pemetaan hierarki Koleksi di atas, antara muka Koleksi adalah tempat keseluruhan hierarki bermula, tetapi dalam praktiknya ia tidak begitu. Koleksi mewarisi daripada antara muka dengan kaedah iterator() , yang mengembalikan objek yang melaksanakan antara muka Iterator<E> . Antara muka Iterator kelihatan seperti ini:

public interface Iterator <E>{

    E next();
    boolean hasNext();
    void remove();
}

next() - dengan memanggil kaedah ini, anda boleh mendapatkan elemen seterusnya. hasNext() - membolehkan anda mengetahui sama ada terdapat elemen seterusnya, dan sama ada penghujung koleksi telah dicapai. Dan apabila masih terdapat elemen, hasNext() akan mengembalikan true . Biasanya, hasNext() dipanggil sebelum kaedah next() , kerana next() akan membuang NoSuchElementException apabila ia mencapai penghujung collection . remove() - Mengalih keluar elemen yang telah diambil oleh panggilan terakhir ke next() . Tujuan Iterator adalah untuk mengulangi elemen. Sebagai contoh:

Set<Integer> values = new TreeSet<>();
  values.add(5);
values.add(3);
values.add(6);
values.add(8);
values.add(2);
values.add(4);
values.add(1);
values.add(7);

Iterator<Integer> iter = values.iterator();
while(iter.hasNext()){
  System.out.println(iter.next());
}

Sebenarnya, gelung untuk-setiap dilaksanakan di bawah hud menggunakan iterator. Anda boleh membaca lebih lanjut mengenai perkara ini di sini . List menyediakan versi iteratornya sendiri, tetapi versi yang lebih sejuk dan lebih canggih - ListIterator . Antara muka ini memanjangkan Iterator dan mempunyai kaedah tambahan:

• hasPrevious akan mengembalikan benar jika terdapat elemen sebelumnya dalam koleksi, palsu sebaliknya;
• sebelumnya mengembalikan elemen semasa dan bergerak ke yang sebelumnya; jika tiada, maka NoSuchElementException dibuang;
• add akan memasukkan objek yang diluluskan sebelum elemen yang akan dikembalikan oleh panggilan seterusnya ke next() ;
• set memberikan elemen semasa rujukan kepada objek yang diluluskan;
• nextIndex mengembalikan indeks elemen seterusnya. Jika tidak ada perkara sedemikian, maka saiz senarai dikembalikan;
• previousIndex mengembalikan indeks elemen sebelumnya. Jika tiada, maka nombor -1 dikembalikan.

Nah, itu sahaja untuk saya hari ini. Saya harap selepas membaca artikel ini anda lebih dekat dengan impian anda - untuk menjadi pemaju.