Hashing and Hash Tables, Trees & Binary Tree
HASHING
merupakan metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi recordyang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hashfunction) dan array yang digunakan disebut tabel hash (hash table). Hash tablemenggunakan struktur data array asosiatif yang mengasosiasikan recorddengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.
Function-function yang terdapat pada hash :
TREE & BINARY TREE
Tree merupakan struktur data non-linear yang mewakili hubungan hierarkis di antara objek data, dan dode di tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.
Sedangkan, Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary tree boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan. Binary tree dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat.
Jenis-jenis Binary tree :
Kunjungan pada Binary tree (Prefix, Infix, Postfix)
1. Kunjungan secara preorder (Depth First Order) -> Prefix, mempunyai urutan :
a. Cetak isi simpul yang dikunjungi ( simpul akar ),
b. Kunjungi cabang kiri,
c. Kunjungi cabang kanan.
2. Kunjungan secara inorder ( symetric order) -> Infix, mempunyai urutan :
a. Kunjungi cabang kiri,
b. Cetak isi simpul yang dikunjungi (simpul akar),
c. Kunjungi cabang kanan.
merupakan metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi recordyang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hashfunction) dan array yang digunakan disebut tabel hash (hash table). Hash tablemenggunakan struktur data array asosiatif yang mengasosiasikan recorddengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut.
Function-function yang terdapat pada hash :
- Mid-square
merupakan teknik hashing yang di mana kunci unik dihasilkan. Dalam teknik ini, nilai benih diambil dan dikuadratkan. Kemudian, beberapa digit dari tengah diekstraksi. Angka-angka yang diekstrak ini membentuk angka yang diambil sebagai benih baru. Teknik ini dapat menghasilkan kunci dengan keacakan tinggi jika nilai benih yang cukup besar diambil. Namun, itu memiliki batasan.
contoh : key=4765, dikuadratkan = 22705225, mid= 7052. - DivisionInti dari fungsi ini adalah membagi dan sisa pembagian nilai key field dijadikan alamat relatifnya. Tujuan dari fungsi ini adalah agar alamat yang akan digunakan bisa berbeda sekecil mungkin (menghemat memori) dan menghindari benturan yang bakal terjadi.Ada juga perhitungan faktor muat (load factor) yaitu jika kita memiliki record yang akan disimpan ke dalam memori, maka setidaknya kita menyediakan memori yang kapasitasnya lebih dari jumlah record tersebut.
contoh : ukuran tabel= 11, nilai 68 -> (68 mod 11) + 1 = 2 + 1 = 3 ; simpan 68 dilokasi 3. - Folding
Teknik ini digunakan untuk mendapatkan alamat relatif, nilai key dibagi menjadi beberapa bagian, setiap bagian (kecuali bagian terakhir) mempunyai jumlah digit yang sama dengan alamat relatif. Bagian-bagian ini kemudian dilipat (seperti kertas) dan dijumlah. Hasilnya, digit yang tertinggi dibuang (bila diperlukan).
contoh : 123456 -> 123+456 = 777; simpan 123456 dilokasi 777 - Digit Extraction
Teknik ini digunakan untuk memilih digit untuk diestrak dari key, yang akan digunakan sebagi alamat.
Contoh 14568 -> ambil digit ke 1,3,5 -> alamat = 158. - Rotating Hash
Teknik hashing yang membaca nilai asli dari belakang untuk dijadikan sebagai alamatnya.
contoh : 123456 -> alamat = 654321.
Collision
Merupakan peristiwa yang terjadi ketika ada 2 atau lebih kunci yang menghasilkan hash code yang sama (berebut dalam satu sel yang sama).
Merupakan peristiwa yang terjadi ketika ada 2 atau lebih kunci yang menghasilkan hash code yang sama (berebut dalam satu sel yang sama).
cara-cara yang dapat digunakan untuk mengatasi Collision :
Hashing benar-benar mendasar dalam penciptaan teknologi blockchain. Jika seseorang ingin memahami apa itu blockchain, mereka pasti harus mengerti apa artinya hashing. Karena hashing dapat menghasilkan proses perhitungan sebuah data secara konkret dan unik.
contoh salah satu implementasi Hash pada Blockchain adalah SHA256, karena dalam kasus SHA-256 , tidak peduli seberapa besar atau kecil input Anda, output akan selalu memiliki panjang 256-bit tetap. Ini menjadi penting ketika Anda berurusan dengan sejumlah besar data dan transaksi. Jadi pada dasarnya, alih-alih mengingat input data yang bisa jadi besar, Anda bisa mengingat hash dan terus melacak. Sebelum kita melangkah lebih jauh, kita perlu terlebih dahulu melihat berbagai properti fungsi hashing dan bagaimana mereka diimplementasikan di blockchain.4
- Linear Probing
metode yang digunakan untuk mencari sel yang kosong di bawah tempat terjadinya Collision. - Chaining
metode yang membuat rantai pada masing-masing sel, jadi ketika terjadi Collision pada salah satu sel, maka sel tersebut akan ditinggalkan.
contoh salah satu implementasi Hash pada Blockchain adalah SHA256, karena dalam kasus SHA-256 , tidak peduli seberapa besar atau kecil input Anda, output akan selalu memiliki panjang 256-bit tetap. Ini menjadi penting ketika Anda berurusan dengan sejumlah besar data dan transaksi. Jadi pada dasarnya, alih-alih mengingat input data yang bisa jadi besar, Anda bisa mengingat hash dan terus melacak. Sebelum kita melangkah lebih jauh, kita perlu terlebih dahulu melihat berbagai properti fungsi hashing dan bagaimana mereka diimplementasikan di blockchain.4
TREE & BINARY TREE
Tree merupakan struktur data non-linear yang mewakili hubungan hierarkis di antara objek data, dan dode di tree tidak perlu disimpan secara berdekatan dan dapat disimpan di mana saja dan dihubungkan oleh pointer.
Sedangkan, Binary tree adalah suatu tree dengan syarat bahawa tiap node (simpul) hanya boleh memiliki maksimal dua subtree dan kedua subtree tersebut harus terpisah. Tiap node dalam binary tree boleh memiliki paling banyak dua child (anak simpul), secara khusus anaknya dinamakan kiri dan kanan. Binary tree dapat juga disimpan sebagai struktur data implisit dalam array, dan jika pohon tersebut merupakan sebuah pohon biner lengkap, metode ini tidak boros tempat.
Jenis-jenis Binary tree :
- Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
- Complete Binary Tree
Setiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.
- Skewed Binary Tree
Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.
- Similer Binary Tree
Dua pohon yang memiliki struktur yang sama tetapi informasinya berbeda.
- Ekuivalent Binary Tree
Dua pohon yang memiliki struktur dan informasi yang sama.
1. Kunjungan secara preorder (Depth First Order) -> Prefix, mempunyai urutan :
a. Cetak isi simpul yang dikunjungi ( simpul akar ),
b. Kunjungi cabang kiri,
c. Kunjungi cabang kanan.
2. Kunjungan secara inorder ( symetric order) -> Infix, mempunyai urutan :
a. Kunjungi cabang kiri,
b. Cetak isi simpul yang dikunjungi (simpul akar),
c. Kunjungi cabang kanan.
3. Kunjungan secara postorder, mempunyai urutan :
a. Kunjungi cabang kiri,
b. Kunjungi cabang kanan,
c. Cetak isi simpul yang dikunjungi ( simpul akar ).
a. Kunjungi cabang kiri,
b. Kunjungi cabang kanan,
c. Cetak isi simpul yang dikunjungi ( simpul akar ).
Sumber : https://arisistemberkas.blogspot.com/2018/10/teknik-hashing.html
https://www.ilmuhacking.com/web-security/hashtable-collision-dos/
https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
http://firmanatduhri.blogspot.com/2015/03/pengertian-tree-dalam-bahasa-pemrograman.html
PPT Bimay
https://www.ilmuhacking.com/web-security/hashtable-collision-dos/
https://selembardigital.com/apa-itu-hashing-di-bawah-tudung-blockchain/
http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html
http://firmanatduhri.blogspot.com/2015/03/pengertian-tree-dalam-bahasa-pemrograman.html
PPT Bimay
Comments
Post a Comment