Jadual Hash dalam Struktur Data: Contoh Python

Isi kandungan:

Anonim

Apa itu Hashing?

Hash adalah nilai yang mempunyai panjang tetap, dan dihasilkan dengan menggunakan formula matematik. Nilai Hash digunakan dalam pemampatan data, kriptologi, dll. Dalam pengindeksan data, nilai hash digunakan kerana mempunyai ukuran panjang tetap tanpa mengira nilai yang digunakan untuk menghasilkannya. Ia menjadikan nilai hash untuk menempati ruang minimum berbanding dengan nilai lain yang berbeza panjangnya.

Fungsi hash menggunakan algoritma matematik untuk menukar kunci menjadi hash. Perlanggaran berlaku apabila fungsi hash menghasilkan nilai hash yang sama untuk lebih daripada satu kekunci.

Dalam tutorial Algoritma ini, anda akan belajar:

  • Apa itu Hashing?
  • Apakah Jadual Hash?
  • Fungsi Hash
  • Kelayakan fungsi hash yang baik
  • Perlanggaran
  • Operasi meja Hash
  • Contoh Hash Meja Python
  • Penjelasan Kod Jadual Hash
  • Contoh Kamus Python
  • Analisis Kerumitan
  • Aplikasi Dunia Nyata
  • Kelebihan jadual hash
  • Kekurangan jadual hash

Apakah Jadual Hash?

A JADUAL HASH adalah struktur data bahawa nilai-nilai kedai menggunakan sepasang kunci dan nilai-nilai. Setiap nilai diberikan kunci unik yang dihasilkan menggunakan fungsi hash.

Nama kunci digunakan untuk mengakses nilai yang berkaitan. Ini menjadikan pencarian nilai dalam tabel hash sangat cepat, tanpa mengira jumlah item dalam jadual hash.

Fungsi Hash

Contohnya, jika kita mahu menyimpan rekod pekerja, dan setiap pekerja dikenal pasti menggunakan nombor pekerja.

Kita boleh menggunakan nombor pekerja sebagai kunci dan menetapkan data pekerja sebagai nilai.

Pendekatan di atas akan memerlukan ruang bebas tambahan dari urutan (m * n 2 ) di mana pemboleh ubah m adalah ukuran array, dan pemboleh ubah n adalah bilangan digit untuk nombor pekerja. Pendekatan ini memperkenalkan masalah ruang simpanan.

Fungsi hash menyelesaikan masalah di atas dengan mendapatkan nombor pekerja dan menggunakannya untuk menghasilkan nilai integer hash, digit tetap, dan mengoptimumkan ruang simpanan. Tujuan fungsi hash adalah untuk membuat kunci yang akan digunakan untuk merujuk nilai yang ingin kita simpan. Fungsi menerima nilai yang akan disimpan kemudian menggunakan algoritma untuk mengira nilai kunci.

Berikut adalah contoh fungsi hash sederhana

h(k) = k1 % m

DI SINI,

  • h (k) adalah fungsi hash yang menerima parameter k. Parameter k adalah nilai yang ingin kita kirakan kuncinya.
  • k 1 % m adalah algoritma untuk fungsi hash kami di mana k1 adalah nilai yang ingin kami simpan, dan m adalah ukuran senarai. Kami menggunakan pengendali modulus untuk mengira kunci.

Contohnya

Mari kita anggap bahawa kita mempunyai senarai dengan ukuran tetap 3 dan nilai berikut

[1,2,3]

Kita boleh menggunakan formula di atas untuk mengira kedudukan yang harus ditempati oleh setiap nilai.

Gambar berikut menunjukkan indeks yang tersedia dalam jadual hash kami.

Langkah 1)

Hitung kedudukan yang akan ditempati oleh nilai pertama seperti itu

h (1) = 1% 3

= 1

Nilai 1 akan memenuhi ruang pada indeks 1

Langkah 2)

Hitung kedudukan yang akan ditempati oleh nilai kedua

h (2) = 2% 3

= 2

Nilai 2 akan memenuhi ruang pada indeks 2

Langkah 3)

Hitung kedudukan yang akan ditempati oleh nilai ketiga.

h (3) = 3% 3

= 0

Nilai 3 akan memenuhi ruang pada indeks 0

Keputusan akhir

Jadual hash kami yang diisi sekarang adalah seperti berikut.

Kelayakan fungsi hash yang baik

Fungsi hash yang baik harus mempunyai kualiti berikut.

  • Rumus untuk menghasilkan hash harus menggunakan nilai data yang akan disimpan dalam algoritma.
  • Fungsi hash harus menghasilkan nilai hash yang unik walaupun untuk data input yang mempunyai jumlah yang sama.
  • Fungsi harus meminimumkan jumlah perlanggaran. Perlanggaran berlaku apabila nilai yang sama dihasilkan untuk lebih dari satu nilai.
  • Nilai mesti diedarkan secara konsisten ke seluruh keseluruhan hash yang mungkin.

Perlanggaran

Perlanggaran berlaku apabila algoritma menghasilkan hash yang sama untuk lebih dari satu nilai.

