Apa yang mungkin mereka tanyakan saat wawancara: Struktur data di Java. Bagian 2

BAGIAN 1 Sekarang kita berbicara tentang dasar yang harus diketahui oleh setiap pengembang Java. Tentang pengetahuan klasik dari mana semuanya dimulai. Hari ini saya ingin menyentuh salah satu topik mendasar dari setiap wawancara - struktur data di Java . Jadi, daripada bertele-tele, mari kita mulai. Simak kelanjutan daftar pertanyaan yang mungkin ditanyakan kepada Anda tentang topik ini selama wawancara.

6. Beritahu kami tentang Daftar

Daftar adalah antarmuka yang mewakili struktur objek yang terurut, yang disebut daftar. “Trik” dari struktur ini adalah elemen-elemen yang terdapat dalam List dapat disisipkan, diubah atau dihapus berdasarkan indeks, yaitu pengenal internal List . Dengan kata lain, indeks berarti: “berapa banyak elemen dari awal daftar”. Elemen List pertama memiliki indeks 0, elemen kedua memiliki indeks 1, dan seterusnya. Jadi elemen kelima berjarak empat elemen dari awal daftar. Seperti disebutkan di atas, urutan penambahan item ke daftar itu penting. Itu sebabnya struktur datanya disebut list . Kami mencantumkan metode unik untuk struktur ini yang ditujukan untuk bekerja dengan elemen berdasarkan indeks:

• dapatkan - mengembalikan elemen pada posisi yang ditentukan (berdasarkan nilai indeks),
• hapus - menghapus elemen pada posisi yang ditentukan,
• set - mengganti elemen pada posisi tertentu dengan elemen yang ditentukan dalam metode.

Implementasi utamanya adalah ArrayList dan LinkedList . Kami akan membicarakannya lebih banyak nanti. Vektor adalah daftar yang aman untuk thread, sehingga setiap metode di kelas ini disinkronkan. Namun perlu diingat bahwa jika Anda ingin mengamankan beberapa tindakan daftar, Anda akan menyinkronkan seluruh rangkaian operasi. Dan sinkronisasi operasi individual menjadi kurang aman dan jauh lebih lambat. Tentu saja, Vector juga memiliki overhead penguncian, meskipun Anda tidak memerlukan kunci tersebut. Oleh karena itu, kelas ini sekarang dianggap usang dan tidak digunakan. Omong-omong: ArrayList mirip dengan Vector , tetapi tidak menggunakan penguncian, sehingga digunakan di mana saja. Stack adalah subkelas dari kelas Vector dengan satu konstruktor default dan semua metode kelas Vector , ditambah beberapa metodenya sendiri (kita akan membicarakannya nanti). Sebagai contoh, Anda dapat membayangkan prosesnya sebagai tumpukan folder berisi dokumen. Anda menempatkan satu folder di bagian atas tumpukan, dan Anda hanya dapat mengambil folder tersebut dalam urutan terbalik, dimulai dari atas. Sebenarnya ini mekanisme tipe LIFO yaitu Last In First Out , yang terakhir datang adalah yang pertama keluar. Tumpukan mengimplementasikan metodenya sendiri:

• push - menambahkan elemen yang diteruskan ke bagian atas tumpukan;
• mengintip - mengembalikan elemen yang ada di bagian atas tumpukan;
• pop - juga mengembalikan elemen yang berada di bagian atas tumpukan, tetapi menghapusnya;
• kosong - memeriksa apakah tumpukan kosong - benar atau tidak - salah ;
• pencarian - mencari tumpukan untuk elemen tertentu. Jika suatu elemen ditemukan, nomor urutnya relatif terhadap bagian atas tumpukan dikembalikan. Jika elemen tidak ditemukan, nilai -1 dikembalikan.

Saat ini, subkelas Stack sebenarnya tidak digunakan karena kesederhanaan dan ketidakfleksibelannya, namun, Anda mungkin menemukannya. Misalnya, ketika Anda menerima beberapa kesalahan dan di konsol Anda melihat setumpuk pesan tentang hal itu. Anda dapat membaca lebih lanjut tentang tumpukan dan antrian di artikel ini .

7. Beritahu kami tentang Peta

Sebagaimana dinyatakan di atas, Peta adalah kumpulan yang memiliki struktur antarmuka terpisah dan implementasinya. Terpisah karena di sini nilai-nilai tidak disimpan satu per satu, tetapi dalam pasangan “nilai-kunci”. Metode Peta Dasar :

