Tabel Hash dalam Struktur Data: Python Example
Sarah Chen
Apa itu Hashing?
Hash adalah nilai yang memiliki panjang tetap, dan dihasilkan menggunakan rumus matematika. Nilai hash digunakan dalam kompresi data, kriptologi, dll. Dalam pengindeksan data, nilai hash digunakan karena memiliki ukuran panjang yang tetap terlepas dari nilai yang digunakan untuk menghasilkannya. Itu membuat nilai hash menempati ruang minimal dibandingkan dengan nilai lain dengan panjang yang bervariasi.
Fungsi hash menggunakan algoritma matematika untuk mengubah kunci menjadi hash. Tabrakan terjadi ketika fungsi hash menghasilkan nilai hash yang sama untuk lebih dari satu kunci.
Apa itu Tabel Hash?
A TABEL HASH adalah struktur data yang menyimpan nilai menggunakan sepasang kunci dan nilai. Setiap nilai diberi kunci unik yang dihasilkan menggunakan fungsi hash.
Nama kunci digunakan untuk mengakses nilai terkaitnya. Hal ini membuat pencarian nilai dalam tabel hash menjadi sangat cepat, berapa pun 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 kosong ekstra (M N2) dimana variabel m adalah ukuran susunan, dan variabel n adalah jumlah digit 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 untuk disimpan kemudian menggunakan algoritma untuk menghitung nilai kunci.
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.
- k1 % m adalah algoritma untuk fungsi hash kita, di mana k1 adalah nilai yang ingin kita simpan, dan m adalah ukuran daftar. Kita menggunakan operator modulus untuk menghitung kunci.
Example
Mari kita asumsikan 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 oleh 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 menyala indeks 1
Langkah 2) Hitung posisi yang akan ditempati oleh nilai kedua
jam(2) = 2 % 3
= 2
Nilai 2 akan menempati ruang menyala indeks 2
Langkah 3) Hitung posisi yang akan ditempati oleh nilai ketiga.
jam(3) = 3 % 3
= 0
Nilai 3 akan menempati ruang menyala indeks 0
Hasil akhir
Tabel hash yang kita isi sekarang akan menjadi seperti 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. Tabrakan terjadi ketika nilai yang sama dihasilkan untuk lebih dari satu nilai.
- Nilai-nilai tersebut harus didistribusikan secara konsisten ke seluruh kemungkinan hash.
Tabrakan
Tabrakan terjadi ketika algoritme menghasilkan hash yang sama untuk lebih dari satu nilai.
Mari kita lihat sebuah contoh.
Misalkan kita memiliki daftar nilai berikut
[3,2,9,11,7]
Misalkan ukuran tabel hash adalah 7, dan kita akan menggunakan rumus (k1 % m) di mana m adalah ukuran tabel hash.
Tabel berikut menunjukkan nilai hash yang akan dihasilkan.
| kunci | Algoritma Hash (k1% 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 bisa kita lihat dari hasil di atas, nilai 2 dan 9 memiliki nilai hash yang sama, dan kita tidak bisa menyimpan lebih dari satu nilai di setiap posisi.
Masalah yang diberikan dapat dipecahkan dengan menggunakan chaining atau probing. Bagian berikut membahas chaining dan probing secara terperinci.
Rantai
Chaining merupakan suatu teknik yang digunakan untuk menyelesaikan masalah tabrakan dengan menggunakan linked list yang masing-masing mempunyai indeks unik.
Gambar berikut memvisualisasikan seperti apa tampilan daftar berantai
Baik 2 maupun 9 menempati indeks yang sama, namun disimpan sebagai daftar tertaut. Setiap daftar memiliki pengidentifikasi unik.
Manfaat daftar berantai
Berikut ini adalah manfaat dari daftar berantai:
- Daftar berantai memiliki performa 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 tersedia ruang kosong.
Menyelidiki
Teknik lain yang digunakan untuk mengatasi tabrakan adalah probing. Saat menggunakan metode probing, jika terjadi tabrakan, kita cukup melanjutkan dan mencari slot kosong untuk menyimpan nilai kita.
Berikut ini adalah metode probing:
| metode | Description |
|---|---|
| Pemeriksaan linier | Seperti namanya, metode ini mencari slot kosong secara linier dimulai dari posisi terjadinya tumbukan dan seterusnya. Jika akhir daftar tercapai dan tidak ditemukan slot kosong. Penyelidikan dimulai dari awal daftar. |
| Pemeriksaan kuadratik | Metode ini menggunakan ekspresi polinomial kuadrat untuk mencari slot kosong berikutnya. |
| Double Hashing | Teknik ini menggunakan algoritma fungsi hash sekunder untuk menemukan slot gratis berikutnya. |
Dengan menggunakan contoh di atas, tabel hash setelah menggunakan probing akan muncul sebagai berikut:
Operasi tabel hash
Ini dia Operations didukung oleh tabel Hash:
- Insersi - ini Operation digunakan untuk menambahkan elemen ke tabel hash
- Pencarian - ini Operation digunakan untuk mencari elemen dalam tabel hash menggunakan kunci
- menghapus - ini Operation digunakan untuk menghapus elemen dari tabel hash
Operasi memasukkan data
Operasi penyisipan digunakan untuk menyimpan nilai dalam tabel hash. Saat nilai baru disimpan dalam tabel hash, nilai tersebut diberi nomor indeks. Nomor indeks dihitung menggunakan fungsi hash. Fungsi hash mengatasi setiap benturan 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 hapus digunakan untuk menghapus nilai dari tabel hash. Untuk menghapus OperaPenghapusan dilakukan dengan menggunakan nomor indeks. Setelah nilai dihapus, nomor indeks dibebaskan. Nomor indeks dapat digunakan untuk menyimpan nilai lain menggunakan operasi penyisipan.
Implementasi Tabel Hash dengan Python Example
Mari kita lihat contoh sederhana yang menghitung nilai hash suatu kunci
def hash_key( key, m):
return key % m
m = 7
print(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,
- Mendefinisikan fungsi hash_key yang menerima kunci parameter dan m.
- Menggunakan operasi modulus sederhana untuk menentukan nilai hash
- Mendefinisikan variabel m yang diinisialisasi ke nilai 7. Ini adalah ukuran tabel hash kami
- Menghitung dan mencetak nilai hash 3
- Menghitung dan mencetak nilai hash 2
- Menghitung dan mencetak nilai hash 9
- Menghitung dan mencetak nilai hash 11
- Menghitung dan mencetak nilai hash 7
Menjalankan kode di atas menghasilkan hasil berikut.
The hash value for 3 is 3 The hash value for 2 is 2 The hash value for 9 is 2 The hash value for 11 is 4 The hash value for 7 is 0
Python Contoh Kamus
Python hadir dengan tipe data bawaan yang disebut Kamus. 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 ular piton 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,
- Mendefinisikan karyawan variabel kamus. Nama kunci digunakan untuk menyimpan nilai John Doe, umur penyimpanan 36, dan posisi menyimpan nilai Manajer Bisnis.
- Mengambil nilai nama kunci dan mencetaknya di terminal
- Memperbarui nilai posisi kunci menjadi nilai Insinyur Perangkat Lunak
- Mencetak nilai nama dan posisi kunci
- Menghapus semua nilai yang disimpan dalam variabel kamus kita karyawan
- Mencetak nilai karyawan
Menjalankan kode di atas menghasilkan hasil 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 kasus terburuk terjadi ketika banyak nilai menghasilkan kunci hash yang sama, dan kita harus menyelesaikan tabrakan dengan penyelidikan.
Aplikasi dunia nyata
Di dunia nyata, tabel hash digunakan untuk menyimpan data
- Database
- Array asosiatif
- set
- Cache memori
Keuntungan dari tabel hash
Berikut ini kelebihan/manfaat menggunakan tabel hash:
- Tabel hash memiliki performa tinggi saat mencari data, menyisipkan, dan menghapus nilai yang ada.
- Kompleksitas waktu untuk tabel hash adalah konstan berapa pun jumlah item dalam tabel.
- Mereka bekerja dengan sangat baik bahkan ketika bekerja dengan kumpulan data yang besar.
Kekurangan tabel hash
Berikut ini kekurangan penggunaan tabel hash:
- Anda tidak dapat menggunakan nilai null sebagai kunci.
- Tabrakan tidak dapat dihindari saat membuat kunci menggunakan. fungsi hash. Tabrakan terjadi ketika kunci yang sedang digunakan dibuat.
- Jika fungsi hashing mengalami banyak tabrakan, hal ini dapat menyebabkan penurunan kinerja.
Kesimpulan
- Tabel hash digunakan untuk menyimpan data menggunakan sepasang kunci dan nilai.
- Fungsi hash menggunakan algoritma matematika untuk menghitung nilai hash.
- Tabrakan terjadi ketika nilai hash yang sama dihasilkan untuk lebih dari satu nilai.
- Chaining menyelesaikan tabrakan dengan membuat daftar tertaut.
- Probing menyelesaikan tabrakan dengan menemukan slot kosong di tabel hash.
- Probing linier mencari slot kosong berikutnya untuk menyimpan nilai dimulai dari slot tempat terjadinya tumbukan.
- Penyelidikan kuadratik menggunakan ekspresi polinomial untuk menemukan slot bebas berikutnya ketika terjadi tumbukan.
- Double hashing menggunakan algoritma fungsi hash sekunder untuk menemukan slot kosong berikutnya ketika terjadi tabrakan.
- Tabel hash memiliki performa yang lebih baik jika dibandingkan dengan struktur data lainnya.
- Kompleksitas waktu rata-rata tabel hash adalah O (1)
- Tipe data kamus di 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.