Mari lihat contohnya.

Anggaplah kita mempunyai senarai nilai berikut

[3,2,9,11,7]

Mari kita anggap bahawa ukuran jadual hash adalah 7, dan kita akan menggunakan formula (k 1 % m) di mana m adalah ukuran jadual hash.

Jadual berikut menunjukkan nilai hash yang akan dihasilkan.

Kunci Algoritma Hash (k 1 % m) Nilai Hash
3 3% 7 3
2 3% 7 2
9 3% 7 2
11 3% 7 4
7 3% 7 0

Seperti yang dapat kita lihat dari hasil di atas, nilai 2 dan 9 mempunyai nilai hash yang sama, dan kita tidak dapat menyimpan lebih dari satu nilai pada setiap kedudukan.

Masalah yang diberikan dapat diselesaikan dengan menggunakan chaining atau probing. Bahagian berikut membincangkan rantai dan penyiasatan secara terperinci.

Berantai

Chaining adalah teknik yang digunakan untuk menyelesaikan masalah perlanggaran dengan menggunakan senarai terpaut yang masing-masing mempunyai indeks unik.

Gambar berikut menggambarkan bagaimana senarai yang dirantai

Kedua-dua 2 dan 9 menempati indeks yang sama, tetapi disimpan sebagai senarai terpaut. Setiap senarai mempunyai pengecam unik.

Faedah senarai berantai

Berikut adalah faedah senarai yang dirantai:

  • Senarai berantai mempunyai prestasi yang lebih baik ketika memasukkan data kerana urutan sisipan adalah O (1).
  • Tidak perlu mengubah saiz jadual hash yang menggunakan senarai berantai.
  • Ia dapat menampung sejumlah besar nilai dengan mudah selagi ada ruang kosong.

Menyiasat

Teknik lain yang digunakan untuk menyelesaikan perlanggaran adalah probing. Semasa menggunakan kaedah probing, jika berlaku perlanggaran, kita boleh terus bergerak dan mencari slot kosong untuk menyimpan nilai kita.

Berikut adalah kaedah penyiasatan:

Kaedah Penerangan
Penyelidikan linear Sama seperti namanya, kaedah ini mencari slot kosong secara linear bermula dari kedudukan di mana perlanggaran berlaku dan bergerak ke hadapan. Sekiranya akhir senarai tercapai dan tiada slot kosong dijumpai. Pemeriksaan bermula pada awal senarai.
Pemeriksaan kuadratik Kaedah ini menggunakan ungkapan polinomial kuadratik untuk mencari slot percuma seterusnya yang tersedia.
Double Hashing Teknik ini menggunakan algoritma fungsi hash sekunder untuk mencari slot tersedia percuma seterusnya.

Dengan menggunakan contoh di atas, jadual hash setelah menggunakan probing akan muncul seperti berikut:

Operasi meja Hash

Berikut adalah operasi yang disokong oleh jadual Hash:

  • Penyisipan - Operasi ini digunakan untuk menambahkan elemen ke dalam jadual hash
  • Mencari - Operasi ini digunakan untuk mencari elemen dalam jadual hash menggunakan kunci
  • Menghapus - Operasi ini digunakan untuk menghapus elemen dari jadual hash

Memasukkan operasi data

Operasi sisipan digunakan untuk menyimpan nilai dalam jadual hash. Apabila nilai baru disimpan dalam jadual hash, ia diberi nombor indeks. Nombor indeks dikira menggunakan fungsi hash. Fungsi hash menyelesaikan sebarang perlanggaran yang berlaku semasa mengira nombor indeks.

Cari operasi data

Operasi carian digunakan untuk mencari nilai dalam tabel hash menggunakan nombor indeks. Operasi carian mengembalikan nilai yang dihubungkan dengan nombor indeks carian. Sebagai contoh, jika kita menyimpan nilai 6 pada indeks 2, operasi carian dengan nombor indeks 2 akan mengembalikan nilai 6.

Padamkan operasi data

Operasi hapus digunakan untuk membuang nilai dari jadual hash. Untuk menghapus Operasi dilakukan menggunakan nombor indeks. Setelah nilai dihapus, nombor indeks akan dibuat percuma. Ia dapat digunakan untuk menyimpan nilai lain menggunakan operasi sisipan.

Pelaksanaan Jadual Hash dengan Contoh Python

Mari kita lihat contoh mudah yang mengira nilai hash kunci

def hash_key( key, m):return key % mm = 7print(f'The hash value for 3 is {hash_key(3,m)}')print(f'The hash value for 2 is {hash_key(2,m)}')print(f'The hash value for 9 is {hash_key(9,m)}')print(f'The hash value for 11 is {hash_key(11,m)}')print(f'The hash value for 7 is {hash_key(7,m)}')

Penjelasan Kod Jadual Hash

