Hashing Table and Binary Tree


HASHING 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. Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi. Hash table menggunakan suatu teknik penyimpanan sehingga waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain. Yang perlu diperhatikan untuk membuat hash function adalah:
-       ukuran array/table size(m),
-       key value/nilai yang didapat dari data(k),
-       hash value/hash index/indeks yang dituju(h).

Beberapa struktur data dan algoritma pencarian (searching) yang memiliki kelebihan dan kekurangan masing-masing. Begitu pula dengan hash table ini juga memiliki kekurangan dan kelebihan. Kelebihan dari hash table antara lain sebagai berikut:
-       Hash table relatif lebih cepat
-       Kecepatan dalam insertions, deletions, maupun searching relatif sama

Hash table 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. Dengan key value tersebut didapat hash value. Jadi hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Sebenarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:
-       Untuk dua buah key yang sama, hasil hashing-nya selalu sama.
-       Memiliki kompleksitas rendah.
-       Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).

BINARY TREE
Binary Tree adalah tree dengan syarat bahwa tiap node hanya boleh memiliki 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 child.

Jenis-jenis Binary Tree :
a) Full Binary Tree
Binary Tree yang tiap nodenya (kecuali leaf) memiliki dua child dan tiap subtree harus mempunyai panjang path yang sama.



b) Complete Binary Tree
Mirip dengan Full Binary Tree, namun tiap subtree boleh memiliki panjang path yang berbeda. Node kecuali leaf memiliki 0 atau 2 child.

c) Skewed Binary Tree
Skewed binary tree yakni Binary Tree yang semua nodenya (kecuali leaf) hanya memiliki satu child.


HASH IN BLOCK CHAIN
Secara sederhana, hashing berarti mengambil string input dengan panjang berapapun dan memberikan output dengan panjang tetap. Dalam konteks cryptocurrency seperti bitcoin, transaksi diambil sebagai input dan dijalankan melalui algoritma hashing (bitcoin menggunakan SHA-256) yang memberikan output dengan panjang tetap. SHA-256 adalah Secure Hashing Algorithm 256.
Blockchain adalah daftar tertaut yang berisi data dan pointer hash yang menunjuk ke blok sebelumnya, sehingga menciptakan rantai. Hash pointer yaitu sebuah pointer yang bukan hanya berisi alamat dari blok sebelumnya, tetapi juga berisi hash dari data di dalam blok sebelumnya.





Sumber :
-       https://informatika11d.wordpress.com/2012/11/22/struktur-data-hash-table/
-       http://kupaskode.blogspot.com/2015/09/tentang-hashing.html
-       https://www.barantum.com/blog/blockchain-adalah/
-       http://new-funday.blogspot.com/2012/12/struktur-data-tree-dan-penjelasaanya.html


Comments

Post a Comment

Popular posts from this blog

Binary Search Tree (BST)

  Binary Search Tree (BST) adalah Binary Tree dengan sifat bahwa semua left child harus lebih kecil daripada right child dan parentnya. Juga semua right child harus lebih besar dari left child serta parentnya. Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Jika struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat. Aturan main Binary Search Tree : -           Setiap child node sebelah kiri harus lebih kecil nilainya daripada root nodenya. -           Setiap child node sebelah kanan harus lebih besar nilainya daripada root nodenya. Lalu, ada 3 jenis cara untuk melakukan penelusuran data (traversal) pada BST : -           PreOrder : Print data, telusur ke kiri, telusur ke kanan -      ...
Read more

Rangkuman Data Structure

Image
Nama: Melody Effendi NIM: 2301925854 Kelas: CB01 Lecturer: Ferdinand Ariandy Luwinda (D4522) dan Henry Chong (D4460) LINKED LIST Linked list atau senarai berantai merupakan suatu kumpulan elemen bertipe sama yang berurutan sesuai dengan ketentuan tertentu. Setiap elemennya dihubungkan melalui pointer. Struktur data pada linked list ini terdiri dari urutan record data, yang masing-masingnya memiliki field untuk menyimpan alamat atau referensi dari record selanjutnya (dalam urutan). Pada linked list, ada istilah node yang berarti elemen data yang dihubungkan dengan link pada linked list. Selain node, ada juga istilah head dan tail. Head adalah elemen yang berada di posisi pertama dalam linked list tersebut, sedangkan tail adalah elemen yang berada di posisi terakhir dalam linked list tersebut. Selain itu, istilah pointer berarti alamat elemen. Macam-macam linked list yaitu sebagai berikut. 1. Circular Single Linked List Arti dari single linked list sendiri adalah suatu kump...
Read more