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

hello! Tidak kira bagaimana anda melihatnya, anda tidak boleh menjadi pembangun tanpa berjaya lulus temu duga masuk teknikal. Terdapat banyak teknologi yang berkaitan dengan Java, dan adalah mustahil untuk mempelajari segala-galanya. Sebagai peraturan, sesuatu yang khusus ditanya semasa temu duga hanya jika mereka mencari pembangun dengan pengalaman yang baik dalam beberapa rangka kerja yang penting untuk projek itu. Jika ini benar, anda akan dikejar di sekitar rangka kerja ini pada kelajuan penuh, anda tidak ragu-ragu mengenainya. Tetapi 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. Cari senarai soalan yang mungkin ditanya tentang topik ini semasa temu duga.

1. Beritahu kami sedikit tentang struktur data

Struktur data ialah stor data yang mengandungi maklumat berstruktur dengan cara tertentu. Struktur ini direka bentuk untuk prestasi cekap operasi tertentu. Contoh biasa struktur data ialah:

• tatasusunan,
• timbunan,
• beratur,
• senarai berkaitan,
• graf,
• pokok,
• pokok awalan,
• jadual hash.

Anda boleh mengetahui lebih lanjut tentang mereka di sini dan di sini . Data ialah komponen utama dalam atur cara dan struktur membenarkan data ini disimpan dalam bentuk khusus dan berstruktur dengan jelas. Apa sahaja yang dilakukan oleh aplikasi anda, aspek ini akan sentiasa ada di dalamnya: jika ia adalah kedai web, maka maklumat tentang produk akan disimpan, jika ia adalah rangkaian sosial, data tentang pengguna dan fail, dan sebagainya.

2. Apakah yang anda tahu tentang Arrays?

Tatasusunan ialah bekas untuk menyimpan nilai dari jenis yang sama, bilangan yang telah ditentukan terlebih dahulu. Contoh mencipta tatasusunan dengan nilai rentetan:

String[] strArray = {"Java","is","the","best","language"};

Apabila mencipta tatasusunan, memori diperuntukkan untuk semua elemennya: lebih banyak sel untuk elemen pada mulanya ditentukan, lebih banyak memori akan diperuntukkan. Jika tatasusunan kosong dengan bilangan sel tertentu dicipta, maka semua elemen tatasusunan akan diberikan nilai lalai. Sebagai contoh:

int[] arr = new int[10];

Jadi, untuk tatasusunan dengan unsur jenis boolean , nilai awal ( lalai ) akan palsu , untuk tatasusunan dengan nilai angka - 0, dengan unsur jenis char - \u0000 . Untuk tatasusunan jenis kelas (objek) - null (bukan rentetan kosong - “” tetapi khususnya null ). Iaitu, dalam contoh di atas, semua nilai tatasusunan arr akan menjadi 0 sehingga ia ditentukan secara langsung. Tidak seperti koleksi, tatasusunan tidak dinamik. Sebaik sahaja tatasusunan saiz tertentu diisytiharkan, saiz itu sendiri tidak boleh diubah. Untuk menambah elemen baharu pada tatasusunan, anda perlu mencipta tatasusunan baharu yang lebih besar dan menyalin semua elemen daripada yang lama ke dalamnya (beginilah cara ArrayList berfungsi). Terdapat satu perkara yang tidak semua orang tahu dan di mana anda boleh ditangkap dengan baik. Terdapat dua jenis pembolehubah dalam Java - jenis mudah dan rujukan kepada objek lengkap. Yang manakah antara ini adalah tatasusunan? Sebagai contoh, di sini:

int[] arr = new int[10];

Nampaknya semuanya mudah - ini adalah 10 elemen int . Jadi, kita boleh mengatakan bahawa ini adalah jenis yang mudah? Tidak kira bagaimana keadaannya. Di Java, tatasusunan ialah objek, dicipta secara dinamik dan boleh diberikan kepada pembolehubah jenis Objek. Semua kaedah kelas Objek boleh dipanggil pada tatasusunan. Jadi kita juga boleh menulis:

