✋🏽 😨 ⚗️ Yang Perlu Anda Ketahui Tentang Koleksi Berbasis Hash 🤸🏻 🖇️ 🔅

Halo semuanya. Dalam sentuhan Vladislav Rodin. Saat ini, saya adalah kepala kursus Arsitek Beban Tinggi di OTUS, dan saya juga mengajar kursus arsitektur perangkat lunak.

Selain mengajar, seperti yang Anda lihat, saya juga menulis materi hak cipta untuk blog OTUS di Habré dan saya ingin mencurahkan artikel hari ini untuk meluncurkan aliran baru kursus "Algoritma untuk Pengembang" .

pengantar

Tabel hash (HashMap) bersama dengan array dinamis adalah struktur data paling populer yang digunakan dalam produksi. Sangat sering Anda dapat mendengar pertanyaan di wawancara mengenai tujuan mereka, fitur struktur internal mereka, serta algoritma terkait. Struktur data ini klasik dan ditemukan tidak hanya di Jawa, tetapi juga di banyak bahasa pemrograman lainnya.

Perumusan masalah

Mari tetapkan tujuan untuk membuat struktur data yang memungkinkan Anda untuk:

mengandung (Elemen elemen) memeriksa apakah suatu elemen di dalamnya atau tidak, untuk O (1)
add (Elemen elemen) tambahkan elemen di O (1)
delete (Elemen elemen) hapus elemen di O (1)

Himpunan

Mari kita coba melakukan operasi ini di atas array, yang merupakan struktur data paling sederhana. Kami setuju bahwa kami akan menganggap sel kosong jika mengandung nol.

Cek ketersediaan

Hal ini diperlukan untuk melakukan pencarian linier melalui array, karena elemen tersebut dapat berpotensi berada dalam sel apa pun. Asimptotik, ini bisa dilakukan dalam O (n), di mana n adalah ukuran array.

Menambahkan

Jika kita perlu menambahkan elemen di mana saja, maka pertama-tama kita perlu menemukan sel kosong, dan kemudian menulis elemen ke dalamnya. Dengan demikian, kami kembali melakukan pencarian linier dan mendapatkan perilaku asimptotik O (n).

Menghapus

Untuk menghapus suatu elemen, Anda harus menemukannya terlebih dahulu, dan kemudian menulis nol ke sel yang ditemukan. Sekali lagi pencarian linear membawa kita ke O (n).

Kumpulan hash paling sederhana

Harap perhatikan bahwa dengan setiap operasi, kami pertama-tama mencari indeks sel yang diinginkan, dan kemudian melakukan operasi, dan itu adalah pencarian yang merusak asimptotik bagi kami! Jika kami belajar untuk mendapatkan indeks ini untuk O (1), maka masalah asli akan terpecahkan.

Sekarang mari kita ganti pencarian linier dengan algoritma berikut: kita akan menghitung nilai fungsi tertentu - fungsi hash yang memetakan objek kelas ke integer. Setelah itu, kita akan membandingkan bilangan bulat yang dihasilkan dengan indeks sel array (ini cukup mudah dilakukan, misalnya, mengambil sisa pembagian angka ini dengan ukuran array). Jika fungsi hash ditulis sedemikian rupa sehingga dianggap sebagai O (1) (dan biasanya ditulis seperti ini), maka kita mendapatkan implementasi hash set yang paling sederhana.. Sel array dalam hal set hash dapat disebut ember .

Masalah implementasi implementasi hash yang paling sederhana

Tidak peduli bagaimana fungsi hash ditulis, jumlah sel dalam array selalu terbatas, sedangkan himpunan elemen yang ingin kita simpan dalam struktur data tidak terbatas. Lagi pula, kita tidak akan repot dengan struktur data jika ada kebutuhan untuk menyimpan hanya sepuluh elemen yang diketahui sebelumnya, kan? Keadaan ini menyebabkan konflik yang tak terhindarkan . Tabrakan adalah situasi ketika, ketika menambahkan objek yang berbeda, kita jatuh ke sel yang sama dalam array.

Dua metode ditemukan untuk menyelesaikan tabrakan: metode chaining dan metode pengalamatan terbuka .

Metode rantai

Metode rantai adalah metode paling sederhana untuk menyelesaikan tabrakan. Di dalam sel array kita tidak akan menyimpan elemen-elemen, tetapi daftar yang terhubung dari elemen-elemen ini. Karena menambahkan ke bagian atas daftar (dan tidak masalah bagian mana dari daftar untuk menambahkan elemen) memiliki perilaku asimptotik O (1), kami tidak akan merusak perilaku asimptotik umum, dan itu akan tetap sama dengan O (1).

