Hashing dalam Struktur Data: Fungsi, Teknik [Dengan Contoh]

Diterbitkan: 2021-05-02

Daftar isi

pengantar

Hashing adalah struktur data penting yang dirancang untuk memecahkan masalah menemukan dan menyimpan data secara efisien dalam array. Misalnya, jika Anda memiliki daftar 20000 nomor, dan Anda telah memberikan nomor untuk dicari dalam daftar itu- Anda akan memindai setiap nomor dalam daftar sampai Anda menemukan kecocokan.

Ini membutuhkan banyak waktu Anda untuk mencari di seluruh daftar dan menemukan nomor tertentu itu. Proses pemindaian manual ini tidak hanya memakan waktu tetapi juga tidak efisien. Dengan hashing dalam struktur data, Anda dapat mempersempit pencarian dan menemukan nomor dalam hitungan detik.

Blog ini akan memberi Anda pemahaman yang lebih dalam tentang metode hash, tabel hash, dan penyelidikan linier dengan contoh-contohnya.

Apa itu Hashing dalam Struktur Data?

Hashing dalam struktur data adalah teknik pemetaan potongan besar data ke dalam tabel kecil menggunakan fungsi hashing. Ini juga dikenal sebagai fungsi intisari pesan. Ini adalah teknik yang secara unik mengidentifikasi item tertentu dari koleksi item serupa.

Ini menggunakan tabel hash untuk menyimpan data dalam format array. Setiap nilai dalam array telah diberi nomor indeks yang unik. Tabel hash menggunakan teknik untuk menghasilkan nomor indeks unik ini untuk setiap nilai yang disimpan dalam format array. Teknik ini disebut teknik hash.

Anda hanya perlu mencari indeks barang yang diinginkan, bukan mencari datanya. Dengan pengindeksan, Anda dapat dengan cepat memindai seluruh daftar dan mengambil item yang Anda inginkan. Pengindeksan juga membantu dalam menyisipkan operasi saat Anda perlu memasukkan data di lokasi tertentu. Tidak peduli seberapa besar atau kecil tabelnya, Anda dapat memperbarui dan mengambil data dalam hitungan detik.

Hashing dalam struktur data adalah proses dua langkah.

  1. Fungsi hash mengubah item menjadi bilangan bulat kecil atau nilai hash. Integer ini digunakan sebagai indeks untuk menyimpan data asli.
  2. Ini menyimpan data dalam tabel hash. Anda dapat menggunakan kunci hash untuk menemukan data dengan cepat.

Contoh Hashing dalam Struktur Data

Berikut ini adalah contoh nyata dari hashing dalam struktur data –

  • Di sekolah, guru memberikan nomor gulungan unik untuk setiap siswa. Kemudian, guru menggunakan nomor gulungan itu untuk mengambil informasi tentang siswa itu.
  • Sebuah perpustakaan memiliki jumlah buku yang tidak terbatas. Pustakawan memberikan nomor unik untuk setiap buku. Nomor unik ini membantu dalam mengidentifikasi posisi buku di rak buku.

Checkout: Menyortir dalam Struktur Data

Fungsi Hash

Fungsi hash dalam struktur data memetakan ukuran data sewenang-wenang ke data berukuran tetap. Ini mengembalikan nilai-nilai berikut: nilai integer kecil (juga dikenal sebagai nilai hash), kode hash, dan jumlah hash.

hash = fungsi hash(kunci)

indeks = hash % array_size

Fungsi has harus memenuhi persyaratan berikut:

  • Fungsi hash yang baik mudah untuk dihitung.
  • Fungsi hash yang baik tidak pernah terjebak dalam pengelompokan dan mendistribusikan kunci secara merata di seluruh tabel hash.
  • Fungsi hash yang baik menghindari tabrakan ketika dua elemen atau item ditugaskan ke nilai hash yang sama.

Tabel Hash

Hashing dalam struktur data menggunakan tabel hash untuk menyimpan pasangan kunci-nilai. Tabel hash kemudian menggunakan fungsi hash untuk menghasilkan indeks. Hashing menggunakan indeks unik ini untuk melakukan operasi penyisipan, pembaruan, dan pencarian.

Bagaimana Hashing dalam Struktur Data Bekerja?

Dalam hashing, fungsi hashing memetakan string atau angka ke nilai integer kecil. Tabel hash mengambil item dari daftar menggunakan fungsi hashing. Tujuan dari teknik hashing adalah untuk mendistribusikan data secara merata di seluruh array. Hashing memberikan semua elemen kunci unik. Tabel hash menggunakan kunci ini untuk mengakses data dalam daftar.

