CA01-003


Hashing Table and Binary Tree
 Hashing adalah pengubahan dari sebuah string of characters ke sebuah ‘kunci’ yang mewakili string awal. Hashing dilakukan untuk memberikan index dan mengambil item yang ada di suatu database karena pencarian akan lebih cepat melalui hash ‘key’ nya yang sudah disingkat, dibandingkan mencari secara keseluruhan.
            Hashing juga biasa digunakan untuk mengencrypt sebuah data. Hash key yang dibentuk biasanya berdasarkan suatu hitungan matematika. Saqlah satu contohnya adalah dengan message. Dari message yang akan dikirim, akan dibuat sebuah hash, dan juga enkripsi untuk pesan itu sendiri. Pesan yang telah dienkripsi dan hash yang telah dibuat akan diterima di end yang lain. Setetalh diterima, maka receiver akan mendecrypt hash dan pesan tersebut. Setelah itu, receiver akan mengenerate hash sesuai dengan pesan yang didecrypt. Jika hash yang di generate receiver sama dengan hash dari sender, maka keduanya akan tersambung.
            Hash table adalah sebuah array/data structure yang menyimpan isi asli dari data tersebut, index table tersebut adalah hash key dari data tersebut, dan value nya adalah data asli yang membuat hash key.
            Hash Function adalah function untuk memetakan data dari beragam ukuran ke sebuah value yang berukuran sama, biasanya berupa integer. Value yang akan dikembalikan dari function tersebut adalah hash key.
            Dalam data structure, ada beberapa hash function yang sering digunakan.
1.      Division Method
Hash key dibuat melalui pembagian modulus dari data tersebut. Function memilike bentuk sebagai berikut:

H(a) = a %(mod) i
H(a) adalah hash key yang dihasilkan dari a. adalah data original yang telah diubah ke dalam angka, i adalah pembaginya. i disini biasanya memiliki sesuatu yang pasti, misalnya angka prima, ukuran dari hash table, ukuran memory yang digunakan, dll.
Dimisalkan ada data berupa 12,90.34.56 dan pembaginya adalah ukuran tablenya, dimisalkan 10. Maka hash key yang akan dibentuk adalah:
            Untuk 12, 12%10 = 2
            Untuk 90, 90%10 = 0
Untuk 34, 34%10 = 4
            Untuk 56, 56%10 = 6
Maka dari itu, 12 ada di indeks 2, 90 ada di indeks 0, 34 ada di indeks 4, dan 56 ada di indeks 6.
             


2.      Mid -Square Method

Hash key dibuat dengan mengubah type data yang ingin disimpan ke bentuk integer, lalu hasilnya dipangkat dua. Setelah dipangkat, diambil nilai tengah. Dimisalkan ada sebuah data dengan nilai integer 25 dalam kelompok data yang berisi 10. Maka 25^2 adalah 625. Dari situ, 2 diambil menjadi hash key/indeksnya. Maka dari itu:

h(25) = 2

3.      Folding

Hash key dibuat dengan membagi ke beberapa bagian integer tersebut. Setelah dilipat menjadi bagian yang ditentukan, hasil lipatan tersebut ditambah. jika hasil penambahan tersebut lebih besar dari banyaknya kelompok data, maka angka di depan tidak dimasukkan, sampai hasilnya lebih kecil dari jumlah kelompok data tersebut. Dimisalkan integer-nya adalah 1234567 dalam sebuah kelompok data berjumlah 100, dan akan dipecah menjadi 3 bagian:
           
            Maka hasil fold dari 1234567 adalah: 123, 456, 7
            Angka-angka tersebut dijumlahkan, yang hasilnya :586
            Maka hash key yang dihasilkan adalah 86 (5 tidak dihiraukan karena melebihi jumlah data)
            Maka : h(1234567) = 86

4.      Digit Extraction
Hash key dibuat dari digit integer yang sudah ditentukan. Dimisalkan integer-nya adalah 1732. Hash key yang dihasilkan ada diambil dari digit ke-2, ke-4, dan ke-6. Maka:

H(173259)= 729

5.      Rotating Hash
Hash key dibuat dari hasil untuk hash key lain. Kemudian, anngka dari hasil tersebut akan digeser digit-nya sesuai dengan keinginan. Misalkan diambil dari digit extraction di atas dan digeser 2 kali.
            h(173259) = 729.
            Maka h(173259) = 297
            Tentunya ada kemungkinan hash key yang dihasilkan memiliki nilai yang sama. Misalkan menggunakan digit extraction dengan digit ke-4 dan ke-3. Jika ada 2 integer yaitu 2812 dan 7512, keduanya memiliki hash key yang sama, yaitu 21. Hal ini dinamakan tabrakan/collision.
            Maka dari itu, hash function yang baik harus memiliki ciri-ciri sebagai berikut:
