Tabel Hash dalam Struktur Data: Python Example

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 N²) 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 mengambil nomor karyawan dan menggunakannya untuk menghasilkan nilai hash integer, dengan jumlah digit tetap, dan mengoptimalkan ruang penyimpanan. Tujuan dari fungsi hash adalah untuk membuat kunci yang akan digunakan untuk merujuk 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₁ % 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 (k₁ % m) di mana m adalah ukuran tabel hash.

Tabel berikut menunjukkan nilai hash yang akan dihasilkan.

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:

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)}')

Tabel Hash Code Penjelasan

SINI,

1. Mendefinisikan 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 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,

1. Mendefinisikan karyawan variabel kamus. Nama kunci digunakan untuk menyimpan nilai John Doe, umur penyimpanan 36, dan posisi menyimpan nilai Manajer Bisnis.
2. Mengambil nilai nama kunci dan mencetaknya di terminal
3. Memperbarui nilai posisi kunci menjadi nilai Insinyur Perangkat Lunak
4. Mencetak nilai nama dan posisi kunci
5. Menghapus semua nilai yang disimpan dalam variabel kamus kita karyawan
6. 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.

Pertanyaan Umum Demo Slot