Tabel hash menyimpan data dalam pasangan nilai kunci. Kunci bertindak sebagai input ke fungsi hashing. Fungsi hashing kemudian menghasilkan nomor indeks unik untuk setiap nilai yang disimpan. Nomor indeks menyimpan nilai yang sesuai dengan kunci itu. Fungsi hash mengembalikan nilai integer kecil sebagai output. Output dari fungsi hashing disebut nilai hash.

Mari kita memahami hashing dalam struktur data dengan sebuah contoh. Bayangkan Anda perlu menyimpan beberapa item (diatur dalam pasangan nilai kunci) di dalam tabel hash dengan 30 sel.

Nilainya adalah: (3,21) (1,72) (40,36) (5,30) (11,44) (15,33) (18,12) (16,80) (38,99)

Tabel hash akan terlihat seperti berikut:

Nomor seri Kunci hash Indeks Array
1 3 3%30 = 3 3
2 1 1%30 = 1 1
3 40 40%30 = 10 10
4 5 5%30 = 5 5
5 11 11%30 = 11 11
6 15 15%30 = 15 15
7 18 18%30 = 18 18
8 16 16%30 = 16 16
9 38 38%30 = 8 8

Baca Juga: Jenis-Jenis Struktur Data di Python

Teknik Resolusi Tabrakan

Hashing dalam struktur data jatuh ke dalam tabrakan jika dua kunci diberi nomor indeks yang sama dalam tabel hash. Tabrakan menciptakan masalah karena setiap indeks dalam tabel hash seharusnya menyimpan hanya satu nilai. Hashing dalam struktur data menggunakan beberapa teknik resolusi tabrakan untuk mengelola kinerja tabel hash.

Penyelidikan Linier

Hashing dalam struktur data menghasilkan indeks array yang sudah ditempati untuk menyimpan nilai. Dalam kasus seperti itu, hashing melakukan operasi pencarian dan menyelidiki secara linier untuk sel kosong berikutnya.

Contoh Penyelidikan Linier

Bayangkan Anda telah diminta untuk menyimpan beberapa item di dalam tabel hash berukuran 30. Item tersebut sudah diurutkan dalam format pasangan nilai kunci. Nilai yang diberikan adalah: (3,21) (1,72) (63,36) (5,30) (11,44) (15,33) (18,12) (16,80) (46,99) .

Hash(n) adalah indeks yang dihitung menggunakan fungsi hash dan T adalah ukuran tabel. Jika indeks slot = ( hash(n) % T) penuh, maka kita mencari indeks slot berikutnya dengan menambahkan 1 ((hash(n) + 1) % T). Jika (hash(n) + 1) % T juga penuh, maka kita coba (hash(n) + 2) % T. Jika (hash(n) + 2) % T juga penuh, maka kita coba (hash( n) + 3) % T.

Tabel hash akan terlihat seperti berikut:

Nomor seri Kunci hash Indeks Array Indeks Array setelah Linear Probing
1 3 3%30 = 3 3 3
2 1 1%30 = 1 1 1
3 63 63%30 = 3 3 4
4 5 5%30 = 5 5 5
5 11 11%30 = 11 11 11
6 15 15%30 = 15 15 15
7 18 18%30 = 18 18 18
8 16 16%30 = 16 16 16
9 46 46%30 = 8 16 17

Hashing ganda

Teknik double hashing menggunakan dua fungsi hash. Fungsi hash kedua mulai digunakan ketika fungsi pertama menyebabkan tabrakan. Ini menyediakan indeks offset untuk menyimpan nilai.

Rumus untuk teknik double hashing adalah sebagai berikut:

(firstHash(key) + i * secondHash(key)) % sizeOfTable

Dimana i adalah nilai offset. Nilai offset ini terus bertambah hingga menemukan slot kosong.

Misalnya, Anda memiliki dua fungsi hash: h1 dan h2. Anda harus melakukan langkah-langkah berikut untuk menemukan slot kosong:

  1. Verifikasi apakah hash1(kunci) kosong. Jika ya, maka simpan nilainya di slot ini.
  2. Jika hash1(key) tidak kosong, cari slot lain menggunakan hash2(key).
  3. Verifikasi apakah hash1(key) + hash2(key) kosong. Jika ya, maka simpan nilainya di slot ini.
  4. Terus tambahkan penghitung dan ulangi dengan hash1(key)+2hash2(key), hash1(key)+3hash2(key), dan seterusnya, sampai menemukan slot kosong.