Object arr = new int[]{7,5,4,3};
System.out.println(arr.toString());

Apabila mengeluarkan ke konsol anda mungkin mendapat sesuatu seperti: Baca lebih lanjut mengenai ciri tatasusunan dalam Java dalam artikel ini tentang Tatasusunan Java . Untuk menyatukan pengetahuan anda, anda boleh menyelesaikan beberapa masalah daripada koleksi ini .

3. Terangkan hierarki koleksi

Koleksi digunakan dalam situasi di mana anda memerlukan fleksibiliti semasa bekerja dengan data. Koleksi boleh menambah elemen, mengalih keluar elemen dan melakukan banyak operasi lain. Terdapat banyak pelaksanaan yang berbeza di Java, dan kami hanya perlu memilih koleksi yang sesuai untuk situasi semasa. Biasanya, apabila anda menyebut antara muka Koleksi , anda diminta untuk menyenaraikan beberapa pelaksanaannya dan hubungannya dengan Peta . Baiklah, mari kita ketahui. Jadi, Pengumpulan dan Peta ialah dua hierarki berbeza untuk struktur data. Rupa hierarki Koleksi : Antara muka Koleksi ialah pautan teratas utama dengan senarai kaedah asas, dari mana tiga jenis asas struktur data berasal - Set , List , Queue . Set<T> ialah antara muka yang mewakili koleksi objek di mana setiap objek adalah unik. List<T> ialah antara muka yang mewakili urutan tertib objek yang dipanggil senarai. Queue<T> ialah antara muka yang bertanggungjawab untuk struktur yang disusun sebagai baris gilir (penyimpanan unsur berjujukan). Seperti yang dinyatakan sebelum ini, Map ialah hierarki yang berasingan: Map<K, V> ialah antara muka yang mewakili kamus di mana elemen terkandung sebagai pasangan nilai kunci. Selain itu, semua kekunci (K) adalah unik dalam objek Peta . Koleksi jenis ini memudahkan untuk mencari elemen jika kita mengetahui kunci - pengecam unik objek.

4. Apa yang anda tahu tentang Set?

Seperti yang dinyatakan sebelum ini, koleksi ini menampilkan banyak elemen unik. Dalam erti kata lain, objek yang sama tidak boleh muncul lebih daripada sekali dalam Set Java . Saya juga ingin menegaskan bahawa kita tidak boleh mengekstrak elemen daripada Set mengikut nombor (indeks) - hanya dengan kekerasan. Perkara penting ialah pelaksanaan Set yang berbeza mempunyai cara penstrukturan data yang berbeza. Kami akan mempertimbangkan pelaksanaan khusus selanjutnya. Jadi, pelaksanaan utama Set : HashSet ialah set yang berdasarkan jadual cincang, yang seterusnya membantu dengan carian. Menggunakan fungsi cincang yang meningkatkan prestasi semasa carian dan sisipan. Tanpa mengira bilangan elemen, secara umum, penyisipan dan carian (kadangkala pemadaman) dilakukan dalam hampir masa tetap - O(1). Kami akan melihat fungsi cincang dengan lebih terperinci sedikit kemudian. Saya juga ingin ambil perhatian bahawa HashSet mengandungi HashMap , di mana semua keajaiban berlaku. Berikut ialah artikel terperinci tentang HashSet dalam Java . LinkedHashSet - kelas ini memanjangkan HashSet tanpa menambah sebarang kaedah baharu. Seperti LinkedList , kelas ini mengekalkan senarai terpaut bagi unsur-unsur set dalam susunan ia dimasukkan. Ini membolehkan anda menyusun susunan yang diperlukan dalam pelaksanaan Set yang diberikan . Kelas TreeSet mencipta set yang berdasarkan pokok merah-hitam untuk menyusun struktur menyimpan elemen. Dalam erti kata lain, dalam set yang diberikan kita boleh mengisih elemen dalam tertib menaik. Jika kita menggunakan beberapa objek standard daripada "kotak", contohnya, Integer , maka kita tidak perlu melakukan apa-apa untuk menyusun set Integer dalam tertib menaik:

