Selasa, 10 Maret 2020

Hashing and Hash Table and Binary Tree

Hash Table

Hash table merupakan salah satu struktur data yang digunakan dalam penyimpanan data sementara. Tujuan dari hash table adalah untuk mempercepat pencarian kembali dari banyak data yang disimpan. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif lebih cepat dibanding struktur data atau algoritma yang lain.

Pada Hash Table, kita akan mengenal suatu fungsi sederhana yang peranannya sangat esensial pada Hash Table. Fungsi tersebut adalah Hash Function. Apa sih Hash Function itu? Hash Function adalah fungsi yang memuat Hashing di dalamnya yang peranannya untuk mengubah value dari data yang akan disimpan, menjadi key value yang nantinya akan digunakan sebagai index untuk menyimpan data tersebut dalam struktur data. Mengapa kita membutuhkan Hash Function sih? Karena, prinsip Hash table  sendiri adalah menggunakan memori penyimpanan utama berbentuk array dengan tambahan algoritma untuk mempercepat pemrosesan data. Pada intinya hash table merupakan penyimpanan data menggunakan key value yang didapat dari nilai data itu sendiri. Jadi, Hash Function sangat dibutuhkan dalam Hash Table dan justru inilah yang membedakannya dengan struktur penyimpanan lainnya.

Gambaran Hash Table

Dapat dilihat dari gambaran sederhana di atas, bahwa setiap data yang diproses melalui Hash Function akan menghasilkan key value, lalu key value tersebut digunakan sebagai index penyimpanan dari data itu sendiri. Lalu pasti kalian akan bertanya-tanya, bagaiamana cara meng-convert nya ? Karena itu mari kita masuk ke dalam materi Hashing itu sendiri.

Hashing

Secara singkat, Hasing adalah Transformasi aritmatik sebuah data menjadi nilai yang merepresentasikan diri aslinya. Data tersebut bisa beragam, misalnya bisa saja ID, Nama, Nomor Kependudukan, bisa String, Integer, dan seterusnya. Intinya, apapun itu yang unik dari sebuah data, bisa di convert menjadi key melalui Hashing. Hashing sendiri merupakan sebuah aksi yang menjadi bagian dari Hash Function.

Caranya?


Ada berbagai macam cara untuk melakukan Hashing atau lebih tepatnya ada beragam Hash Function yang dapat digunakan. Namun, perlu diperhatikan bahwa tidak semua Hash Function mempunyai fungsi yang optimal, atau bisa saja terjadi collision dalam prosesnya. Collision adalah kondisi dimana 2 data diproses ke dalam Hash Function, namun menghasilkan key value yang sama sehingga ketika di store ke array, akan tejadi bentrokan. Karena itu, kita harus pandai-pandai dalam memilih Hash Function. 

Di sini tidak akan saya contohkan Hash Function yang sederhana, hanya akan saya berikan gambarannya. Misalnya, anda ingin meng-convert String jadi key value, cukup dengan memainkan ASCII dari setiap characternya, misal ASCII dari semua characternya anda tambahkan, nah hasilnya tinggal di modulus dengan size dari array yang anda siapkan supaya tidak out of bound. Itu sangat sederhana dan possibility of collision nya pasti besar. Karena itu, saya akan contohkan algoritma Hash Function yang lebih efisien. Di sini saya punya contoh algoritma dari DJB2. 

DJB2 Hash Function in C
DJB2 cukup efisien untuk struktur data dengan size besar, namun tidak menutup kemungkinan terjadinya collision apalagi jika sizenya kecil. Karena itu perlu penanganan untuk collision.

Berikut ini cara-cara yang digunakan untuk mengatasi collision :

1.   Closed hashing (Open Addressing)

Close hashing menyelesaikan collision dengan menggunakan memori yang masih ada tanpa menggunakan memori diluar array yang digunakan. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

·        Linear Probing
Apabila telah terisi, linear probing mencari alamat lain dengan bergeser 1 indeks dari alamat sebelumnya hingga ditemukan alamat yang belum terisi data, dengan rumus

·        Ø Quadratic Probing
Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini,anda dapat menentukan sendiri formula yang akan digunakan.

Kelemahan dari closed hashing adalah ukuran array yang disediakan harus lebih besar dari jumlah data. Selain itu dibutuhkan memori yang lebih besar untuk meminimalkan collision.

2.   Open hashing (Separate Chaining)
Pada dasarnya separate chaining membuat tabel yang digunakan untuk proses hashing menjadi sebuah array of pointer yang masing-masing pointernya diikuti oleh sebuah linked list, dengan chain (mata rantai) 1 terletak pada array of pointer, sedangkan chain 2 dan seterusnya berhubungan dengan chain 1 secara memanjang.

Kelemahan dari open hashing adalah bila data menumpuk pada satu/sedikit indeks sehingga terjadi linked list yang panjang.

Hashing pada Blockchain


Blockchain sangat bergantung pada cryptography untuk mendapatkan keamanan data mereka. Satu dari fungsi cryptography yang sangatlah penting dalam konteks ini adalah hashing. 

