Mar 27, 20202 min read

Hashing,Hash Tables,Trees and Binary Tree

Hashing

Hashing merupakan tehnik untuk menyimpan dan mengambil kunci dengan cepat.Hashing mengubah panjang input ke string dengan ukuran tetap.Artinya,seberapa banyak panjang input yang diberikan,dapat diubah menjadi array dari string dan angka melalui suatu algoritma.Pesan yang akan di hashing adalah input,algoritma yang akan digunakan untuk hashing disebut hash function dan hasilnya disebut hash value.

Hash Tables

Hash tables adalah suatu table / array dimana tempat menyimpan string yang original.Ukuran hash table biasanya lebih sedikit dari jumlah string yang mungkin sehingga beberapa string memiliki hashed key yang sama.

Hash Function Ada banyak cara untuk mengubah suatu string ke key,yaitu bisa dengan : a).Mid - square : Mengkuadratkan suatu string,lalu gunakan digit tengah sebagai hash key.Seperti contohnya nilai = 3121. Di kuadratkan menjadi 9740641 lalu diambil digit tengah yaitu 406 sebagai hash keynya.

b).Division : Membagi suatu string menggunakan operator modul.Seperti contohnya : "HELLO" akan di masukan di lokasi. c).Folding : Mempartisi string ke beberapa bagian,lalu tambahkan partnya untuk mendapatkan hash keynya.Seperti contohnya 123.Membagi menjadi 1 dan 23 sehingga hash keynya menjadi 24.(anggap lokasi ada 50).Apabila melebihi 50, seperti contohnya 56,biarkan angka awalannya sehingga menjadi 6.

d).Digit Extraction : Digit yang telah ditentukan dari yang diberikan akan dijadikan alamat hash.Seperti contohnya 123456. Apabila mengambil di bagian ke 2 ,ke 3 dan ke 4, akan mendapatkan 234 sehingga hash key nya adalah 234.

e).Rotating Hash : Menggunakan cara hash apapun seperti division atau mid-square.Setelah mendapatkan hash code dari cara hash tersebut,lakukan rotasi.Dimana rotasi dilakukan dengan men-shift kan dikit menjadi alamat hash.Seperti contohnya 123456,dengan rotasi ,akan didapatkan menjadi 654321 sebagai alamat hash yang baru.

Collision : Collision terjadi ketika 2 data yang memiliki hash value yang sama.Untuk itu,terdapat 2 cara untuk menangani collision yaitu dengan cara :

a). Linear Probing

Dilakukan dengan cara mencari slot yang kosong dan memasukan string tersebut disana.

b).Chaining

Memasukan string di slot sebagai linked list.

Contoh Chaining

Binary Tree

Binary tree merupakan tree yang memiliki dua child di setiap nodenya(child kiri & child kanan). Terdapat tipe Binary tree yaitu :

a). Perfect Binary Tree = binary tree yang setiap levelnya memiliki kedalaman yang sama.

b). Complete Binary Tree =binary tree yang setiap levelnya kecuali yang kemungkinan terakhir,terisi dan setiap nodenya paling panjang ke kiri.Perfect Binary Tree termasuk dengan Complete Binary Tree.