Rangkuman Data Structure Week 3

Hashing and Binary Tree

Review Linked List, 10 Maret 2020

Nama: Julian Andhika Diputra

NIM: 2301858023      

HASHING

Hashing adalah sebuah fungsi yang bisa digunakan dalam Data Structure, yang dapat digunakan untuk menggunakan sebuah fungsi khusus yaitu Hash Function. Hash function sendiri digunakan untuk memetakan sebuah nilai dengan key tertentu agar lebih mudah untuk diakses. Dalam Hashing, sebuah string character diubah menjadi string character yang lebih pendek atau sebuah key yang mewakili string awalnya. Ada juga Hash Table yaitu sebuah array dimana kita menyimpan string awalnya. Index table itu adalah keynya sedangkan valuenya adalah string awalnya.

Ada beberapa cara untuk meng-hash sebuah string menjadi key;

1. Mid-Square
2. Division
3. Folding
4. Digit Extraction
5. Rotating Hash

Mid-Square

Mid-Square adalah Teknik hashing dimana key hashing di-generate secara unik. Dalam Teknik ini, sebuah string diambil dan dikuadratkan. Lalu beberapa digit dari tengah diambil, yang nanti akan menjadi sebuah key baru. Teknik ini dapat membuat key dengan keacakan yang tinggi, jika digitnya besar. Jika key itu adalah sebuah string, akan diubah menjadi sebuah nomor.

Step:

1. Kuadratkan value sebuah key
2. Ambil bit tengah dari hasil yang didapatkan di step 1

Division

Division adalah Teknik hashing dimana sebuah string/identifier dibagi menggunakan operator modulus. Teknik ini merupakan Teknik hashing yang paling mudah.

Folding

Folding adalah Teknik hashing dimana sebuah string/identifier dipartisikan menjadi berbagai bagian, lalu kita menambahkan semua part tersebut untuk mendapatkan sebuah hash key.

Step:

1. Bagi value sebuah key menjadi berbagai bagian
2. Tambahkan setiap individual key ( carry terakhir diabaikan )

Digit Extraction

Digit Extraction adalah Teknik hashing dimana sebuah digit yang ditentukan dari nomor yang diberikan akan dijadikan sebagai alamat hash

Contoh:

Bayangkan X=14,568. Jika kita mengambil digit 1,3, dan 5, kita akan mendapatkan kode hash = 158.

Rotating Hash

Rotating Hash adalah salah satu Teknik hashing. Sebelum menggunakan Rotating Hash, kita harus menggunakan hash method yang lain. Setelah mendapatkan Hash code dari hash method yang lain, lakukanlah rotation. Rotation dilakukan dengan mengubah posisi digit untuk mendapatkan hash code/address baru.

Contoh:

Bayangkan hash address = 20021. Setelah dilakukan rotation, akan didapatkan hash address = 12002.

Collision

Apakah yang terjadi jika terjadi tabrakan antara hash-key yang satu dengan hash-key yang lain. Hal ini disebut sebagai Collision. Ada dua cara untuk menangani Collision.

1. Linear Probing :Mencari slot kosong selanjutnya dan menaruh string disana. Linear probing akan mengalami beberapa masalah jika terjadi banyak Collision.    
2. Chaining: Masukkan string di slot sebagai chained list (linked list). Dalam chaining ini, kita menyimpan setiap string dalam sebuah chain. Jika terjadi Collision, kita tingal mengubah chain/linked list tersebut.

BINARY TREE

Binary tree adalah sebuah data structure yang non linear yang merepresentasikan hubungan hirearki antara objek.

• Node dipaling atas disebut root 
• Garis yang menghubungkan sebuah parent dengan child disebut edge
• Node yang tidak memiliki children disebut leaf 
• Node yang memiliki parent yang sama disebut sibling 
• Degree dari sebuah node adalah total sub tree dari node tersebut 
• Height/Depth adalah maximum degree dari sebuah node dalam tree 
• Jika ada sebuah garis yang menghubungi p ke q, maka p disebut sebagai ancestor dari q, dan q adalah descendant dari p. 

Konsep Binary Tree

1. Perfect Binary Tree : Adalah sebuah tree dimana setiap level memiliki depth yang sama
2. Complete Binary Tree : Adalah sebuah tree dimana setiap level, kecuali mungkin yang terakhir, dipenuhi, dan semua node ditaruh dipaling kiri. Perfect binary tree juga disebut sebagai complete binary tree
3. Skewed Binary Tree : Adalah sebuah tree dimana setiap node memiliki satu child
4. Balanced Binary Tree : Adalah sebuah tree dimana tidak ada leaf yang lebih jauh dari root daripada leaf lain.

BLOCKHAIN DAN HASHING

Blockchain adalah salah satu cara melakukan cryptography yang sangatlah popular, terutama dalam bitcoin atau cryptocurrency. Dalam pembayaran cryptocurrency, butuhlah digunakan pengamanan yang kuat. Salah satu fungsi yang digunakan dalam Blockchain adalah hashing.

Setiap block dalam blockchain memiliki ribuan transaksi, dan akan sangatlah tidak efisien ketika ingin menyimpan data dalam setiap block. Oleh karena itu, digunakanlah merkle tree yaitu salah satu implementasi hashing, agar lebih efisien dalam mengetahui apakah pengunaan sebuah transaksi ditaruh di block yang mana. Setiap block yang dibuat selanjutnya, akan mempoint ke hash yang ada sebelumnya.

Sebagai kesimpulan, Blockchain tidak akan ada tanpa adanya hashing. Hashing ada sehingga blockchain tersebut tidak tercorrupt  atau dikompromosikan.