Hashing and Hash Tables, Trees & Binary Tree

A. HASHING

     Hashing merupakan metode yang digunakan untuk menyimpan data dalam sebuah array agar dapat menyimpan data, mencari data, menambah data, dan menghapus data dengan cepat. Pengertian hashing adalah transformasi aritmatik sebuah string dari karakter menjadi nilai yang merepresentasikan string aslinya. Dalam hashing, yang dilakukan adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array.

     Hash Function atau Fungsi Hash merupakan fungsi yang mengembalikan nilai atau kunci. Hash Table atau Tabel Hash merupakan array yang digunakan.



B. HASH TABLE

     Hash Table merupakan sebuah struktur data, terdiri atas sebuah tabel dan fungsi. Fungsi pada Hash Table bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

     Kelebihan dari Hash Table adalah waktu mengaksesnya yang cepat, apabila record yang dicari berada pada angka hash lokasi penyimpanannya. Namun, sering kali ditemukan Hash Table yang record-recordnya memiliki angka hash yang sama, sehingga bertabrakan.



C. HASH FUNCTION

     Hash Function yang dilambangkan dengan h(k) bertugas untuk mengubah k (key) menjadi suatu nilai dalam interval [0....X], di mana "X" adalah jumlah maksimum dari record-record yang dapat ditampung dalam tabel. Hash Function dikatakan ideal apabila mudah dihitung dan bersifat random agar dapat menyebarkan semua key. Dengan tersebarnya key, data dapat terdistribusi secara seragam dan bentrokan dapat dicegah. 

     Beberapa macam Hash Function yang dapat digunakan dalam penyimpanan database :

1. Division
      Pada metode ini, jumlah lokasi memori yang tersedia akan dihitung, kemudian digunakan untuk membagi nilai yang asli dan menghasilkan sisa yang merupakan nilai hashnya.
       Rumusnya adalah h(k)=k mod M.
       M adalah jumlah lokasi memori yang tersedia pada array.
    Hash Function tersebut menempatkan record dengan kunci k pada suatu lokasi memori yang beralamat h(k).
     Dalam metode ini, sering dihasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau bisa juga disebut terjadi bentrokan. Maka, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut sebagai kebijakan resolusi bentrokan.

2. Folding
     Pada metode ini, nilai asli dibagi ke dalam beberapa bagian kemudian nilai-nilai tersebut dijumlahkan, lalu beberapa angka terakhir diambil sebagai nilai hashnya.

3. Digit
     Pada metode ini, urutan digit diubah dengan pola tertentu. Contoh, ambil digit ke-3 sampai ke-6 dari nilai aslinya kemudian balikkan urutannya dan gunakan digit yang urutannya terbalik itu sebagai nilai hash.
             


D. COLLISION

     Hash Function bukan merupakan fungsi satu ke satu, yang artinya beberapa record berbeda dapat menghasilkan nilai hash yang sama dan dapat menyebabkan terjadinya bentrokan (Collision). Apabila terjadi Collision, record-record tersebut tidak bisa menempati lokasi yang sama. 

     Ada dua cara umum untuk menangani Collision :

1. Linear Probing
     Dilakukan dengan cara mencari lokasi yang belum terisi, kemudian menambahkan string.

2. Chaining
     Dilakukan dengan cara menambahkan string pada lokasi tertentu sebagai Chained List (Linked List).



E. TREES

     Tree adalah salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hierarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan elemen khusus yang disebut sebagai Root. Node lainnya terbagi menjadi himpunan-himpunan yang saling tak berhubungan satu sama lain, atau disebut Subtree.

     Istilah-istilah dalam Tree :
1. Predecessor : Node yang berada di atas node tertentu.
2. Successor    : Node yang berada di bawah node tertentu.
3. Ancestor : Seluruh node yang terletak sebelum node tertentu dan terletak pada jalur yang sama.
4. Descendant : Seluruh node yang terletak sesudah node tertentu dan terletak pada jalur yang sama.
5. Parent : Predecessor satu level di atas suatu node.
6. Child : Successor satu level di bawah suatu node.
7. Sibling : Node-node yang memiliki parent yang sama dengan suatu node.
8. Subtree : Bagian dari Tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari Tree tersebut.
9. Size : Banyaknya node dalam suatu Tree.
10. Height : Banyaknya tingkatan/level dalam suatu Tree.
11. Root : Satu-satunya node khusus dalam Tree yang tak punya predecessor.
12. Leaf : Node-node dalam Tree yang tak memiliki successor.
13. Degree : Banyaknya child yang dimiliki suatu node.



