Tabel Hash dalam Struktur Data: Contoh Python

Daftar Isi:

Anonim

Apa itu Hashing?

Hash adalah nilai yang memiliki panjang tetap, dan dibuat menggunakan rumus matematika. Nilai hash digunakan dalam kompresi data, kriptologi, dll. Dalam pengindeksan data, nilai hash digunakan karena memiliki ukuran panjang tetap terlepas dari nilai yang digunakan untuk membuatnya. Itu membuat nilai hash menempati ruang minimal dibandingkan dengan nilai lain dengan panjang yang bervariasi.

Fungsi hash menggunakan algoritme matematika untuk mengubah kunci menjadi hash. Tabrakan terjadi ketika fungsi hash menghasilkan nilai hash yang sama untuk lebih dari satu kunci.

Dalam tutorial Algoritma ini, Anda akan mempelajari:

  • Apa itu Hashing?
  • Apa itu Tabel Hash?
  • Fungsi hash
  • Kualitas fungsi hash yang baik
  • Tabrakan
  • Operasi tabel hash
  • Contoh Python Tabel Hash
  • Penjelasan Kode Tabel Hash
  • Contoh Kamus Python
  • Analisis Kompleksitas
  • Aplikasi dunia nyata
  • Keuntungan dari tabel hash
  • Kekurangan tabel hash

Apa itu Tabel Hash?

Sebuah TABLE Hash adalah struktur data bahwa nilai-nilai toko menggunakan sepasang kunci dan nilai-nilai. Setiap nilai diberi kunci unik yang dihasilkan menggunakan fungsi hash.

Nama kunci digunakan untuk mengakses nilai yang terkait. Hal ini membuat pencarian nilai dalam tabel hash menjadi sangat cepat, terlepas dari jumlah item dalam tabel hash.

Fungsi hash

Misalnya, jika kita ingin menyimpan catatan karyawan, dan setiap karyawan diidentifikasi secara unik menggunakan nomor karyawan.

Kita dapat menggunakan nomor karyawan sebagai kunci dan menetapkan data karyawan sebagai nilainya.

Pendekatan di atas akan membutuhkan ruang bebas ekstra berorde (m * n 2 ) di mana variabel m adalah ukuran larik, dan variabel n adalah jumlah digit untuk nomor karyawan. Pendekatan ini menimbulkan masalah ruang penyimpanan.

Fungsi hash memecahkan masalah di atas dengan mendapatkan nomor karyawan dan menggunakannya untuk menghasilkan nilai integer hash, digit tetap, dan mengoptimalkan ruang penyimpanan. Tujuan dari fungsi hash adalah untuk membuat kunci yang akan digunakan untuk mereferensikan nilai yang ingin kita simpan. Fungsi tersebut menerima nilai yang akan disimpan kemudian menggunakan algoritma untuk menghitung nilai kunci tersebut.

Berikut ini adalah contoh fungsi hash sederhana

h(k) = k1 % m

SINI,

  • h (k) adalah fungsi hash yang menerima parameter k. Parameter k adalah nilai yang ingin kita hitung kuncinya.
  • k 1 % m adalah algoritma untuk fungsi hash kita di mana k1 adalah nilai yang ingin kita simpan, dan m adalah ukuran daftar. Kami menggunakan operator modulus untuk menghitung kuncinya.

Contoh

Mari kita asumsikan bahwa kita memiliki daftar dengan ukuran tetap 3 dan nilai-nilai berikut

[1,2,3]

Kita dapat menggunakan rumus di atas untuk menghitung posisi yang harus ditempati setiap nilai.

Gambar berikut menunjukkan indeks yang tersedia di tabel hash kami.

Langkah 1)

Hitung posisi yang akan ditempati oleh nilai pertama seperti itu

jam (1) = 1% 3

= 1

Nilai 1 akan menempati ruang pada indeks 1

Langkah 2)

Hitung posisi yang akan ditempati oleh nilai kedua

jam (2) = 2% 3

= 2

Nilai 2 akan menempati ruang pada indeks 2

Langkah 3)

Hitung posisi yang akan ditempati oleh nilai ketiga.

jam (3) = 3% 3

= 0

Nilai 3 akan menempati ruang pada indeks 0

Hasil Akhir

Tabel hash terisi kami sekarang akan menjadi sebagai berikut.

Kualitas fungsi hash yang baik

