Hashing

Hashing sangat cekap. Ia mengambil masa O(1) untuk mencari, memasukkan dan memadam elemen menggunakan pencincangan. Satu elemen boleh ditemui dalam masa O(log n) dalam pepohon carian yang seimbang. Adakah terdapat cara yang lebih cekap untuk mencari elemen dalam bekas? Bab ini memperkenalkan teknik yang dipanggil pencincangan. Anda boleh menggunakan pencincangan untuk melaksanakan peta atau set untuk mencari, memasukkan dan memadamkan elemen dalam masa O(1).

Apa Itu Hashing?

Hashing menggunakan fungsi hashing untuk memetakan kunci kepada indeks. Sebelum memperkenalkan pencincangan, mari kita semak peta, iaitu struktur data yang dilaksanakan menggunakan pencincangan. Ingat bahawa peta (diperkenalkan dalam Bahagian) ialah objek bekas yang menyimpan entri. Setiap entri mengandungi dua bahagian: kunci dan nilai. Kunci, juga dipanggil kunci carian, digunakan untuk mencari nilai yang sepadan. Contohnya, kamus boleh disimpan dalam peta, di mana perkataan adalah kunci dan takrif perkataan adalah nilai.

Peta juga dipanggil kamus, jadual cincang atau tatasusunan bersekutu.

Rangka Kerja Koleksi Java mentakrifkan antara muka java.util.Map untuk pemodelan peta. Tiga pelaksanaan konkrit ialah java.util.HashMap, java.util.LinkedHashMap dan java.util.TreeMap. java.util.HashMap dilaksanakan menggunakan pencincangan, java.util.LinkedHashMap menggunakan LinkedList dan java.util.TreeMap menggunakan merah -pokok hitam.

Jika anda mengetahui indeks elemen dalam tatasusunan, anda boleh mendapatkan semula elemen menggunakan indeks dalam masa O(1). Jadi adakah ini bermakna kita boleh menyimpan nilai dalam tatasusunan dan menggunakan kunci sebagai indeks untuk mencari nilai? Jawapannya ya—jika anda boleh memetakan kunci kepada indeks. Tatasusunan yang menyimpan nilai dipanggil jadual cincang. Fungsi yang memetakan kunci kepada indeks dalam jadual cincang dipanggil fungsi cincang. Seperti yang ditunjukkan dalam Rajah di bawah, fungsi cincang memperoleh indeks daripada kunci dan menggunakan indeks untuk mendapatkan semula nilai bagi kunci. Hashing ialah teknik yang mendapatkan semula nilai menggunakan indeks yang diperoleh daripada kekunci tanpa melakukan carian.

Bagaimana anda mereka bentuk fungsi cincang yang menghasilkan indeks daripada kunci? Sebaik-baiknya, kami ingin mereka bentuk fungsi yang memetakan setiap kunci carian ke indeks yang berbeza dalam jadual cincang. Fungsi sedemikian dipanggil fungsi cincang sempurna. Walau bagaimanapun, sukar untuk mencari fungsi cincang yang sempurna. Apabila dua atau lebih kekunci dipetakan kepada nilai cincang yang sama, kami mengatakan bahawa perlanggaran telah berlaku. Walaupun terdapat cara untuk menangani perlanggaran, yang dibincangkan kemudian dalam bab ini, adalah lebih baik untuk mengelakkan perlanggaran di tempat pertama. Oleh itu, anda harus mereka bentuk fungsi cincang yang cepat dan mudah dikira yang meminimumkan perlanggaran.

Atas ialah kandungan terperinci Hashing. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!