Hashing Pengertian hasing adalah suatu teknik yang dipakai untuk menyimpan dan mengambul kunci dengan cepat. Dalam hashing, string karakter diubah menjadi nilai yang panjang dan biasanya lebih pendek atau kunci yang mewakili string asli. Hashing juga dapat diartikan sebagai sebuah konsep mendistribusikan kunci dalam array yang di sebut tabel hash menggunakan fungsi yang telah di tentukan yang disebut sebagai hash function Hash Table Pengertian hash table adalah suatu tabel tempat kita menyimpan sstring asli. Indeks tabel adalah hashed key sementara nilainya adalah string asli Ukuran tabel hash biasanya terdiri dari beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hashed key yang sama Contoh kita ingin menyimpan 5 string: define, float, exp, char, atan ke tabel hash dengan ukuran 26. hash function yang akan kita gunakan adalah "mengubah karakter pertama setiap string menjadi angka antara 0..25 ” (a akan menjadi 0, b akan menjadi 1, c akan menjadi 2, ..., z akan menjadi 25).
Hash Function
Pada hash function terdapat beberapa cara untuk mengaitkan string menjadi key. Berikut adalah beberapa cara untuk membangun hash function
* Mid-square
Kuadratkan string kemudian gunakan jumlah bit yang sesuai dari tengah kotak untuk mendapatkan hash-key.
Jika key nya adalah string, akan di konversi ke angka
Langkah langkah:
1. kuadratkan nilai pada sebuah key.
2. ekstrak ambil nilai tengah sejumlah r bits dari hasil kuadrat nilai pada step pertama.
Contoh
nilai = 3121
hasil kuadrat = 3121 * 3121 = 9740641
nilai tengah = 9740641
* Division (most common)
Membagi suatu string dengan memakai operator modulus
Ini adalah metode hashing integer x yang paling sederhana
Function: h(z) = z mod M
z = key
M = nilai yang digunakan untuk membagi key, biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan.
Contoh
"COBB" akan disimpan di lokasi
(64 + 3 + 64 + 15 + 64 + 2 + 64 + 2)% 97 = 88
* Folding
Metode folding berfungsi dalam dua langkah :
1. Bagilah nilai key menjadi sejumlah bagian di mana disetiap bagian memiliki jumlah digit yang sama kecuali bagian terakhir yang mungkin memiliki angka lebih sedikit daripada bagian lain
2. Tambahkan bagian individual. Yaitu memperoleh jumlah part1 + part2 + ... + bagian n. Nilai hash yang dihasilkan dengan mengabaikan carry terakhir, jika ada.
Contoh
Nilai = 34567
Parts = 34,56, dan 7
Sum = 34 + 56 + 7 = 97
Hash value = 97
* Digit Extraction
Digit extraction adalah digit yang ditentukan sebelumnya dari nomor yang diberikan yang dianggap sebagai hash address
Contoh
X = 14.568
Jika kita mengekstrak digit 1,3, dan 5, kita akan mendapatkan hash code yaitu : 158
* Rotating Hash
Gunakan metode hash (seperti metode pembagian atau mid-square)
Lakukan rotasi
Contoh
Diberikan hash address = 20021
Hasil rotasi = 12002
Impelemntasi Hash Table pada Block Chain
Implementasi hash table pada block chain terdapat pada kriptografi hash, yang berfungsi sebagai penghubung block chain
Binary Tree
Tree
Pengertian tree adalah suatu data structure non linear yang menggambarkan hubungan antara suatu data dengan objek.
Node di tree dapat disimpan dimana saja dan terhubung dengan pointer
Konsep tree :
1. Node yang paling atas di sebut root
2. Gari yang menghubungkan parent dan child disebut edge
3. Node yang tidak punya child disebut leaf
4. Node yang mempunyai parent yang sama disebut sibling
5. Total sub tree pada sebuah node disebut degree
6. Maksimum degree pada sebuah node disebut height / depth
7. Ancestor dan Descendant
Comments