Hashing, Hash Tables, Tree, and Binary Tree
Angelia
2301854492
COMP6048 - CB01
Pada pertemuan ini dilakukan pembelajaran mandiri (GSLC) akibat mewabahnya kasus virus corona.
Pada sesi ini akan dibahas mengenai Hashing dan Hash Tables beserta Tree dan Binary Tree. Setelah membaca materi dari Binus Maya dan beberapa sumber lain, maka berikut ini adalah pembahasan ringkasan dari materi yang telah saya pelajari.
Pengertian Hashing
Jadi, hashing merupakan teknik yang digunakan untuk mengubah string dengan panjang yang asli menjadi lebih pendek.
Teknik hashing ini biasa digunakan untuk mengambil suatu item dari database. Teknik ini dipilih karena item bisa ditemukan lebih cepat dengan menggunakan kunci hash daripada menggunakan nilai asli.
Hashing juga merupakan konsep mendistribusikan kunci dalam array (table hash) menggunakan fungsi hash.
Sumber: https://en.wikipedia.org/wiki/Hash_function
Pengertian Hash Table
Hash table menjadi tempat penyimpanan string sementara.
Index tabel adalah kunci hashnya, kemudian value tabel adalah string aslinya.
Ukuran hash table bisa lebih sedikit dibandingkan jumlah string asli yang ada, karena beberapa string dapat memiliki kunci hash yang sama.
Contoh Konsep Hash
Soal:
Menyimpan 5 string: define, atan, char, float, exp dengan fungsi hash "ubah karakter dari tiap string menjadi angka mulai dari 0...25"
Dari soal tersebut, maka dapat diklasifikasikan:
a) Index tabel adalah angka 0...25
b) Fungsi hash adalah "ubah karakter dari tiap string menjadi angka mulai dari 0...25"
c) Value tabel adalah define, atan, char, float, exp
Maka, dari penjabaran di atas, dapat disesuaikan bahwa
indeks 0 diisi dengan string atan karena awal karakternya 'a'.
indeks 1 kosong karena tidak ada string yang awal karakternya 'b'.
indeks 2 diisi dengan string char karena awal karakternya 'c'.
indeks 3 diisi dengan string define karena awal karakternya 'd'.
indeks 4 diisi dengan string exp karena awal karakternya 'e'.
indeks 5 diisi dengan string float karena awal karakternya 'f'.
dst
Dari, pengelompokkan di atas, maka didapat hash table sebagai berikut:
2301854492
COMP6048 - CB01
Pada pertemuan ini dilakukan pembelajaran mandiri (GSLC) akibat mewabahnya kasus virus corona.
Pada sesi ini akan dibahas mengenai Hashing dan Hash Tables beserta Tree dan Binary Tree. Setelah membaca materi dari Binus Maya dan beberapa sumber lain, maka berikut ini adalah pembahasan ringkasan dari materi yang telah saya pelajari.
PART 1
HASHING DAN HASH TABLES
Pengertian Hashing
Jadi, hashing merupakan teknik yang digunakan untuk mengubah string dengan panjang yang asli menjadi lebih pendek.
Teknik hashing ini biasa digunakan untuk mengambil suatu item dari database. Teknik ini dipilih karena item bisa ditemukan lebih cepat dengan menggunakan kunci hash daripada menggunakan nilai asli.
Hashing juga merupakan konsep mendistribusikan kunci dalam array (table hash) menggunakan fungsi hash.
Fungsi Hash
Sumber: https://en.wikipedia.org/wiki/Hash_function
Pengertian Hash Table
Hash table menjadi tempat penyimpanan string sementara.
Index tabel adalah kunci hashnya, kemudian value tabel adalah string aslinya.
Ukuran hash table bisa lebih sedikit dibandingkan jumlah string asli yang ada, karena beberapa string dapat memiliki kunci hash yang sama.
Contoh Konsep Hash
Soal:
Menyimpan 5 string: define, atan, char, float, exp dengan fungsi hash "ubah karakter dari tiap string menjadi angka mulai dari 0...25"
Dari soal tersebut, maka dapat diklasifikasikan:
a) Index tabel adalah angka 0...25
b) Fungsi hash adalah "ubah karakter dari tiap string menjadi angka mulai dari 0...25"
c) Value tabel adalah define, atan, char, float, exp
Maka, dari penjabaran di atas, dapat disesuaikan bahwa
indeks 0 diisi dengan string atan karena awal karakternya 'a'.
indeks 1 kosong karena tidak ada string yang awal karakternya 'b'.
indeks 2 diisi dengan string char karena awal karakternya 'c'.
indeks 3 diisi dengan string define karena awal karakternya 'd'.
indeks 4 diisi dengan string exp karena awal karakternya 'e'.
indeks 5 diisi dengan string float karena awal karakternya 'f'.
dst
Dari, pengelompokkan di atas, maka didapat hash table sebagai berikut:
Hash Table
Sumber: PPT Binus Maya
Metode-Metode Fungsi Hash
Ada beberapa metode yang digunakan sebagai fungsi hash, diantaranya:
- Mid-square
Metode ini dilakukan dengan:
1) Memangkatkan value (jika value string, convert jadi angka) dengan pangkat dua
2) Mengambil angka di tengah dari hasil pangkat dua tersebut yang kemudian dikonversi menjadi nilai bit
Contoh:
Valuenya adalah 3121. Maka 3121 akan dipangkatkan dengan dua menjadi 9740641. Dari hasil pangkat dua, diambil angka di tengahnya yaitu 406.
Hasil pangkat dua dari 3121 dalam bentuk bit adalah 1001010-0101000010-1100001. Nilai 0101000010 (angka tengah dari hasil pangkat dua 3121) akan diambil menjadi key hashnya.
- Division
Metode ini menggunakan modulus.
Rumusnya bisa dengan menggunakan angka 64 ditambah nilai urutan huruf (1...26)
Jumlah angka yang didapat akan dimodulus dengan 97.
Contohnya:
"COBB" akan disimpan di index = ((64+3) + (64+15) + (64+2) + (64+2)) % 97 = 88
Maka value "COBB" akan disimpan di index h[88].
- Folding
Metode ini menggunakan konsep 'melipat' yaitu dengan memecah value menjadi beberapa bagian yang masing-masing memiliki 2 digit yang kemudian akan dijumlahkan kemudian 2 angka terakhir dari hasil penjumlahan digunakan sebagai indeks hash.
Contoh:
a) 34567
dipecah per 2 digit menjadi: 34, 56, dan 7
kemudian dijumlahkan: 34 + 56 + 7 = 97
maka indeks hash untuk menyimpan value 34567 adalah h[97].
b) 5678
dipecah per 2 digit: 56 dan 78
dijumlahkan: 56 + 78 = 134
diambil 2 angka terakhir: 34
maka indeks hash untuk menyimpan value 5678 adalah h[34].
- Digit Extraction
Metode ini mengambil value dari digit angka tertentu untuk dijadikan kunci hash.
Contoh:
Nilai 14568
akan diambil value dari digit yang ganjil: digit ke-1,3,5 -> 158
maka indeks hash untuk menyimpan value 14568 adalah h[138].
- Rotating Hash
Metode ini merupakan metode tambahan setelah melakukan metode yang lain (folding, mid-square, division, dsb).
Setelah mendapatkan kunci hash dari fungsi hash sebelumnya, maka akan dilakukan rotasi.
Contoh:
Alamat hash sebelumnya -> Alamat hash setelah dirotasi
600101 -> 160010
600102 -> 260010
600103 -> 360010
(Note: value digit paling terakhir, pindah posisi ke paling depan)
Collision
Collision adalah kondisi dimana ada 2 value yang memiliki kunci hash/indeks hash yang sama.
Contoh lanjutan dari 5 string sebelumnya (ada tambahan):
define, atan, char, float, exp, ceil, acos, floor
Pembahasan:
Jika menggunakan fungsi hash "ubah karakter dari tiap string menjadi angka mulai dari 0...25", maka ada beberapa value yang memiliki kunci hash yang sama.
(atan dan acos berada di h[0], char dan ceil berada di h[2], float dan floor berada di h[5]).
Peristiwa ini disebut Collision.
Ada beberapa cara mengatasi Collision:
- Linear Probing
Metode ini akan mencari slot kosong selanjutnya kemudian meletakkan string tersebut di situ.
Contoh soal sebelumnya:
#Jika disesuaikan dengan soal sekarang (sebelum dilakukan Linear Probing) maka:
h[0] = atan, acos
h[1] = null
h[2] = char, ceil
h[3] = define
h[4] = exp
h[5] = float, floor
Setelah ditambahkan beberapa value string di soal baru (acos, ceil, dan floor) maka ada beberapa value yang berada di indeks yang sama.
Dengan menggunakan 'Linear Probing', maka value selanjutnya yang berada di indeks yang sama akan diletakkan pada slot selanjutnya yang kosong, sehingga menjadi:
Kelemahan: Sulit dilakukan pencarian bila terdapat banyak Collision, karena jika ingin mencari ceil mulai dari indeks ke-2 akan lanjut iterasi hingga menemukan value ceil (2->3->4->5->6) sebanyak 5 step.
- Chaining
Meletakkan string di slot sebagai sebuah chained list (linked list).
Dalam metode chaining ini, value tetap akan diletakkan pada indeks yang sama, hanya saja dijadikan dalam bentuk linked list. Maka, jika terdapat Collision, kita hanya perlu melakukan iterasi di indeks tersebut saja.
PART 2
TREE DAN BINARY TREE
Pengertian Tree
Tree merupakan struktur data yang tidak linear, sifatnya hierarki (bertingkat), dan mewakili hubungan hierarkis di antara objek data.
Tree adalah kumpulan dari satu atau lebih nodes.
Node di pohon dapat disimpan di mana saja dan dihubungkan oleh pointer.
Konsep Binary Tree
Binary Tree merupakan tree yang memiliki anak cabang maksimal 2 pada tiap nodenya.
Tipe Binary Tree:
- Perfect Binary Tree
Binary Tree yang tiap nodenya ( kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.
- Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap 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.
- Balanced Binary Tree
Merupakan pohon biner di mana tidak ada daun yang lebih jauh dari akar daripada daun lainnya (skema penyeimbangan yang berbeda memungkinkan definisi yang berbeda dari "jauh lebih jauh").
Property Binary Tree
Formula untuk menghitung jumlah node per level: 2^n
Level dimulai dari n = 0.
Maka, jumlah maksimum nodes dari tree dengan height 3 adalah 1+2+4+8 = 15.
Minimum tinggi binary tree dari n nodes adalah 2log(n).
Maksimum tinggi binary tree dari n nodes adalah n - 1. => (skewed binary tree memiliki height tree maksimum).
Implementasi Binary Tree
- Menggunakan Array
Indeks di array mewakili nomor node
Indeks untuk node root adalah 0.
Indeks Anak Kiri adalah 2p + 1 (p adalah indeks parent)
Indeks Anak Kanan adalah 2p+2
Indeks parent adalah (p-1)/2
- Menggunakan Linked List
struct node {
int data;
struct node *left;
struct node *right;
struct node *parent;
};
struct node *root = NULL;
PART 3
IMPLEMENTASI HASHING DALAM BLOCKCHAIN
Berdasarkan pembahasan di atas, maka hashing ini kerap kali digunakan dalam konsep blockchain. Dikenal dengan metode 'Kriptografi' yaitu ilmu yang mempelajari teknik-teknik matematika yang berhubungan dengan aspek keamanan informasi, seperti kerahasiaan data, keabsahan data, integritas data, serta autentikasi data.
Pada prinsipnya, Kriptografi memiliki 4 komponen utama yaitu :
1. Plaintext, yaitu pesan yang dapat dibaca
2. Ciphertext, yaitu pesan acak yang tidak dapat dibaca
3. Key, yaitu kunci untuk melakukan teknik kriptografi
4. Algorithm, yaitu metode untuk melakukan enkrispi dan dekripsi
Kemudian, proses dasar yang umumnya ada pada Kriptografi yaitu:
1. Enkripsi (Encryption), proses menjadikan pesan yang dapat dibaca (plaintext) menjadi pesan acak yang tidak dapat dibaca (ciphertext).
2. Dekripsi (Decryption), proses kebalikan dari enkripsi dimana proses ini akan mengubah ciphertext menjadi plaintext dengan menggunakan algoritma "pembalik" dan key yang sama.
Pada prinsipnya, Kriptografi memiliki 4 komponen utama yaitu :
1. Plaintext, yaitu pesan yang dapat dibaca
2. Ciphertext, yaitu pesan acak yang tidak dapat dibaca
3. Key, yaitu kunci untuk melakukan teknik kriptografi
4. Algorithm, yaitu metode untuk melakukan enkrispi dan dekripsi
Kemudian, proses dasar yang umumnya ada pada Kriptografi yaitu:
1. Enkripsi (Encryption), proses menjadikan pesan yang dapat dibaca (plaintext) menjadi pesan acak yang tidak dapat dibaca (ciphertext).
2. Dekripsi (Decryption), proses kebalikan dari enkripsi dimana proses ini akan mengubah ciphertext menjadi plaintext dengan menggunakan algoritma "pembalik" dan key yang sama.
Kode-kode asing yang sering kita lihat dalam proses encryption dan decryption merupakan salah satu contoh hash. Hash mampu mengubah setiap data yang mengalami perubahan dengan nilai unik sendiri.
Nilai berharga sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik mengakalinya ialah dengan pemberian kode unik.
Ada sejumlah hash yang digunakan saat ini seperti:
- SHA256
Hash ini digunakan pada Bitcoin khusus proses transaksi dan perhitungan nilai Hash.
- RIPEMD160
Hash RIPEMD160 merupakan singkat dari Race Integrity Primitive Evaluation Message Digest. Konsep dari algoritma dari hash ini dikembangkan oleh MD4. Jumlah data transaksi yang dihasilkan lebih kecil dibandingkan SHA256 yaitu hanya 160 bit.
- Monero
Pada Monero, penerapan pada keamanan data menggunakan sejumlah Hash, mulai dari Keccak, Blake, Grostl, JH, dan Skein pada CryptoNote. Konsep dari Monero yang sangat kompleks seakan membuatnya dijuluki sebagai fully anonymous.
Jadi, konsep Hash ini sangat penting dan sering digunakan dalam konsep Blockchain. Teknik Hash ini digunakan untuk melakukan enkripsi terhadap data dengan mengubah value asli dari data menjadi sebuah kode yang unik yang bertujuan untuk menjaga privasi data user dan terhindar dari pencurian data. Konsep ini sering kita dengar seperti dalam penggunaannya di Bitcoin.
Demikian pembahasan dari materi yang saya pelajari. Mohon maaf apabila ada kesalahan dan kekurangan. Terima kasih.
Angelia
2301854492
COMP6048 - CB01
2301854492
COMP6048 - CB01
Referensi:
PPT Binus Maya
Comments
Post a Comment