• put(K kunci, nilai V) - menambahkan elemen ke Peta;
• dapatkan(Kunci objek) - mencari nilai berdasarkan kunci;
• berisiKey(Kunci objek) — memeriksa Peta untuk mengetahui keberadaan kunci ini;
• berisiNilai(Nilai objek) - memeriksa Peta untuk mengetahui keberadaan nilai ini;
• hapus(Kunci objek) - menghapus nilai dengan kuncinya.

Seperti yang Anda lihat, sebagian besar operasi dilakukan dengan menggunakan kunci. Sebagai aturan, objek yang tidak dapat diubah dipilih sebagai kunci . Contoh khas dari objek ini adalah String . Implementasi Peta Dasar :

1. HashMap - dirancang untuk menyimpan nilai dalam urutan acak, tetapi memungkinkan Anda mencari elemen peta dengan cepat. Memungkinkan Anda menentukan kunci menggunakan kata kunci null , tetapi tidak lebih dari sekali, karena pasangan dengan kunci yang sama ditulis di atas satu sama lain. Syarat utamanya adalah keunikan kunci: nilainya dapat diulang (mungkin ada beberapa nilai nol).
2. LinkedHashMap adalah analog dari HashMap yang menyimpan nilai sesuai urutan penambahannya. Oleh karena itu, seperti LinkedList , ia memiliki header - kepala dari daftar tertaut ganda. Saat diinisialisasi, ia menunjuk ke dirinya sendiri.

   LinkedHashMap juga memiliki accessOrder yang menentukan bagaimana elemen akan diakses ketika iterator digunakan. Jika accessOrder salah, akses akan dilakukan sesuai urutan penyisipan elemen. Jika benar, elemen akan berada dalam urutan yang terakhir diakses (elemen yang terakhir diakses akan ditempatkan di akhir).

3. TreeMap adalah Peta yang mengurutkan elemen berdasarkan nilai kunci. Mirip dengan TreeSet , tetapi berpasangan berdasarkan nilai kunci. Untuk menetapkan aturan pengurutan TreeMap , kunci harus mengimplementasikan antarmuka Comparable . Jika tidak, harus ada Pembanding Berorientasi Kunci (yang ditentukan dalam konstruktor TreeMap ), TreeSet - diimplementasikan dengan objek TreeMap di dalamnya, di mana, pada kenyataannya, semua keajaiban terjadi.

   Anda dapat membaca selengkapnya tentang pengurutan di TreeMap menggunakan pohon merah-hitam di artikel tentang fitur TreeMap .

4. Hashtable mirip dengan HashMap , tetapi tidak mengizinkan null disimpan baik sebagai kunci atau nilai. Ini disinkronkan dengan hati-hati dari sudut pandang multi-threading, yang berarti aman dari sudut pandang multi-threading. Namun implementasi ini sudah ketinggalan jaman dan lambat, jadi sekarang Anda tidak akan melihat Hashtable di proyek-proyek baru.

8. Daftar Array vs Daftar Tertaut. Mana yang lebih baik untuk digunakan?

Pertanyaan ini mungkin yang paling populer dalam struktur data dan disertai beberapa kendala. Sebelum menjawabnya, mari pelajari lebih lanjut tentang struktur data ini. ArrayList mengimplementasikan antarmuka Daftar dan beroperasi pada array internal yang diperluas sesuai kebutuhan. Ketika array internal terisi penuh, dan elemen baru perlu dimasukkan, array baru dibuat dengan ukuran (oldSize * 1.5) +1. Setelah ini, semua data dari array lama disalin ke elemen baru + baru, dan elemen lama akan dihapus oleh pengumpul sampah . Metode add menambahkan elemen ke sel kosong terakhir dari array. Artinya, jika kita sudah memiliki 3 elemen di sana, elemen berikutnya akan ditambahkan ke sel ke-4. Mari kita lihat kinerja metode dasar:

• get(int indeks) - mengambil elemen dalam array berdasarkan indeks adalah yang tercepat di O(1) ;
• add(Object obj) - jika ada cukup ruang di array internal untuk elemen baru, maka dengan penyisipan normal O(1) waktu akan dihabiskan , karena penambahan ditargetkan ke sel terakhir.

  Jika kita perlu membuat array baru dan menyalin isinya ke dalamnya, maka waktu kita akan berbanding lurus dengan jumlah elemen dalam array O(n) ;

