1. Hashing dan Hash Table
Hashing adalah suatu teknik yang digunakan untuk
menyimpan dan menerima suatu keys dengan cepat. Dalam hashing, sebuah string
karakter berubah menjadi suatu value atau key yang lebih pendek yang
mewakili string itu sendiri. Hashing digunakan untuk mengindeks dan mengambil
item dalam database karena metode tersebut dapat lebih cepat menemukan item
dengan menggunakan hashed key yang lebih pendek daripada menemukannya
menggunakan value asli. Hashing juga dapat didefinisikan sebagai konsep
mendistribusikan key dalam array yang disebut tabel hash menggunakan
fungsi yang telah ditentukan yang disebut fungsi hash.
Hashing menggunakan suatu tabel yang disebut hash
table. Hash table adalah suatu tabel (array) tempat kita menyimpan string
asli. Indeks dari tabel tersebut adalah key hash, sedangkan valuenya
adalah string asli. Ukuran hash table biasanya terdiri dari beberapa
urutan yang besarnya lebih kecil dari jumlah total string yang ada, sehingga
beberapa string mungkin memiliki hashed key yang sama. Contoh: terdapat
267 (8.031.810.176) string dengan panjang 7 karakter yang terdiri
dari huruf kecil saja.
Misalkan kita ingin menyimpan 5 string: ambon, goa,
exponen, delta, buaya ke hash table dengan ukuran 26. Fungsi hash yang
akan digunakan adalah “mengubah huruf pertama dari setiap string ke dalam sebuah
angka dari 0-25. (a = 0, b = 1, .... z = 25).
Tabel tersebut merupakan hash table dari string-string
tersebut yang disimpan menurut huruf pertamanya.
ambon disimpan di str[0] karena a = 0;
buaya disimpan di str[1] karena b = 1;
delta disimpan di str[3] karena d = 3, dst.
Beberapa method yang digunakan untuk membangun fungsi
has:
- Mid-square
- Division (paling
sering digunakan)
- Folding
- Digit extraction
- Rotating hash
Kita akan
membahas metode division/pembagian saja.
Division à membagi string/identifier dengan menggunakan operator
modulus dan merupakan metode hashing paling mudah.
Misalkan ada
suatu tabel untuk menyimpan string. Fungsi hash yang sangat sederhana adalah
menambahkan nilai ASCII dari semua karakter dalam string dan mengambil sisa
bagi ukuran tabel, misalnya 10.
Contoh:
Angka yang
akan disimpan adalah: 35, 84, 22, 93, 98.
h(z) = z
mod 10;
h(35) = 5
h(84) = 4
h(22) = 2
h(93) = 3
h(98) = 8
Dalam implementasi, hash table merupakan salah
satu komponen penting dalam blockchain untuk menjaga konsistensi data dan
memastikan tidak ada perubahan data yang terjadi. Penggunaan
blockchainoleh banyak orang
sekaligus menuntut penggunaan fungsi hashdengan performa yang handal. Fungsi
hash Keccak dan BLAKE2 merupakan fungsi hash yang relatif baru
dan dapat digunakan
dalam teknologi blockchain.
Algoritma hash digunakan dalam blockchain
untuk memastikan data yang dituliskan valid, sehingga perubahan data sepihak
akan sulit dilakukan. Terutama jika blockchain diimplementasikan
pada sistem terdistribusi dengan konsensus tertentu. Setiap perubahan data pada
suatu blok akan mengakibatkan berbedanya hasil hash,
sehingga blok-blok selanjutnya menjadi tidak valid. Oleh karena itu, untuk
melakukan perubahan sepihak dibutuhkan usaha dan waktu yang lama.
2. Binary Tree dan Tree
Tree
adalah struktur data non-linear yang mewakili hubungan hierarkis di antara
objek data. Beberapa hubungan dalam tree dapat diamati dalam struktur direktori
atau hierarki organisasi. Node pada tree tidak perlu disimpan secara berdekatan
dan dapat disimpan di mana saja dan dihubungkan oleh pointer.
Tree memiliki elemen-elemen:
- Node
- Node paling atas disebut root
- Node yang tidak memiliki children (anak) disebut leaf (daun)
- Node yang memiliki parent yang sama disebut sibling
- Degree (tingkat) dari suatu node merupakan total subtree dari node
- Height/depth merupakan degree maximum dari node dalam tree
- Jika terdapat suatu garis yang menghubungkan p ke q, maka p disebut ancestor (leluhur) dari q, dan q merupakan descendant (keturunan) dari p.
Graf diatas merupakan contoh binary tree yang memiliki
9 node, dimana akar dari tree tersebut memiliki nilai 18. Daun-daunya adalah 9,
12, 10, 23.
No comments:
Post a Comment