Contoh Hashing Ganda

Bayangkan Anda perlu menyimpan beberapa item di dalam tabel hash berukuran 20. Nilai yang diberikan adalah: (16, 8, 63, 9, 27, 37, 48, 5, 69, 34, 1).

h1(n)=n%20

h2(n)=n%13

nh(n, i) = (h1 (n) + ih2(n)) mod 20

n h(n,i) = (h'(n) + i 2 ) %20
16 I = 0, h(n,0) = 16
8 I = 0, h(n,0) = 8
63 I = 0, h(n,0) = 3
9 I = 0, h(n,0) = 9
27 I = 0, h(n,0) = 7
37 I = 0, h(n,0) = 17
48 I = 0, h(n,0) = 8

I = 0, h(n,1) = 9

I = 0, h(n,2) = 12

5 I = 0, h(n,0) = 5
69 I = 0, h(n,0) = 9

I = 0, h(n,1) = 10

34 I = 0, h(n,0) = 14
1 I = 0, h(n,0) = 1
Pelajari Kursus Pengembangan Perangkat Lunak online dari Universitas top dunia. Dapatkan Program PG Eksekutif, Program Sertifikat Tingkat Lanjut, atau Program Magister untuk mempercepat karier Anda.

Kesimpulan

Double hashing memiliki biaya komputasi yang tinggi, tetapi pencarian slot gratis berikutnya lebih cepat daripada metode probing linier. Contoh yang diberikan dalam artikel hanya untuk tujuan penjelasan. Anda dapat mengubah pernyataan yang diberikan di atas sesuai kebutuhan Anda. Di blog ini, kita belajar tentang konsep hashing dalam struktur data .

Anda dapat mencoba contoh untuk memperkuat pengetahuan struktur data Anda. Jika Anda ingin tahu lebih banyak tentang struktur data , lihat Program PG Eksekutif upGrad dalam kursus Pengembangan Stack Penuh. Kursus ini dirancang untuk para profesional yang bekerja dan menawarkan pelatihan yang ketat dan penempatan kerja dengan perusahaan-perusahaan top.

Apa itu tabel hash?

Tabel hash adalah implementasi dari array asosiatif, struktur yang digunakan dalam pemrograman komputer untuk mengimplementasikan tipe data abstrak (ADT). Dalam tipe data abstrak, programmer tidak perlu mengetahui detail implementasi tipe data (seperti bagaimana data disimpan dalam memori), hanya operasi yang dapat dilakukan pada tipe data. Tabel hash menggunakan fungsi hash untuk menghitung indeks ke dalam array ember atau slot, dari mana nilai yang diinginkan dapat ditemukan. Tabel Hash digunakan untuk mengimplementasikan peta seperti struktur data. Tabel hash sangat banyak digunakan di komputer modern untuk mengimplementasikan hal-hal seperti kamus (seperti dalam python), larik asosiatif (seperti dalam php), tabel hash java, dll. Tabel hash biasanya diimplementasikan dalam bahasa sebagai larik nilai yang diurutkan berdasarkan kuncinya . Ini membuat operasi pencarian dan penyisipan/penghapusan menjadi sangat cepat, karena data disimpan secara sistematis dalam memori.

Apa aplikasi dari fungsi hashing?

Fungsi hashing digunakan untuk beberapa aplikasi dalam ilmu komputer, misalnya kriptografi dan sidik jari dokumen. Tujuan utama dari fungsi hashing adalah untuk memetakan sejumlah besar input ke output panjang tetap. Dalam kriptografi, hashing digunakan untuk memastikan bahwa pesan atau dokumen tidak dirusak. Jika dokumen atau pesan diubah dengan cara apa pun (bahkan satu karakter), nilai hash juga diubah. Oleh karena itu hampir tidak mungkin untuk membuat dokumen atau pesan dengan nilai hash yang diberikan.

Apa teknik resolusi tabrakan dalam hashing?

Teknik resolusi tabrakan dalam hashing digunakan untuk menyelesaikan tabrakan dalam hashing. Teknik resolusi tabrakan dapat berupa rantai atau pengalamatan terbuka. Dalam chaining, kami mempertahankan elemen lama di tempatnya dan menyisipkan elemen baru di ruang berikutnya yang tersedia. Ini adalah metode sederhana resolusi tabrakan tetapi memiliki kelemahan kinerja yang buruk. Dalam pengalamatan terbuka, kami mengganti elemen lama dengan elemen baru dan menandai elemen lama sebagai tabrakan.