TreeSet set = new TreeSet<>();
set.add(4);
set.add(2);
set.add(3);
set.add(1);

System.out.println(set);

Dan dalam konsol kita akan mendapat output: Iaitu, dalam set ini nombor disimpan dalam bentuk disusun. Jika kita menggunakan elemen String dalam TreeSet , ia akan diisih, tetapi mengikut abjad. Nah, bagaimana jika kita mempunyai kelas standard (tersuai)? Bagaimanakah objek kelas ini akan menstrukturkan TreeSet ? Jika kita cuba memberikan objek sewenang-wenangnya kepada Set ini :

TreeSet set = new TreeSet<>();
set.add(new Cat(4, "Murzik"));
set.add(new Cat(2, "Barsik"));
set.add(new Cat(3, "Гарфилд"));

System.out.println(set);

Kami akan menerima ClassCastException kerana TreeSet tidak tahu cara mengisih objek jenis ini. Dalam kes ini, kami memerlukan objek tersuai kami untuk melaksanakan antara muka Sebanding dan kaedah compareTo :

public class Cat implements Comparable {
    int age;
    String name;

   public Cat(int age, String name) {
       this.age = age;
       this.name = name;
   }

   @Override
   public int compareTo(Cat cat) {
       return age > cat.age ? 1 : -1;
   }

   @Override
   public String toString() {
       return "Cat{" +
               "age=" + age +
               ", name='" + name + '\'' +
               '}';
   }
}

Seperti yang anda perhatikan, kaedah compareTo mengembalikan int :

• 1 jika objek semasa (ini) dianggap besar;
• -1 jika objek semasa dianggap lebih kecil daripada objek yang datang sebagai hujah;
• 0 jika objek adalah sama (kami tidak menggunakan ini dalam kes ini).

Dalam kes ini, TreeSet kami akan berfungsi dengan betul dan memaparkan hasilnya: Cara lain ialah membuat kelas pengisihan berasingan yang melaksanakan antara muka pembanding dan kaedah perbandingannya :

public class CatComparator implements Comparator {

   @Override
   public int compare(Cat o1, Cat o2) {
       return o1.age > o2.age ? 1 : -1;
   }
}

Dalam kes ini, untuk menggunakannya, kita mesti menetapkan objek kelas ini kepada pembina TreeSet :

TreeSet set = new TreeSet<>(new CatComparator());

Selepas ini, semua objek kelas Cat yang disertakan dalam TreeSet akan diisih menggunakan kelas Cat Comparator . Anda boleh mengetahui lebih lanjut tentang Comparator dan Comparable dalam Java daripada artikel ini .

5. Beritahu kami tentang Queue

Baris gilir ialah antara muka yang bertanggungjawab untuk struktur yang disusun sebagai baris gilir - struktur data yang menyimpan elemen secara berurutan. Sebagai contoh, dari barisan orang, orang pertama yang masuk adalah orang yang tiba lebih awal daripada yang lain, dan yang terakhir adalah orang yang tiba lebih awal daripada orang lain. Kaedah ini dipanggil FIFO , iaitu First in First Out . Kaedah Gilir Unik menumpukan pada bekerja dengan elemen pertama atau terakhir, contohnya:

• tambah dan tawarkan - memasukkan elemen pada penghujung baris gilir,
• keluarkan - mengambil dan mengalih keluar pengepala baris gilir ini,
• mengintip - Mendapat semula tetapi tidak mengalih keluar pengepala baris gilir.

BAHAGIAN 2