Hash Table and binary tree

Hash and Tree

Hash adalah suatu cara untuk menyimpan data dengan mengubah data menjadi kunci, sehingga kunci tersebut dapat digunakan untuk mengakses data tersebut. Didalam Hash ada 2 objek terpenting yang harus diketahui, yaitu key dan Hash Table. Key adalah kunci dalam hash sedangkan Hash Table adalah tempat penampung data tersebut. Hashing banyak digunakan didalam database dan berbagai macam penyimpanan data sehingga teknik atau cara ini dapat dikembangkan dengan berbagai macam function hash.

Function Hash didalam data structures sangatlah banyak, mari kita lihat satu per satu:

1. Division.

    Jadi division ini adalah teknik hashing dengan cara mengubah data menjadi key sehingga key tersebut tidak boleh lebih besar daripada penampung data. Rumusnya adalah sebagai berikut:

f(x) = x % data_penampung, dimana f(x) adalah key dan kemudian data tersebut akan diletakan sesuai dengan key yang berurutan. contohnya:

Nah jadi bagaimana dengan data yang keynya sama?Di dalam teknik hashing ini disebut sebagai collision dimana data tersebut harus diakalin.

Cara mengakalin collision ini ada 2 cara yaitu Linear Probing dan Chaining:

a. Linear Probing, dengan cara ini kita menggunakan rumus f(x) = [f(x) + h(i)]% size, dimana h(i) = i.

i disini adalah index yaitu 0,1,2,3,..... jadi kalau data pada tampungan key sudah ada maka i akan bertambah. dan akan meletakan data kedalam index setelah key tersebut, akan begitu terus apabila data tampugannya telah diisi.

b. Chaining, cara dengan menggunakan linked list dimana node data yang memiliki key yang sama akan saling bersambungan.

2.Folding

   Cara ini adalah cara melipat key yang sudah didapatkan dari data, contohnya size tampung data adaa 100 dan key adalah 14567,331 ,dan 539123, nah disini kita akan melihat key pertama yaitu 14567.

14 dan 56 dan 7 dipisahkan, lalu 14+56 = 70 lalu ditambah 7 jadi 77, sehingga data diletakan di tampungan data ke-77

331, 33 dan 1 dipisahkan, 33 + 1 = 34,sehingga data diletakan ditampungan data ke-34

539123, dipisahkan menjadi 53,91,23, 53+91 = 144(angka paling belakang dihiraukan apabila melewati size tampungnya), 44 + 23 = 67,sehingga data tersebut diletakan di tampungan data ke -67

3. Digit Extraction

           cara hash dimana kita mengambil key lewat data tersebut. cthnya: 14568, untuk mengabil hash codenya kita mengambil angka ke 1,3 dan 5 sehingga didapatkan hash code, 158.

4. Rotating Hash

  caranya hanya memutar balik key yang diberikan dan menggunakannya mencari hash code.

cthnya 15666, diputar menjadi 66651.

Hash sering di implementasi dalam dunia Blockchain. Kalau bilang Block chain pasti banyak yang kepikir bitcoin bukan? Yah dengan menggunakan Hash akan didapatkan hashcode yang sangat unik dimana tidak ada duanya di dalam bitcoin, sehingga ketika ingin download sesuatu di official web dengan web bajakan, kita dapat mengetahui web bajakan tersebut terdapat virus atau tidak sesuai dengan official web dengan melihatnya melewati hash code. Apabila hash codenya sama dengan yang didapat di official web, maka itu adalah barang yang asli bukan virus dll.

Tree adalah??, tree adalah pohon!!!, yah sedikit bener sih......

Sebetulnya Tree adalah cara ngoding data structure dimana logicnya akan berbetuk seperti pohon dan data yang di insert sudah tersortir. Ini adalah contoh visual dari tree,

jadi konsepnya adalah level 0 di atas gambar ini merupakan root, dimana data paling pertama, sama seperti head hanya saja konsepnya yang dipakai akan berbeda dengan linked list.

Di sini kita akan memainkan root,parent,dan child dimana parent adalah data sebelum data yang sekarang , contohnya seperti B adalah parent dari E. dan E adalah childnya dari B.

Sekarang kita akan lanjut ke Binary Tree.

Binary Tree adalah cara dimana kalian dapat search dengan gampang, karena data telah di sortir pada saat penginputan data dalam tree.

Binary tree memiliki 3 objek yaitu parent,left,right.

Parent adalah data yang paling pertama sesuai aturan sorting dan left adalah data terkecil setelah data itu. Right adalah data yang lebih besar dari pada data itu setelah di iniput.

berikut adalah contohnya:

struct node {

  int data;

  struct node *left;

  struct node *right;

  struct node *parent;

};

struct node *root = NULL;

source berasal dari binus maya, dan https://sadakurapati.wordpress.com/tag/hash-collision/.