Fungsi hash yang baik harus memiliki kualitas berikut.

  • Rumus untuk menghasilkan hash harus menggunakan nilai data yang akan disimpan dalam algoritma.
  • Fungsi hash harus menghasilkan nilai hash yang unik bahkan untuk data masukan yang memiliki jumlah yang sama.
  • Fungsi tersebut harus meminimalkan jumlah tabrakan. Benturan terjadi ketika nilai yang sama dibuat untuk lebih dari satu nilai.
  • Nilai harus didistribusikan secara konsisten di seluruh kemungkinan hash.

Tabrakan

Tabrakan terjadi saat algoritme menghasilkan hash yang sama untuk lebih dari satu nilai.

Mari kita lihat contohnya.

Misalkan kita memiliki daftar nilai berikut

[3,2,9,11,7]

Mari kita asumsikan bahwa ukuran tabel hash adalah 7, dan kita akan menggunakan rumus (k 1 % m) di mana m adalah ukuran tabel hash.

Tabel 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 memiliki nilai hash yang sama, dan kita tidak dapat menyimpan lebih dari satu nilai pada setiap posisi.

Masalah yang diberikan dapat diselesaikan dengan menggunakan chaining atau probing. Bagian berikut membahas chaining dan probing secara detail.

Merantai

Chaining adalah teknik yang digunakan untuk menyelesaikan masalah collision dengan menggunakan linked list yang masing-masing memiliki indeks unik.

Gambar berikut memvisualisasikan bagaimana daftar yang dirantai terlihat

Baik 2 dan 9 menempati indeks yang sama, tetapi disimpan sebagai daftar tertaut. Setiap daftar memiliki pengenal unik.

Manfaat daftar dirantai

Berikut ini adalah manfaat dari daftar berantai:

  • Daftar yang dirantai memiliki kinerja yang lebih baik saat memasukkan data karena urutan penyisipannya adalah O (1).
  • Tidak perlu mengubah ukuran tabel hash yang menggunakan daftar berantai.
  • Ini dapat dengan mudah menampung sejumlah besar nilai selama ruang kosong tersedia.

Probing

Teknik lain yang digunakan untuk mengatasi tabrakan adalah probing. Saat menggunakan metode probing, jika tabrakan terjadi, kita dapat melanjutkan dan mencari slot kosong untuk menyimpan nilai kita.

Berikut ini adalah metode probing:

metode Deskripsi
Pemeriksaan linier Seperti namanya, metode ini mencari slot kosong secara linier mulai dari posisi terjadinya tabrakan dan bergerak maju. Jika akhir daftar tercapai dan tidak ada slot kosong yang ditemukan. Pemeriksaan dimulai di awal daftar.
Penyelidikan kuadrat Metode ini menggunakan ekspresi polinomial kuadrat untuk mencari slot kosong berikutnya yang tersedia.
Hashing Ganda Teknik ini menggunakan algoritma fungsi hash sekunder untuk menemukan slot gratis berikutnya yang tersedia.

Menggunakan contoh kami di atas, tabel hash setelah menggunakan probing akan muncul sebagai berikut:

Operasi tabel hash

Di sini, adalah Operasi yang didukung oleh tabel Hash:

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

Memasukkan operasi data

Operasi penyisipan digunakan untuk menyimpan nilai dalam tabel hash. Ketika nilai baru disimpan dalam tabel hash, itu diberi nomor indeks. Nomor indeks dihitung menggunakan fungsi hash. Fungsi hash menyelesaikan setiap tabrakan yang terjadi saat menghitung nomor indeks.

Cari operasi data

Operasi pencarian digunakan untuk mencari nilai dalam tabel hash menggunakan nomor indeks. Operasi pencarian mengembalikan nilai yang ditautkan ke nomor indeks pencarian. Misalnya, jika kita menyimpan nilai 6 pada indeks 2, operasi pencarian dengan nomor indeks 2 akan mengembalikan nilai 6.

Hapus operasi data

Operasi delete digunakan untuk menghapus nilai dari tabel hash. Untuk menghapus Operasi dilakukan dengan menggunakan nomor indeks. Setelah nilai dihapus, nomor indeks dibebaskan. Ini dapat digunakan untuk menyimpan nilai lain menggunakan operasi penyisipan.

Implementasi Tabel Hash dengan Contoh Python

Mari kita lihat contoh sederhana yang menghitung nilai hash dari sebuah 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 Kode Tabel Hash

