Hash Table dan Binary Tree
Hash Table
Hash table adalah data struktur yang memetakan data
data kedalam sebuah table dimana pemetaan table tersebut berdasarkan hashing.
Tujuan dari hash table sendiri adalah untuk mempercepat pencarian data karena
data data tersebut sudah tersusun. Tetapi dalam kenyataannya sendiri algoritma
hashing sendiri masih memiliki beberapa kelemahan karena beberapa data memiliki
hasil hash yang sama yang akan membuat data mengalami tabrakan sehingga
penyusunan dalam table pun juga akan menjadi masalah.
Hashing sendiri adalah sebuah proses untuk mengubah
string menjadi sebuah key dimana panjang string tersebut tetap tergantung
dengan algoritma untuk hashnya. Sebuah string dapat menjadi lebih panjang
maupun menjadi lebih pendek. Karena panjang string yang tetap itu maka ada
kemungkinan untuk terjadinya tabrakan atau sering disebut dengan Collision.
Ada beberapa metode untuk melakukan hash atau Hash
function, contoh sederhananya seperti:
1.
Mid Square
2.
Division
3.
Folding
4.
Digit Extraction
5.
Rotating Hash
Saya akan menjelaskan cara kerja dua Hash function
tersebut, Pada Hash function pertama yaitu Mid square. Pertama yang akan
dilakukan adalah dengan melakukan operasi pangkat dua pada sebuah angka lalu
akan diambil angka pada bagian tengahnya, jumlah angka yang diambil bisa bebas
tetapi harus konsisten. Hash function folding yaitu dengan membagi angka angka
menjadi beberapa digit setelah itu angka yang telah dibagi akan dijumlahkan.
Misalnya 1023 akan dipisah menjadi 10 dan 23 lalu dijumlahkan menjadi 33 maka
itulah hashnya.
Di awal saya menjelaskan tentang collision dimana
hash value dari sebuah data sama sehingga penempatan dalam table pun menjadi
bermasalah. Untuk itu ada dua cara untuk mengatasinya.
1. Linear
Probing
Cara ini adalah dengan memasukan
data ditempat kosong terdekat jika terjadi sebuah collision
2.
Chaining
Cara
ini adalah dengan membuat sebuah Linked list di block yang mengalami collision.
Blockchain
adalah kumpulan record yang berisikan data data yang berhubungan dengan kriptokurensi seperti dengan jejak waktu dan transaksi dimana setiap record ini disimpan dalam sebuah block yang akan terhubung dengan block lain. Block block ini akan terhubung dengan hash block sebelumnya, konsep dari blockchain ini sendiri hampir mirip dengan Linked list. Penggunaan hash dalam blockchain sendiri adalah untuk menghindari terjadinya pengubahan data secara tidak sah. Jadi jika ada hash yang tidak sesuai dengan hash yang tersimpan dalam block tersebut maka transaksi sudah diubah secara illegal. Block chain sendiri menggunakan hash dalam menghubungkan block block yang lain, maka dari itu diperlukan sebuah hash function yang memiliki collision yang sangat minimal karena record record ini akan terus bertambah banyak.
Binary Tree
adalah sebuah data struktur non linear tetapi penhubungan data data bersifat hieraki.
Ada beberapa sebutan yang umum digunakan dalam Tree,yaitu root yang berarti data yang berada paling atas, leaf adalah data terujung yang tidak memilki anak/ cabang. Sibiling adalah data yang memiliki parent yang sama dan edge adalah yang meghubungkan setiap node.
Jenis-jenis Binary Tree
- Perfect Binary Tree dimana setiap node memiliki dua anak dan panjang nya sama.
- Complete Binary Tree, adalah Binary Tree dimana setiap tingkatan pada Tree tersebut terisi terkecuali bagian terakhir dimana bagian terakhir harus di isi mulai dari bagian kiri sehingga bagian kiri dari binary tree tersebut akan penuh.
-
Skewed Binary Tree adalah Binary Tree yang setiap nodenya paling tidak memiliki satu anak.
1. Insertion
2. Search
3. Delete
Dalam Binary Tree sendiri penghubungan setiap nodes mirip dengan Linked list dimana setiap node nantinya akan memiliki address untuk nodes sebelumnya/ nodes parent dan akan memiliki nodes untuk anak yaitu nodes left dan nodes right. Dalam penerapannya operasi operasi dalam Binary Tree sendiri akan menggunakan konsep rekursif untuk mempermudah melakukan operasi operasi diatas.
Komentar
Posting Komentar