Apa itu Hashing? Bagaimana Kod Hash berfungsi - dengan Contoh

Pengenalan hashing

Hashing dirancang untuk menyelesaikan masalah keperluan mencari atau menyimpan barang dalam koleksi dengan cekap.

Sebagai contoh, jika kita mempunyai senarai 10,000 perkataan bahasa Inggeris dan kita ingin memeriksa sama ada perkataan yang ada dalam senarai, tidak berkesan membandingkan perkataan tersebut dengan 10.000 item berturut-turut sehingga kita menemui padanan. Walaupun senarai kata disusun secara leksikografis, seperti dalam kamus, anda masih memerlukan sedikit masa untuk mencari perkataan yang anda cari.

Hashing adalah teknik untuk menjadikan sesuatu menjadi lebih cekap dengan mempersempit carian secara efektif pada awalnya.

Apa itu hashing?

Hashing bermaksud menggunakan beberapa fungsi atau algoritma untuk memetakan data objek ke beberapa nilai integer yang mewakili.

Kod hash yang disebut (atau hanya hash) ini kemudian dapat digunakan sebagai cara untuk mempersempit pencarian kami ketika mencari item di peta.

Secara amnya, kod hash ini digunakan untuk menghasilkan indeks, di mana nilainya disimpan.

Bagaimana hashing berfungsi

Dalam jadual hash, anda menyimpan data dalam bentuk pasangan kunci dan nilai. Kunci, yang digunakan untuk mengenal pasti data, diberikan sebagai input untuk fungsi hashing. Kod hash, yang merupakan bilangan bulat, kemudian dipetakan ke ukuran tetap yang kita ada.

Jadual Hash mesti menyokong 3 fungsi.

  • masukkan (kunci, nilai)
  • dapatkan (kunci)
  • padam (kunci)

Murni sebagai contoh untuk membantu kita memahami konsep, mari kita anggap bahawa kita ingin memetakan senarai kunci rentetan kepada nilai rentetan (misalnya, memetakan senarai negara ke ibu kota mereka).

Oleh itu, katakan kita mahu menyimpan data dalam Jadual dalam peta.

Dan mari kita anggap bahawa fungsi hash kita hanya mengambil panjang tali.

Untuk kesederhanaan, kami akan mempunyai dua tatasusunan: satu untuk kunci kami dan satu untuk nilai.

Oleh itu, untuk memasukkan item ke dalam jadual hash, kami menghitung kod hashnya (dalam kes ini, hanya menghitung jumlah aksara), kemudian masukkan kunci dan nilai dalam tatasusunan pada indeks yang sesuai.

Sebagai contoh, Cuba mempunyai kod hash (panjang) 4. Oleh itu, kami menyimpan Cuba di kedudukan ke-4 dalam susunan kunci, dan Havana dalam indeks ke-4 dari array nilai dll. Dan kami berakhir dengan yang berikut:

Sekarang, dalam contoh khusus ini semuanya berjalan lancar. Susunan kami harus cukup besar untuk menampung tali terpanjang, tetapi dalam kes ini hanya 11 slot.

Kami membuang sedikit ruang kerana, misalnya, tidak ada kunci 1 huruf dalam data kami, atau kunci antara 8 dan 10 huruf.

Tetapi dalam kes ini, ruang yang terbuang juga tidak begitu buruk. Mengambil panjang tali itu bagus dan cepat, begitu juga proses mencari nilai yang berkaitan dengan kunci yang diberikan (tentu lebih cepat daripada melakukan hingga lima perbandingan rentetan).

Tetapi, apa yang kita lakukan sekiranya set data kita mempunyai rentetan yang mempunyai lebih dari 11 aksara?

Bagaimana jika kita mempunyai satu kata lain dengan 5 aksara, "India", dan cuba memberikannya ke indeks menggunakan fungsi hash kami. Oleh kerana indeks 5 sudah terpakai, kita harus membuat panggilan mengenai apa yang harus dilakukan dengannya. Ini dipanggil perlanggaran.

Sekiranya set data kami mempunyai rentetan dengan seribu aksara, dan anda membuat susunan seribu indeks untuk menyimpan data, itu akan mengakibatkan pembaziran ruang. Sekiranya kunci kami adalah kata-kata rawak dari bahasa Inggeris, di mana terdapat begitu banyak perkataan dengan panjang yang sama, penggunaan panjang sebagai fungsi hashing tidak akan berguna.

Pengendalian Perlanggaran

Dua kaedah asas digunakan untuk menangani perlanggaran.

  1. Rantai Berasingan
  2. Buka Alamat

Rantai Berasingan

Pengendalian perlanggaran Hash dengan rantai berasingan, menggunakan struktur data tambahan, senarai yang lebih disukai untuk peruntukan dinamik, ke dalam keranjang. Dalam contoh kami, apabila kami menambahkan India ke set data, ia ditambahkan ke senarai terpaut yang disimpan di indeks 5, maka jadual kami akan kelihatan seperti ini.

Untuk mencari item, pertama-tama kita pergi ke baldi dan kemudian membandingkan kunci. Ini adalah kaedah yang popular, dan jika senarai pautan digunakan, hash tidak akan terisi. Kos untuk get(k)rata-rata O(n)di mana n adalah bilangan kunci dalam baldi, jumlah kunci menjadi N.

Masalah dengan rantai berasingan adalah bahawa struktur data dapat berkembang tanpa batas.

Buka Alamat

Pengalamatan terbuka tidak memperkenalkan struktur data baru. Sekiranya perlanggaran berlaku maka kita mencari ketersediaan di tempat seterusnya yang dihasilkan oleh algoritma. Open address biasanya digunakan di mana ruang penyimpanan adalah terhad, iaitu pemproses tertanam. Pidato terbuka tidak semestinya lebih cepat daripada rantai yang terpisah.

Kaedah untuk Pengalamatan Terbuka

  • [Pemeriksaan Linear
  • Pemeriksaan Kuadratik
  • Double Hashing

Cara menggunakan hashing dalam kod anda.

Python

 # Few languages like Python, Ruby come with an in-built hashing support. # Declaration my_hash_table = {} my_hash_table = dict() # Insertion my_hash_table[key] = value # Look up value = my_hash_table.get(key) # returns None if the key is not present || Deferred in python 3, available in python 2 value = my_hash_table[key] # throws a ValueError exception if the key is not present # Deletion del my_hash_table[key] # throws a ValueError exception if the key is not present # Getting all keys and values stored in the dictionary keys = my_hash_table.keys() values = my_hash_table.values()
:roket:

Jalankan Kod

Jawa

 // Java doesn't include hashing by default, you have to import it from java.util library // Importing hashmaps import java.util.HashMap; // Declaration HashMap myHashTable = new HashMap(); // declares an empty map. // Insertion myHashTable.put(key, value); // Deletion myHashtable.remove(key); // Look up myHashTable.get(key); // returns null if the key K is not present myHashTable.containsKey(key); // returns a boolean value, indicating the presence of a key // Number of key, value pairs in the hash table myHashTable.size();
:roket:

Jalankan Kod

Maklumat lanjut mengenai hashing

  • Panduan tanpa kod untuk jadual hash dan hash
  • Cara melaksanakan jadual hash sederhana dalam JavaScript
  • Jadual Hash menerangkan