SINI,

  1. Mendefinisikan sebuah fungsi hash_key yang menerima kunci parameter dan m.
  2. Menggunakan operasi modulus sederhana untuk menentukan nilai hash
  3. Mendefinisikan variabel m yang diinisialisasi ke nilai 7. Ini adalah ukuran tabel hash kami
  4. Menghitung dan mencetak nilai hash 3
  5. Menghitung dan mencetak nilai hash 2
  6. Menghitung dan mencetak nilai hash 9
  7. Menghitung dan mencetak nilai hash 11
  8. Menghitung dan mencetak nilai hash 7

Menjalankan kode di atas menghasilkan hasil sebagai 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 hadir dengan tipe data built-in yang disebut Dictionary. Kamus adalah contoh tabel hash. Ini menyimpan nilai menggunakan sepasang kunci dan nilai. Nilai hash dibuat secara otomatis untuk kami, dan setiap benturan diselesaikan untuk kami di latar belakang.

Contoh berikut menunjukkan bagaimana Anda dapat menggunakan tipe 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)

SINI,

  1. Mendefinisikan karyawan variabel kamus. Nama kunci digunakan untuk menyimpan nilai John Doe, usia penyimpanan 36, dan posisi menyimpan nilai Manajer Bisnis.
  2. Mengambil nilai dari nama kunci dan mencetaknya di terminal
  3. Memperbarui nilai posisi kunci ke nilai Software Engineer
  4. Mencetak nilai nama dan posisi kunci
  5. Menghapus semua nilai yang disimpan di karyawan variabel kamus kami
  6. Mencetak nilai karyawan

Menjalankan kode di atas menghasilkan hasil sebagai berikut.

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

Analisis Kompleksitas

Tabel hash memiliki kompleksitas waktu rata-rata O (1) dalam skenario kasus terbaik. Kompleksitas waktu kasus terburuk adalah O (n). Skenario terburuk terjadi ketika banyak nilai menghasilkan kunci hash yang sama, dan kita harus menyelesaikan benturan dengan probing.

Aplikasi dunia nyata

Di dunia nyata, tabel hash digunakan untuk menyimpan data

  • Database
  • Array asosiatif
  • Set
  • Cache memori

Keuntungan dari tabel hash

Berikut, keuntungan / keuntungan menggunakan tabel hash:

  • Tabel hash memiliki kinerja tinggi saat mencari data, memasukkan, dan menghapus nilai yang ada.
  • Kompleksitas waktu untuk tabel hash adalah konstan terlepas dari jumlah item dalam tabel.
  • Mereka berkinerja sangat baik bahkan saat bekerja dengan kumpulan data besar.

Kekurangan tabel hash

Berikut, kontra menggunakan tabel hash:

  • Anda tidak dapat menggunakan nilai null sebagai kunci.
  • Tabrakan tidak dapat dihindari saat membuat kunci menggunakan. fungsi hash. Tabrakan terjadi saat kunci yang sudah digunakan dibuat.
  • Jika fungsi hashing mengalami banyak benturan, ini dapat menyebabkan penurunan performa.

Ringkasan:

  • Tabel hash digunakan untuk menyimpan data menggunakan sepasang kunci dan nilai.
  • Fungsi hash menggunakan algoritme matematika untuk menghitung nilai hash.
  • Tabrakan terjadi ketika nilai hash yang sama dibuat untuk lebih dari satu nilai.
  • Chaining memecahkan tabrakan dengan membuat daftar tertaut.
  • Probing memecahkan tabrakan dengan menemukan slot kosong di tabel hash.
  • Linear probing mencari slot kosong berikutnya untuk menyimpan nilai mulai dari slot tempat tumbukan terjadi.
  • Penyelidikan kuadrat menggunakan ekspresi polinomial untuk menemukan slot kosong berikutnya saat tabrakan terjadi.
  • Hash ganda menggunakan algoritme fungsi hash sekunder untuk menemukan slot kosong berikutnya saat tabrakan terjadi.
  • Tabel hash memiliki kinerja yang lebih baik jika dibandingkan dengan struktur data lainnya.
  • Kompleksitas waktu rata-rata dari tabel hash adalah O (1)
  • Tipe data kamus dalam python adalah contoh tabel hash.
  • Tabel hash mendukung operasi penyisipan, pencarian, dan penghapusan.
  • Nilai null tidak dapat digunakan sebagai nilai indeks.
  • Tabrakan tidak dapat dihindari dalam fungsi hash. Fungsi hash yang baik meminimalkan jumlah tabrakan yang terjadi untuk meningkatkan kinerja.