1.      Hash key yang dihasilkan dari hash values yang mirip memberikan hasil yang berbeda
2.      Hash function tersebut mudah dimengerti dan mudah untuk dicompute
3.      Hash key yang dihasilkan harus seragam dalam sebuah array/linked list
4.      Hash function yang baik seharusnya menggunakan semua input data

Namun, jika collision terjadi, ada beberapa method untuk menangani collision:
1.       Linear Probing

Linear probing adalah menggeser hash key yang sama ke indeks kosong yang tersedia. Maka, jika diambil dengan permasalahan di atas:

h(2812) = 21

h(7512) = 22

Linear Probing memiliki kerugian untuk search complexity. Jika ada integer 2812,3812,3412,2312,3612,9812 , semuanya memiliki hash key yang sama, yaitu 21, dalam sebuah kelompok data berjumlah 100, dan semuanya terletak di tempat yang berbeda-beda. Maka ketika dilakukan search untuk 9812, harus dilakukan iterasi dari 2312, dan bergeser astu langkah terus sampai menemukan 9812.
                                   
2.       Quadratic Probing

Quadratic Probing memiliki prinsip yang sama, tetapi dengan mengkalikan hash key tersebut dengan pangka yang dimulai dari angka 1, yang kemudian akan di modulus dengan jumlah data.
Formula kalkulasinya adalah sebagai berikut:

H(key)=(H(key)+x*x)%Ukuran data

Misalkan diambil data 2812,3812,3412,2312,3612,9812 yang memiliki jumlah data 20.  Semuanya memiliki hash key 21 dari digit extraction.


                Maka h(2312) = (21+1*1)%20 = 1
                Maka h(2812) = (21+2*2)%20 = 5
                Maka h(3412) = (21+3*3)%20 = 10
                Maka h(3612) = (21+4*4)%20 = 17
                Maka h(3812) = (21+5*5)%20 = 6
                9812 tidak memiliki indeks karena (21+6*6)%20 adalaha= 17, yaitu sama dengan hash key 3612. Maka dari itu, Quadratic Probing memiliki beberapa syarat, yaitu:
1.       Tabel data harus berjumlah bilangan prima.
2.       Table data tidak boleh lebih penuh dari setengah kapasitasnya.

                3. Double Hashing           
                Double Hashing adalah menggunakan hash function yang lain, jika terjadi collision dalam fungsi hash yang pertama. Namun, ada beberapa syarat yang harus dipenuhi hash function sekunder. Syarat tersebut adalah:
1.                   Tidak  boleh memeriksa ke indeks 0
2.                   Indeks tersebut sudah dibentuk dan kosong

                4. Chaining
                Chaining adalah menjadikan data yang memiliki hash key yang sama ke sebuah linked list. Jika diambil data 2812,3812,3412,2312,3612,9812 yang memiliki jumlah data 20.  Semuanya memiliki hash key 21 dari digit extraction. Maka, integer tersebut akan dihubungkan menjadi satu linked list. Sehingga ketika dilakukan search dilakukan, hanya perlu dilakukan penggeseran dari integer yang memiliki hash key yang sama.
Konsep Hashing digunakan dalam Cryptocurrency. Hashing yang digunakan dalam Crypto adalah sebagai suatu ‘puzzle’ yang harus diselesaikan untuk mendapatkan akses ke block yang disimpan. Blok ini yang akan dikumpulkan dan disambungkan ke blockchain. Blok-blok tersebut memiliki tingkat enkripsi/hash yang berbeda-beda.
Binary Tree
                Tree dalam data structures adalah sebuah struktur yang memiliki tingkatan/hierarki. Konsep Tree sudah sering digunakan dalam sehari-hari, seperti dalam organisasi, makalah, jurnal, dan lain-lain. Dalam computer sendiri, tree digunakan dalam sistem folder dan subfolder.
 Beberapa konsep dalam tree adalah:
1.  Node paling atas dinamakan root                      2.  Garis penghubung antara parent dan keturunannya dinamakan edge                                                                       3.  Node yang tidak memiliki keturunan dinamakan leaf                                                                     
4.  Node yang berasal dari parent yang sama dinamakan sibling                                                               
5.  Degree adalah jumlah keturunan dari node utama/root                                                              6. Height/Depth adalaah degree maksimum dari sebuah tree                                                                                                                               
7. Ancestor adalah semua node sebelum node tersebut yang terhubung/ sedabgkan descendant adalah semua node setelah node tersebut
                Binary Tree sendiri adalah sebuah tree yang nodenya paling banyak memiliki 2 keturunan. Nama keturunan ini biasa dinamakan keturunan kiri dan kanan. Sama seperti tree, node yang tidak memiliki keturunan dinamakan leaf.
                Binary Tree memiliki beberapa jenis yaitu:
