Langsung ke konten utama

Hashing & Hash Tables, Trees & Binary Trees

Halo ges!! Pada post kali ini untuk pertemuan kelima, kita akan membahas tentang Hashing & Hash Tables, Trees & Binary Trees yang merupakan topik dari GSLC pada hari ini. Sebelumnya jangan lupa untuk jaga diri kita masing - masing ya. Soalnya, semakin banyak korban dari wabah itu sehinga kita semua malah harus belajar sendiri di rumah deh. Nah, tanpa basa basi mari kita bahas topik pada pertemuan kelima ini satu persatu.

Hashing

Hashing adalah sebuah fungsi yang dapat mengubah sebuah string menjadi bentuk yang lebih simpel yang dapat merepresentasi string tersebut. Contohnya adalah ketika kita menyimpan nomor telepon. Nomor telepon itu kan panjang, sekitar 12 digit. Nah dengan hashing, kita hanya perlu mengambil 3 angka belakang. Kenapa tidak 3 angka depannya aja? Karena jika kita mengambil 3 digit terdepan, pasti banyak nomor yang sama ketika nomor itu dihash. 

Hash Tables

Hash table adalah sebuah tabel dalam bentuk array yang menyimpan string. Index dari tabel itu adalah data yang dihash dan nilainya merupakan string itu sendiri. Untuk lebih jelasnya, mari kita lihat ilustrasi dibawah.

Ilustrasi Hashing dari geeksforgeeks

Nah, ilustrasi tersebut menjelaskan kita tentang hash table yang dibuat berdasarkan operasi x%10. Kita ambil angka pertama yaitu 11. 11%10 adalah 1, sehingga dalam hash table, index ke 1 dimasukkan angka 11. Begitu juga berlaku terhadap 12 yang dimodulus 10. Hasilnya kan 2, sehingga pada indeks ke 2 kita masukkan value 12.

Jika dibuat tabelnya, lebih jelas seperti ini

Contoh lainnya adalah ketika kita ingin membuat hash table dari 6 String yaitu: Dem, Mezquito, Budi, Chandra, Zidan. Tabelnya akan kita buat dengan ukuran 26 maksimalnya.

Pembuatan Hash tablenya adalah seperti diatas

Fungsi dari Hash

Hash mempunyai beberapa fungsi yaitu:
Mid-square, Division (yang biasa dipakai), Folding, Digit Extraction, dan Rotating Hash.

Mid-Square

Mid-square merupakan fungsi yang mengambil nilai string dari tengah. Jika keynya merupakan string, string tersebut akan diubah nilainya menjadi angka. Contohnya adalah ketika kita mempunyai key 5010, 5011, 5012, 5013, dan 5015. Kita harus memangkatkan nilai tersebut dan mengambil string ditengahnya.

Tabel dari Mid-Square

Division

Division merupakan fungsi yang membagi nilai dari string dengan operator modulus. Biasanya bentuk dari fungsi ini adalah sebagai berikut.

Fungsi: h(z)  = z mod M
z = keynya
M = nilai yang digunakan untuk memodulus z. Biasanya berupa ukuran dari tabelnya atau ukuran dari memori yang terpakai.

Contoh:
Kita mempunyai Budi, Abah, dan Caca. Kita akan menambahkan masing masing ASCIInya dan memodulusnya dengan ukuran tabelnya. Anggap saja ukurannya adalah 98.
"Budi" akan disimpan pada lokasi (66+117+100+105) % 98 = 14
"Abah" akan disimpan pada lokasi (65+98+97+104) % 98 = 70
"Caca" akan disimpan pada lokasi (96+97+99+97) % 98 = 95

Folding

Folding merupakan fungsi yang memisahkan string lalu menambahkan bagiannya menjadi sebuah hash key.
Contohnya sebagai berikut:

Tabel dari Folding

Digit Extraction

Digit extraction adalah fungsi yang mengambil digit dari angka yang diberikan.
Contoh: 15.987.654
Jika kita menggunakan fungsi digit extraction untuk mengambil digit 1, 3, dan 5, Maka kita akan mendapatkan kode hashnya yaitu 197.

Rotating Hash

Fungsi rotating hash dapat dilakukan ketika kita melakukan fungsi hash apapun. Ketika kita mendapatkan hash codenya, selanjutnya kita akan mengacaknya atau bisa disebut rotation.
Contoh:
Nilai hashnya: 857
Hasil Rotasi: 785

Collision

Ini akan terjadi jika kita mempunyai string yang sama. Misalnya kita akan memasukkan data dari string "Budi", "Caca", "Danang" "Bambang". Untuk masalah ini kita dapat mengatasinya dengan Linear Probing dan Chaining.

Linear Probing

"Budi" dan "Bambang" mempunyai huruf depan yang sama kan, makanya kita akan menaruh Bambang di 1, Caca di 2, Danang di 3, dan Budi di 4. Itu adalah cara Linear Probing bekerja, yaitu menaruh datanya di tempat manapun yang kosong. Tapi cara ini mempunyai kerugian yaitu jika terjadi banyak data yang sama yang menyebabkan collision, waktu untuk mencarinya akan lebih kompleks.

Tabel dengan teknik Linear Probing

Chain

Nah, dengan chain, kita dapat menyimpan data setiap string dalam sebuah rantai atau linked list. Contohnya  Bambang->Budi di 1, Caca di 2, Danang di 3, Bambang di 4.

Tabel dengan teknik Chain

Aplikasi dari Hash Table