F. BINARY TREE

     Binary Tree adalah Tree dengan syarat bahwa setiap node hanya boleh memiliki maksimal dua Subtree dan kedua Subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, setiap node dalam Binary Tree hanya boleh memiliki paling banyak dua Child.

     Kelebihan struktur Binary Tree :
1. Mudah dalam penyusunan algoritma sorting.
2. Searching data relatif cepat.
3. Fleksibel dalam penambahan dan penghapusan data.

     Jenis-jenis Binary Tree :
1. Perfect Binary Tree : sebuah Binary Tree yang setiap levelnya memiliki kedalaman yang sama.
2. Complete Binary Tree : setiap Subtree boleh memiliki panjang path yang berbeda dan setiap node kecuali leaf hanya boleh memiliki dua Child.
3. Skewed Binary Tree : sebuah Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu Child.
4. Balanced Binary Tree : tinggi maksimal suatu Tree adalah N-1, di mana N adalah jumlah node.



G. HASHING TABLE IMPLEMENTATION IN BLOCKCHAIN

     Dalam jaringan Blockchain, peran penting kriptografi terus berkembang tiada hentinya. Salah satunya yaitu proses perhitungan sebuah data secara konkret dan unik. Metode ini disebut juga dengan Hash. Ada banyak kode unik yang sering ditemukan di Blockchain, yang merupakan salah satu contoh dari Hash.

     Nilai berharga dari sebuah data saat ini berpotensi dibobol atau diketahui oleh orang lain. Salah satu teknik untuk mengatasinya adalah dengan memberikan kode unik. Data tersebut akan aman. Hanya orang yang terkait yang berhak dan bisa mengakses data tersebut. Saat ini, ada beragam proses pengamanan data, mulai dari sidik jari, sidik mata, dan di sistem Blockchain menggunakan kode unik (Hash).

     Saat ini, ada sejumlah Hash yang digunakan. Fungsi dan keamanannya pun beragam dan dengan kemampuan transaksi data cepat.

Comments

Post a Comment

Popular posts from this blog

AVL Tree dan B-Tree

Image
A. AVL Tree AVL adalah balanced binary search tree yang memiliki perbedaan jumlah node pada subtree kiri dan subtree kanannya maksimal satu.                                              Untuk menentukan Height dan Balance Factor, gunakan cara berikut : Height : 1. Jika node (root) tidak memiliki subtree heightnya = 0. 2. Jika node adalah leaf, height = 1. 3. Jika internal node, maka height = height tertinggi dari anak + 1. Balance Factor : 1. Selisih height antara anak kiri dan kanan. Jika tidak memiliki anak dianggap 0. Insertion Insert suatu node pada AVL Tree sama dengan insert node pada Binary Search Tree. Node baru diposisikan sebagai leaf. Setelah memasukkan node baru, maka harus dilakukan penyeimbangan kembali pada path dari node yang baru di-insert atau path terdalam. Namun biasanya, path terdalam adalah path dari node yang baru saja di-insert. ...
Read more

Binary Search Tree

A. BINARY SEARCH TREE      Binary Search Tree adalah tree yang terurut (ordered Binary Tree) yang memiliki kelebihan bila dibanding dengan struktur data lain. Binary Search Tree juga sering disebut dengan Sorted Binary Tree yang berfungsi untuk menyimpan informasi nama atau bilangan yang disimpan di dalam memory.      Ciri-ciri Binary Search Tree : 1. Setiap node mempunyai value dan tidak ada value yang double. 2. Value yang ada di kiri tree lebih kecil dari rootnya. 3. Value yang ada di kanan tree lebih besar dari rootnya. 4. Kiri dan kanan tree bisa menjadi root lagi atau bisa mempunyai child. 5. Memiliki sifat rekursif.      Binary Search Tree memiliki tiga operasi dasar : 1. Find(x) : menemukan value x di dalam Binary Search Tree (Search) 2. Insert(x) : memasukkan value baru x ke Binary Search Tree (Push) 3. Remove(x) : menghapus key x dari Binary Search Tree (Delete) B....
Read more