DI SINI,

  1. Mentakrifkan fungsi hash_key yang menerima kunci parameter dan m.
  2. Menggunakan operasi modulus sederhana untuk menentukan nilai hash
  3. Menentukan pemboleh ubah m yang diinisialisasi ke nilai 7. Ini adalah ukuran jadual hash kami
  4. Mengira dan mencetak nilai hash 3
  5. Mengira dan mencetak nilai hash 2
  6. Mengira dan mencetak nilai hash 9
  7. Mengira dan mencetak nilai hash 11
  8. Mengira dan mencetak nilai hash 7

Melaksanakan kod di atas menghasilkan hasil berikut.

The hash value for 3 is 3The hash value for 2 is 2The hash value for 9 is 2The hash value for 11 is 4The hash value for 7 is 0

Contoh Kamus Python

Python dilengkapi dengan jenis data terbina dalam yang disebut Kamus. Kamus adalah contoh jadual hash. Ia menyimpan nilai menggunakan sepasang kunci dan nilai. Nilai hash dihasilkan secara automatik untuk kami, dan sebarang perlanggaran diselesaikan untuk kami di latar belakang.

Contoh berikut menunjukkan bagaimana anda boleh menggunakan jenis data kamus di python 3

employee = {'name': 'John Doe','age': 36,'position': 'Business Manager.'}print (f"The name of the employee is {employee['name']}")employee['position'] = 'Software Engineer'print (f"The position of {employee['name']} is {employee['position']}")employee.clear()print (employee)

DI SINI,

  1. Mentakrifkan pekerja pembolehubah kamus. Nama kunci digunakan untuk menyimpan nilai John Doe, kedai usia 36 tahun, dan kedudukan menyimpan nilai Pengurus Perniagaan.
  2. Mengambil nilai nama kunci dan mencetaknya di terminal
  3. Mengemas kini nilai kedudukan utama kepada nilai Jurutera Perisian
  4. Mencetak nilai nama dan kedudukan kekunci
  5. Padamkan semua nilai yang disimpan dalam pekerja pembolehubah kamus kami
  6. Mencetak nilai pekerja

Menjalankan kod di atas menghasilkan hasil berikut.

The name of the employee is John Doe.The position of John Doe is a Software Engineer.{}

Analisis Kerumitan

Jadual Hash mempunyai kerumitan waktu rata-rata O (1) dalam senario kes terbaik. Kerumitan masa yang paling teruk adalah O (n). Senario terburuk berlaku apabila banyak nilai menghasilkan kunci hash yang sama, dan kita harus menyelesaikan perlanggaran dengan menyiasat.

Aplikasi Dunia Nyata

Di dunia nyata, jadual hash digunakan untuk menyimpan data untuk

  • Pangkalan Data
  • Susunan bersekutu
  • Set
  • Cache memori

Kelebihan jadual hash

Berikut adalah kebaikan / faedah menggunakan jadual hash:

  • Jadual Hash mempunyai prestasi tinggi ketika mencari data, memasukkan, dan menghapus nilai yang ada.
  • Kerumitan masa untuk jadual hash adalah tetap tanpa mengira jumlah item dalam jadual.
  • Mereka berprestasi sangat baik walaupun bekerja dengan set data yang besar.

Kekurangan jadual hash

Berikut, keburukan menggunakan jadual hash:

  • Anda tidak boleh menggunakan nilai nol sebagai kunci.
  • Pertembungan tidak dapat dielakkan semasa menghasilkan kunci menggunakan. fungsi hash. Perlanggaran berlaku apabila kunci yang sudah digunakan dihasilkan.
  • Sekiranya fungsi hashing mempunyai banyak perlanggaran, ini dapat menyebabkan penurunan prestasi.

Ringkasan:

  • Jadual Hash digunakan untuk menyimpan data menggunakan sepasang kunci dan nilai.
  • Fungsi hash menggunakan algoritma matematik untuk mengira nilai hash.
  • Perlanggaran berlaku apabila nilai hash yang sama dihasilkan untuk lebih dari satu nilai.
  • Chaining menyelesaikan pertembungan dengan membuat senarai terpaut.
  • Menyiasat menyelesaikan perlanggaran dengan mencari slot kosong di jadual hash.
  • Penyelidikan linear mencari slot percuma seterusnya untuk menyimpan nilai bermula dari slot di mana perlanggaran berlaku.
  • Pemeriksaan kuadratik menggunakan ungkapan polinomial untuk mencari slot percuma seterusnya apabila berlaku perlanggaran.
  • Double hashing menggunakan algoritma fungsi hash sekunder untuk mencari slot percuma seterusnya apabila berlaku perlanggaran.
  • Jadual Hash mempunyai prestasi yang lebih baik jika dibandingkan dengan struktur data lain.
  • Kerumitan masa rata-rata jadual hash adalah O (1)
  • Jenis data kamus dalam python adalah contoh jadual hash.
  • Jadual Hash menyokong operasi memasukkan, mencari dan memadam.
  • Nilai nol tidak boleh digunakan sebagai nilai indeks.
  • Pertembungan tidak dapat dielakkan dalam fungsi hash. Fungsi hash yang baik meminimumkan jumlah perlanggaran yang berlaku untuk meningkatkan prestasi.