• hapus(int indeks) - saat menghapus sebuah elemen, misalnya, dari tengah, kita akan mendapatkan waktu O(n/2), karena kita perlu memindahkan elemen di sebelah kanannya satu sel ke belakang. Oleh karena itu, jika menghapus dari awal daftar, maka O(n), dari akhir - O(1);
• add(int index, Object obj) - situasi yang mirip dengan menghapus: saat menambahkan ke tengah, kita perlu memindahkan elemen di sebelah kanan satu sel ke depan, sehingga waktunya adalah O(n/2). Tentu saja, dari awal - O(n), dari akhir - O(1);
• set(int indeks, Objek objek) - di sini situasinya berbeda, karena Anda hanya perlu mencari elemen yang diinginkan dan menuliskannya tanpa memindahkan sisanya, jadi O(1).

Baca selengkapnya tentang ArrayList di artikel ini . LinkedList mengimplementasikan dua antarmuka sekaligus - List dan Queue , dan oleh karena itu memiliki properti dan metode yang melekat pada kedua struktur data. Dari Daftar ia mengambil akses ke elemen berdasarkan indeks, dari Antrian - keberadaan "kepala" dan "ekor". Secara internal, ini diimplementasikan sebagai struktur data yang mewakili daftar tertaut ganda. Artinya, setiap elemen memiliki link ke elemen berikutnya dan sebelumnya, kecuali “ekor” dan “kepala”.

• get(int indeks) - saat mencari elemen yang berada di tengah daftar, ia mulai mencari semua elemen secara berurutan hingga elemen yang diinginkan ditemukan. Logikanya, pencarian harus memakan waktu O(n/2) , tetapi LinkedList juga memiliki ekor, sehingga pencarian dilakukan secara bersamaan dari kedua sisi. Oleh karena itu, waktu dikurangi menjadi O(n/4) .

  Jika elemen dekat dengan awal atau akhir daftar, maka waktunya adalah O(1) ;

• add(Object obj) - saat menambahkan elemen baru, elemen "ekor" akan memiliki tautan ke elemen berikutnya yang ditambahkan, dan elemen baru akan menerima tautan ke elemen sebelumnya dan menjadi "ekor" baru. Oleh karena itu, waktunya adalah O(1) ;
• hapus(int indeks) - logika yang mirip dengan metode get(int indeks) . Untuk menghapus elemen dari tengah daftar, Anda harus menemukannya terlebih dahulu. Ini lagi-lagi O(n/4) , sedangkan penghapusan itu sendiri sebenarnya tidak memerlukan apa-apa, karena hanya mengubah penunjuk objek yang berdekatan (mereka mulai merujuk satu sama lain). Jika elemen berada di awal atau di akhir, maka lagi - O(1) ;
• add(int index, Object obj) dan set(int index, Object obj) - metode ini akan memiliki kompleksitas waktu yang identik dengan get(int index) , karena sebagian besar waktu dihabiskan untuk mencari elemen. Oleh karena itu, untuk bagian tengah daftar - O(n/4) , untuk awal - O(1).

Informasi lebih lanjut tentang bekerja dengan LinkedList dijelaskan dalam artikel ini . Mari kita lihat semua ini dalam sebuah tabel: Seperti yang mungkin sudah Anda pahami, tidak mungkin menjawab pertanyaan ini dengan jelas. Memang, dalam situasi berbeda mereka bekerja dengan kecepatan berbeda. Oleh karena itu, ketika Anda ditanya pertanyaan seperti ini, Anda harus segera menanyakan apa yang akan menjadi fokus daftar ini dan operasi apa yang paling sering dilakukan. Berangkat dari hal tersebut, berikanlah jawabannya, namun disertai penjelasan mengapa demikian. Mari kita rangkum perbandingan kita: ArrayList:

• pilihan terbaik jika operasi yang paling sering dilakukan adalah mencari elemen, menimpa elemen;
• pilihan terburuk jika operasi penyisipan dan penghapusan di awal-tengah, karena operasi pergeseran elemen di sebelah kanan akan berlangsung.

Daftar Tertaut:

• pilihan terbaik jika operasi yang sering kita lakukan adalah penyisipan dan penghapusan di awal-tengah;
• pilihan terburuk jika operasi yang paling umum adalah pencarian.

9. Bagaimana elemen disimpan dalam HashMap?

Koleksi HashMap berisi array internal Node[] table , yang selnya juga disebut buckets . Node berisi:

• kunci - tautan ke kunci,
• nilai — referensi ke nilai,
• hash - nilai hash,
• selanjutnya - tautan ke Node berikutnya .

Satu sel dari array table[] mungkin berisi referensi ke objek Node dengan tautan ke elemen Node berikutnya , dan mungkin memiliki tautan ke elemen lain, dan seterusnya... Hasilnya, elemen Node ini dapat membentuk a daftar tertaut tunggal , dengan elemen dengan tautan ke yang berikutnya. Dalam hal ini, nilai hash dari elemen rantai yang sama adalah sama. Setelah penyimpangan singkat, mari kita lihat bagaimana elemen disimpan dalam HashMap :