Dalam blockchain, nilai output yang dikenal sebagai hash, digunakan sebagai sebuah penanda unik untuk blok data. Hash setiap blok yang dihasilkan berhubungan dengan hash dari blok sebelumnya. Terlebih lagi, blok hash bergantung pada data yang terdapat dalam blok tersebut, yang berarti setiap perubahan yang terjadi pada data tersebut akan membutuhkan perubahan pada blok hash.

Maka dari itu, hash dari setiap blok dihasilkan berdasarkan data yang terdapat dalam blok tersebut dan hash dari blok sebelumnya. Penanda hash tersebut memainkan peran penting dalam memastikan keamanan dan keabadian blockchain.

Hashing juga berpengaruh dalam algoritma konsensus yang digunakan untuk memvalidasi transaksi. Sebagai contohnya, algoritma Proof of Work (PoW) yang digunakan dalam blockchain Bitcoin untuk mencapai konsensus dan penambangan koin baru, yang menggunakan sebuah fungsi hash yang disebut dengan SHA-256. Sesuai dengan namanya, SHA-256 mengambil input data dan menghasilkan sebuah hash yang memiliki panjang 256 bits atau 64 karakter.

Selain memberikan proteksi pada riwayat transaksi pada buku kas, cryptography juga memainkan peran dalam memastikan keamanan dompet yang digunakan untuk menyimpan mata uang digital. Pasangan kunci publik dan pribadi yang mengizinkan pengguna untuk menerima dan mengirimkan pembayaran dibuat melalui penggunaan cryptography kunci publik atau 'asimetris'. Kunci pribadi digunakan untuk membuat sebuah tanda tangan digital untuk transaksi, dan mengizinkan otentikasi kepemilikan koin yang dikirim.

Walaupun masih banyak sifat cryptography asimetris yang tidak tercakup dalam penjelasan ini, akan tetapi, cryptography asimetris ini menghalangi siapapun diluar pemilik kunci pribadi untuk pengaksesan dana yang disimpan dalam dompet mata uang digital, dan mengamankan dana sampai pemilik memutuskan untuk menggunakannya (selama kunci pribadi tidak dibeberkan dan terkompromi).


Binary Tree

Tree Concept

Tree adalah sebuah struktur data bukan linear yang secara bentuk menyerupai sebuah struktur pohon, yang terdiri dari serangkaian node (simpul) berisi data yang saling berhubungan.

contoh Tree

Beberapa konsep terkait Tree : 
  • Node paling atas di namakan Root atau akar
  • Garis yang menghubungkan node parent ke node child disebut edge
  • Node yang tidak memiliki child disebut leaf
  • Dua node yang memiliki parent yang sama disebut sibling
  • Descendant adalah seluruh node yang terletak setelah sebuah node dan terletak di jalur yang sama
  • Sub-tree adalah suatu node beserta descendantnya
  • Degree dari sebuah node dapat dihitung dari total sub-tree dari node tersebut
  • Height / Depth adalah banyaknya tingkatan / level dalam tree

Binary Tree


Binary Tree adalah tree dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak / child.

contoh Binary Tree

Dalam implementasi nya, Binary Tree digunakan sebagai sebuah sorted data structure, salah satu contohnya Binary Search Tree. Akan saya beri sedikit gambaran dalam codingannya. 

Contoh Codingan deklarasi Binary Search Tree :

Struct node {

    int value;
    node *left, *right; 

}*root;


Konsep Linked List sangat terpakai di sini, hanya perlu penyesuain di beberapa syarat tree saja. Namun, untuk insertion, searching, ataupun deletion akan ada perbedaan yang cukup signifikan dengan Linked List.

Tipe-tipe Binary Tree

  • Perfect Binary Tree, adalah binary tree yang setiap levelnya memiliki kedalaman yang sama.
Perfect Binary Tree

  • Complete Binary Tree, adalah binary tree yang seluruh node pada setiap levelnnya terisi penuh, kecuali level terakhir dan penempatan node nya diutamakan yang sebelah kiri penuh terlebih dahulu. Perfect Binary Tree bisa juga disebut Complete Binary Tree.
Complete Binary Tree

  • Skewed Binary Tree, adalah binary tree yang setiap nodenya hanya punya maksimal 1 child sehingga sangat jelas bahwa binary tree ini tidak seimbang.
Skewed Binary Tree

  • Balanced Binary Tree, adalah binary tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. Binary tree ini merupakan konsep yang digunakan dalam AVL (Adelson-Velskii and Landis). Perfect Binary Tree dan Complete Binary Tree termasuk juga dalam Balanced Binary Tree.
Balanced Binary Tree



Demikian adalah penjelasan / rangkuman saya mengenai materi Hashing, Hash Tables, dan Binary Tree, semoga membantu teman-teman sekalian. Beri tahu saya melalui kolom komentar kalau ada penjelasan yang kurang / salah. Terimakasih.


Refrensi :


Diposting oleh di

Tidak ada komentar:

Posting Komentar

Langganan: Posting Komentar (Atom)