Implementasi ini memiliki masalah: jika daftar tumbuh sangat banyak (sebagai upaya terakhir, kita dapat mempertimbangkan fungsi hash yang mengembalikan konstanta untuk objek apa pun), maka kita mendapatkan asimptotik O (m), di mana m adalah jumlah elemen dalam set, jika ukuran array sudah diperbaiki. Untuk menghindari masalah seperti itu, konsep siklus tugas diperkenalkan.(itu bisa sama, misalnya, 1.5). Jika ketika menambahkan elemen ternyata fraksi dari jumlah elemen yang ada dalam struktur data relatif terhadap ukuran array melebihi faktor isi, maka terjadi hal berikut: array baru dipilih yang ukurannya melebihi ukuran array lama (misalnya, 2 kali), dan struktur data dibangun kembali pada array baru.

Metode penyelesaian tabrakan ini digunakan di Jawa, dan struktur data disebut HashSet .

Metode pengalamatan terbuka

Dalam metode ini, sel itu sendiri disimpan dalam sel, dan jika terjadi tabrakan, urutan sampel terjadi , yaitu, kita mulai memilah-milah sel menggunakan beberapa algoritma dengan harapan menemukan yang gratis. Ini dapat dilakukan dengan algoritma yang berbeda ( urutan linear / kuadrat sampel , hashing ganda ), yang masing-masing memiliki masalah sendiri (misalnya, munculnya cluster primer atau sekunder ).

Dari hash yang diatur ke tabel hash (HashMap)

Mari kita membuat struktur data yang memungkinkan Anda untuk menambah, menghapus, mencari item, tetapi dengan beberapa kunci, secepat hash set (yaitu, di luar O (1)).

Kami akan menggunakan struktur data yang sama dengan hash set, tetapi kami tidak akan menyimpan elemen, tetapi pasangan elemen.

Jadi, penyisipan (put (kunci kunci, Nilai nilai)) akan dilakukan sebagai berikut: kita akan menghitung sel array dengan objek tipe Key, kita akan mendapatkan jumlah ember. Mari kita lihat daftar dalam ember, membandingkan kunci dengan kunci dalam pasangan yang disimpan. Jika Anda menemukan kunci yang sama - cukup tekan nilai lama, jika Anda tidak menemukannya - tambahkan pasangan.

Bagaimana barang diterima dengan kunci? Ya, sesuai dengan prinsip yang sama: kami mendapatkan ember dengan kunci, melalui pasangan dan mengembalikan nilai dalam pasangan, kunci yang sama dengan kunci dalam permintaan, jika ada pasangan seperti itu, dan nol jika tidak.

Struktur data ini disebut tabel hash .

Pertanyaan wawancara tipikal

T: Bagaimana pengaturan HashSet dan HashMap? Bagaimana operasi utama dilakukan dalam koleksi ini? Bagaimana metode equals () dan hashCode () diterapkan?
A : Jawaban untuk pertanyaan-pertanyaan ini dapat ditemukan di atas.

T: Apa kontrak untuk equals () dan kode hash ()? Apa itu karena?
A : Jika objek sama, maka mereka harus memiliki kode hash sama. Dengan demikian, kode hash harus ditentukan oleh kemampuan bidang yang terlibat dalam persamaan. Pelanggaran kontrak ini dapat menyebabkan efek yang sangat menarik. Jika objek sama, tetapi kode hash mereka berbeda, maka Anda mungkin tidak mendapatkan nilai yang sesuai dengan kunci yang Anda tambahkan objek ke HashSet atau ke HashMap.

Kesimpulan

Pada wawancara, mereka suka bertanya berbagai kasus terkait dengan struktur data ini. Selain itu, keputusan salah satu dari mereka dapat disimpulkan dari memahami prinsip-prinsip pekerjaan mereka tanpa "menjejalkan".

Itu saja. Jika Anda telah membaca materi sampai akhir, saya mengundang kolega saya Evgeny Volosatov untuk menunjukkan kepada Anda bagaimana memecahkan masalah olimpiade menggunakan gagasan pemrograman dinamis untuk pelajaran gratis tentang topik "Rahasia Pemrograman Dinamis" .

Yang Perlu Anda Ketahui Tentang Koleksi Berbasis Hash