1. Kuncinya diperiksa null . Jika null , maka kunci akan disimpan di sel table[0] karena kode hash untuk null selalu 0.
2. Jika kuncinya bukan null , maka metode hashcode() objek kunci tersebut dipanggil , yang akan mengembalikan kode hashnya. Kode hash ini digunakan untuk menentukan sel array dimana objek Node akan disimpan.
3. Selanjutnya, kode hash ini ditempatkan dalam metode hash() internal , yang menghitung kode hash, tetapi dalam ukuran array table[] .
4. Selanjutnya, bergantung pada nilai hash, Node ditempatkan di sel tertentu dalam array table[] .
5. Jika sel table[] yang digunakan untuk menyimpan elemen Node saat ini tidak kosong, namun sudah memiliki beberapa elemen, maka elemen Node akan diiterasi pada nilai berikutnya hingga elemen terakhir tercapai. Artinya, bidang berikutnya adalah null .

   Selama pencarian ini, kunci dari objek Node yang dilindungi dibandingkan dengan kunci dari objek yang sedang dicari:

   • jika ditemukan kecocokan, pencarian akan berakhir, dan Node baru akan menimpa Node di mana kecocokan ditemukan (hanya bidang nilainya yang akan ditimpa );
   • jika tidak ada kunci yang cocok ditemukan, maka Node baru akan menjadi yang terakhir dalam daftar ini, dan Node sebelumnya akan memiliki tautan berikutnya ke sana.

Pertanyaan yang sering muncul saat wawancara: apa itu konflik ? Situasi ketika sel array table[] tidak menyimpan satu elemen, tetapi rantai dua atau lebih, disebut tabrakan . Dalam kasus normal di mana hanya satu elemen disimpan dalam satu sel table[] , mengakses elemen HashMap memiliki kompleksitas waktu O(1) yang konstan . Tetapi bila sel dengan elemen yang diinginkan berisi rantai elemen ( tabrakan ), maka O(n) , karena dalam hal ini waktu berbanding lurus dengan jumlah elemen yang diurutkan.

10. Jelaskan iteratornya

Dalam diagram pemetaan hierarki Koleksi di atas, antarmuka Koleksi adalah tempat seluruh hierarki dimulai, namun dalam praktiknya tidak seperti itu. Koleksi mewarisi dari antarmuka dengan metode iterator() , yang mengembalikan objek yang mengimplementasikan antarmuka Iterator<E> . Antarmuka Iterator terlihat seperti ini:

public interface Iterator <E>{

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

next() - dengan memanggil metode ini, Anda bisa mendapatkan elemen berikutnya. hasNext() - memungkinkan Anda mengetahui apakah ada elemen berikutnya, dan apakah akhir koleksi telah tercapai. Dan bila masih ada elemen, hasNext() akan mengembalikan true . Biasanya, hasNext() dipanggil sebelum metode next() , karena next() akan memunculkan NoSuchElementException ketika mencapai akhir koleksi . hapus() - Menghapus elemen yang diambil oleh panggilan terakhir ke next() . Tujuan Iterator adalah untuk mengulangi elemen. Misalnya:

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, perulangan for-each diimplementasikan menggunakan iterator. Anda dapat membaca lebih lanjut tentang ini di sini . List menyediakan versi iteratornya sendiri, tetapi versi yang lebih keren dan lebih canggih - ListIterator . Antarmuka ini memperluas Iterator dan memiliki metode tambahan:

• hasPvious akan mengembalikan nilai true jika ada elemen sebelumnya dalam koleksi, false jika tidak;
• sebelumnya mengembalikan elemen saat ini dan berpindah ke elemen sebelumnya; jika tidak ada, maka NoSuchElementException akan dilempar;
• add akan menyisipkan objek yang diteruskan sebelum elemen dikembalikan pada panggilan berikutnya ke next() ;
• set menugaskan elemen saat ini sebagai referensi ke objek yang diteruskan;
• nextIndex mengembalikan indeks elemen berikutnya. Jika tidak ada hal seperti itu, maka ukuran daftar dikembalikan;
• previousIndex mengembalikan indeks elemen sebelumnya. Jika tidak ada, maka angka -1 dikembalikan.

Baiklah, itu saja untukku hari ini. Saya harap setelah membaca artikel ini Anda semakin dekat dengan impian Anda - menjadi seorang pengembang.