1.       Perfect Binary Tree, Binary Tree yang di setiap tingkat punya depth yang sama
2.       Complete Binary Tree, Binary Tree yang semua tingkatan terisi, memilik kemungkinan untuk tingkat terakhir tidak terisi semua, dan semua nodenya paling banyak di sisi kiri. Perfect Binary Tree termasuk Complete Binary Tree
3.       Skewed Binary Tree, Binary Tree yang paling banyak memilik satu keturunan di tiap node-nya.
4.       Balanced Binary Tree, Binary Tree yang memilik depth yang sama

Beberapa property dari Binary tree adalah:
1.       Node paling banyak di tingkat x adalah 2x
2.       Jumlah node maksumym yang dimiliki binary tree dengan height h adalah 2h+1-1
3.       Height maksimum dari sebuah binary tree dengan jumlah node n adalah n-1
4.       Height minimu dari sebuah binary tree dengan jumlah node n adalah 2log(n)
Binary Tree dapat diimplementasikan dengan array, maupun dengan linked list. Struktur dari binary tree adalah sebagai berikut:
                struct node {
                int data;
                struct node *left;
                struct node *right;
                struct node *parent;
};
struct node *root = NULL;
Konsep Binary Tree digunakan dalam infix, prefix, dan postfix. Konsep tersebut dinamakan Expression Tree.
Prefix    : *+ab/-cde
Postfix : ab+cd-e/*
Infix       : (a+b)*((c-d)/e)
















Binary Tree juga memiliki variasi lain. Binary tree ini memiliki NULL pointer di setiap nodenya, yaitu Threaded Binary Tree



Threaded binary tree memiliki 2 jenis berdasarkan arah threading dari pointer node tersebut adalah:
1.       One-way Threading Binary Tree, dimana node sebelumnya hanya dapat ditunjuk oleh salah satu mode keturunannya, jika ada 2 node.


2.       Two-way Threading Binary tree, dimana node sebelumnya dapat ditunjuk dua node keturunannya.




Komentar

Posting Komentar

Postingan populer dari blog ini

CA01-011 Heap & Tries

Gambar
Max Heap : pohon yang parentnya selalu lebih besar dari anaknya Min Heap : pohon yang parentnya selalu lebih kecil dari anaknya Min-Max Heap : Pohon yang selang-seling parentnya Heap biasanya menggunakan array, tapi bisa menggunakan linked list juga. Dimulai dari 1 untuk memudahkan mencari node. Insert dalam heap dilakukan dengan seperti berikut: 1.        Insert node seperti dalam Binary Tree 2.        cek apakah angka tersebut memenuhi syarat (lebih besar dari parentnya untuk min heap, lebih kecil dari parentnya untuk max heap) 3.        Jika salah, maka angka tersebut ditukar dengan parentnya 4.        lakukan step 2 dan 3 sampai node tersebut memenuhi syaratnya, atau node tersebut berada di posisi root aksi yang dilakukan tersebut disebut Heapify Up untuk delete dilakukan sebagai berikut: 1.        hap...
Baca selengkapnya

CA01-006

Linked List Butuh malloc untuk alokasi value ke memory yang berbeda Pointer next dibuat untuk menyimpan data setelahnya, struct data untuk recursive Indikator posisi awal dengan if head==NULL Pergeseran dilakukan dengan next->curr Tail->Next==NULL Sebagai penanda akhir list Next adalah alamat curr setelah bergeser Menghapus/pop dengan menggeser curr/tail ke alamat sebelumnya Double Linked List Double linked list adalah single linked list yang memiliki 2 arah. Tidak seperti single linked list yang hanya bergeser dari head ke tail, double linked list bisa begeser ke arah sebaliknya Keuntungan Double linked List 1.         Implementasinya tidak jauh berbeda dari Single linksed list 2.         Mampu bergeser dua arah 3.         Deletion lebih mudah dilakukan, karena tidak perlu menggunakan pointer node dan pointer node sebelum yang akan...
Baca selengkapnya

CA01-004

BST/ Binary Search Tree BST adalah sebuah cara untuk mengurutkan data berdasarkan Hieerarki. Karena Binary, masing-masing node hanya punya boleh keturunan maksimum dua. Dalam penyusunannya, data yang lebih besar ada di kanan dan data yang lebih kecil ada di kiri, bisa juga sebaliknya. Insert: insert dalam BST setelah insert pertama adalah ·          Jika node yang dimasukkan lebih besar dari node atasnya, maka keturunannya akan ada di bawah dan diletakkan di sisi kanan node tersebut. ·          Jika node yang dimasukkan lebih kecil dari node atasnya, maka keturunannya aka nada di bawah dan diletakkan di sisi kiri node tersebut Pop : Pop dalam BST memiliki aturan sebagai berikut: ·          Jika pop dilakukan pada leaf/ node yang tidak memiliki keturunan maka node tersebut akan langsung di pop ·          Jika pop...
Baca selengkapnya