Hash table masih digunakan sampai sekarang. Contoh paling gampangnya adalah ketika kita memasukkan email dan password untuk login di BinusMaya. Email dan password kita akan diubah menjadi hash code dan akan dibandingkan dengan hash code yang ada di dalam database BinusMaya. Jika kodenya sesuai dan tabelnya sesuai, maka email dan password berhasil diverifikasi dan kita dapat masuk ke dalam dashboard BinusMaya. Jika email dan password tidak diubah menajadi kode hash, maka akun kita akan lebih rentan untuk diretas orang.

Trees

Trees adalah kumpulan dari satu atau lebih nodus.
Contoh Tree dari BinusMaya

Derajat dari pohon tersebut adalah 3
Derajat C adalah 2
Derajat F adalah 0
Parent dari C adalah A
Parent dari E adalah B
Leluhur dari F dan G adalah C dan A
Tingginya dalah 3
Saudara dari F adalah G

Binary Tree

Binary tree adalah sebuah pohon yang anaknya mempunyai paling banyak 2 anak (atau bisa disebut juga dengan cabang). Biasanya anak atau cabangnya dapat disebut dengan anak kiri dan kana karena hanya berjumlah 2.

Contoh Binary Tree dari geeksforgeeks

Pengaplikasian dari Binary Tree

Contoh paling gampangnya adalah system file dari sebuah komputer.
  /   <-- root
  /      \
...        home
      /          \
   ugrad        course
    /          /    |    \
  ...        cs101 cs112 cs113
System file komputer dari geeksforgeeks

Jika kita menggunakan tree, maka waktu yang diperlukan untuk mencari dan mengakses sebuah key akan lebih cepat dari linked list, namun lebih lambat dari array. Bisa kita katakan bahwa kecepatan dari tree untuk mengakses data adalah rata - rata dari linked list dan array. Kita juga dapat menambah atau menghapus data dengan kecepatan rata - rata dari array dan unordered linked list. Menambah atau menghapus data menggunakan tree lebih cepat dari array tapi lebih lambar dari unordered linked list. Terakhir, tree itu mirip seperti linked list, yaitu tidak mempunyai batas data. Array kan mempunyai batasnya, nah dengan tree kita dapat menyimpan data tanpa takut terbatasi seperti ketika menggunakan sebuah array. Kesimpulannya, gunakanlah tree jika ingin akses data yang tidak terlalu cepat atau lambat dan tanpa ketakutan untuk menggunakannya terus menerus karena tidak dibatasi.

Sumber:

Komentar

Posting Komentar

Postingan populer dari blog ini

How do you get to the top of Mt Coronet in Pokemon Diamond?

Note: If you are going to try to catch Dialga or Palkia (diamond or pearl) make sure you have a bunch of Ultra and Dusk balls!! First, Fly to Hearthome city and head west, Route 208. Enter the cave and once inside, you should go north.When you first enter the cave, you need to head west to the opposite side. Once you reach the west entrance, head north and surf across the pond. Use rock climb to reach the stairs up. In the next room: Go- North, West, South, Upstairs, North, West over bridge, down stairs, up north, stairs,up stairs, cross bridge, down stairs, down stairs, upstairs and in cave door. In the Next room: Up stairs, up stairs Again Next room: up stairs, north, west, south, Out. Now you are outside. Follow the path and use rock climb when you get there. Now don't use rock climb again, instead, head west and through the grass until you reach another cave. Inside, use rock climb, follow the path, down the stairs then east, you're out of the cave. ...
Posting Komentar
Baca selengkapnya

Binary Search Tree

Pengertian Binary Search Tree Binary search tree adalah sebuah metode dari data structure yang mempunyai ciri sebagai berikut: Bagian kiri dari subtree adalah nodus yang mempunyai nilai yang lebih kecil Bagian kanan dari subtree adalah nodus yang mempunyai nilai yang lebih besar Bagian kiri dan kanan dari subtree harus berupa binary search tree juga Mencari Sebuah Angka (searching) Ilustrasi Binary Search Tree dari geeksforgeeks Bisa kita lihat dari contoh diatas, bagian kiri dari binary search tree merupakan nilai yang kecil sedangkan bagian kanannya adalah nilai-nilai yang besar. Kita bisa mengambil contoh angka 7. Ketika angka 7 ingin dicari pada binary search tree diatas, maka dia akan mengecek. Apakah 8 lebih kecil atau besar dari 7? Karena lebih kecil, maka 7 akan dicari di bagian kiri. Kemudian, akan dicek lagi. Apakah 7 lebih kecil daripada 3? Jawabannya adalah tidak, sehingga 7 dicari dibagian kanan. Lalu ketika sampai di 6, karena 7 lebih besar...
Posting Komentar
Baca selengkapnya

Heaps & tries

Heap Minggu lalu kita sudah membahas AVL Tree dan sekarang kita akan membahas Heap & Tries. Heap adalah sebuah struktur data dengan konsep binary tree. Heap mempunyai dua jenis yaitu: Min - heap Max - heap Min - Max heap Heap dapat diimplementasikan dengan linked list, namun akan lebih gampang jika menggunakan array. Agar lebih jelas, lebih baik kita lihat gambar berikut ini. Heap dari geeksforgeeks Min - Heap Pada min - heap terdapat aturan agar heap itu dapat dibuat. Aturan tersebut adalah angka atau huruf yang ada di root harus paling kecil daripada anak - anaknya. Hal ini juga berlaku pada subtree lainnya secara rekursif. Jadi, yang diatas harus lebih kecil daripada bawahnya. Insertion Berbeda dengan BST yang mempunyai aturan kiri harus yang kecil dan kanan yang besar, min - heap hanya menghiraukan atasnya. Pada kasus min - heap berarti atasnya harus lebih kecil daripada bawahnya. Agar kita mengerti cara menginsertnya, lihat gambar berikut: Kita ak...
Posting Komentar
Baca selengkapnya