Hashmap And Binary Tree

Nama : Dikky Larson
NIM : 2301853930

Hashing and Hash Table

Pendahuluan

Hashing adalah sebuah metode/cara menyimpan dan mengambil data secepat mungkin. Jika kita menggunakan loop untuk mengambil suatu data dari index tertentu, maka akan diperlukan waktu compile sebanyak ON dikarenakan kita harus mencari dari awal hingga akhir.

Hal itu tidak terjadi pada hashing sebab hashing menggunakan metode penyimpanan dimana indeksnya merupakan hasil dari manipulasi string yang kita input. Sehingga ketika kita melakukan pencarian, system akan bisa langsung menunjuk pada indeks yang menjadi tempat dimana data tersebut disimpan.

Hash Function

Untuk mengubah/memanipulasi string menjadi indeks hash-table, diperlukan hash function. Berikut ini beberapa contoh dari hash function:
  1. Mid-square
    1.1. Mid-square function, sumber: binusmaya.binus.ac.id
    Mid-square merupakan fungsi hash dimana kita akan memangkatkan value awal, lalu mengambil angka tengah sebagai indeks untuk hash table. Jika valuenya berupa string, maka terlebih dahulu kita mengubahnya ke dalam number (int) menggunakan ASCII atau metode lain yang kita ketahui.
  2. Division
    2.1. Division function
    Dalam division function, kita mengubah value dari data yang ingin dimasukkan menggunakan modifier. Sangat dianjurkan untuk menggunakan bilangan prima -sesuai dengan jumlah table yang ingin dibuat- sebagai modifier untuk menghindari terjadinya collision (data bertumpuk dalam satu indeks table).
  3. Folding
    3.1. Folding function, sumber: binusmaya.binus.ac.id
    Folding adalah teknik hashing dengan langkah pertama yaitu, membagi value menjadi beberapa bagian, menjumlahkannya, baru memasukkannya sesuai dengan size table yang sudah dibuat/ditentukan.
  4. Digit Extraction
    4.1. Contoh Digit Extraction Logic, sumber: binusmaya.binus.ac.id
    Digit extraction adalah metode dimana kita hanya mengambil beberapa digit dalam sebuah value sebagai hashkey untuk hash table yang kita buat.
  5. Rotating Hash
    Rotating Hash merupakan metode hash yang menggunakan salah satu function diatas (mid-square atau division), lalu key yang sudah ada kemudian dirotasi digitnya.

    Contoh:
    hashkey yang sudah kita dapatkan dari salah satu function = 20021
    hashkey kemudian dirotasi sesuai yang kita inginkan, misalnya menjadi = 12002 (di-flip)

Collision

Collision adalah kondisi dimana value yang kita masukkan bertabrakan dengan value yang sebelumnnya di satu indeks hash table yang sama.

Misal kita akan menyimpan value atan dan acos. Jika kita hanya hashing pada huruf pertama menggunakan division, maka indeks atan dan acos akan menempati bagian indeks yang sama. Hal ini tentu akan menimbulkan issue karena kemungkinan data akan ter-overwrite.

Ada dua solusi untuk mengatasi permasalahan ini, diantaranya:
  1. Linear Probing
    Linear probing adalah cara pertama untuk menghidari collision dengan cara memindahkannya ke indeks yang masih kosong di setelah/sebelum indeks hash. Hal ini memiliki kelemahan, salah satunya adalah terbatasnya spare indeks ,jika data yang dimasukkan semakin banyak, maka compilation time akan semakin lama karena sudah banyak indeks hash table yang penuh dan jika semua table sudah penuh, maka data tidak akan masuk atau terbuang.
    1.2. Penggambaran logika Linear Probing, sumber: binusmaya.binus.ac.id
  2. Chaining
    Chaining merupakan teknik penambahan memory allocation menyamping jika terjadi collision di suatu indeks hash table. Dengan penambahan penampung data secara menyamping, kita tidak perlu khawatir akan limitasi data yang ditampung.
    2.2.Penggambaran logika Chaining, sumber: binusmaya.binus.ac.id

Implementasi Hash Table dalam Blockchain

Hash table pada blockchain digunakan untuk mengambil transaction pada suatu block menggunakan key yang ada.
Selebihnya mengenai blockchain dapat dibaca disini: http://ceur-ws.org/Vol-2334/DLTpaper4.pdf

Tree dan Binary Tree

Pengenalan Tree

Tree adalah struktur data yang bersifat non-linear yang menggambarkan hubungan hierarki antar objek data.

Konsep Tree

  • Objek data yang berada di puncak/paling atas disebut root.
  • Node yang berada diatas node yang lain disebut parent/ancestor dari node tersebut.
  • Node yang berada di bawah node yang lain disebut child/descendant node dari parentnya.
  • Garis yang menghubungkan parent dengan child node disebut edge.
  • Total subtree/cabang disebut degree.
  • Jumlah maksimum degree dari sebuah node disebut height/depth.

Binary Tree

Binary tree adalah jenis tree dimana tiap-tiap node memiliki paling banyak dua degree (dua child node).

Jenis Binary Tree

Beberapa jenis binary tree, diantaranya adalah:
  1. Perfect Binary Tree
    Image result for perfect binary tree
    1.1. Perfect Binary Tree, sumber: https://i.stack.imgur.com/EHqzp.png
    Perfect binary tree adalah kondisi dimana degree dari tiap node di setiap level memiliki jumlah yang sama.
  2. Complete Binary Tree
    Image result for complete binary tree
    2.1. Complete Binary Tree, sumber: https://web.cecs.pdx.edu/~sheard/course/Cs163/Graphics/CompleteBinary.jpg
    Complete binary tree adalah tree dimana setiap node di tiap level, kecuali kemungkinan yang terakhir, memiliki data objek. Semua perfect binary tree adalah complete binary tree.
  3. Skewed Binary Tree
    Image result for skewed binary tree
    3.1. Left and Right Skewed Binary Tree, sumber: https://www.tutorialride.com/images/data-structures/skewed-binary-tree.jpeg
    Skewed binary tree adalah jenis binary tree dimana degree dari tiap node di tiap level hanya berjumlah satu.
  4. Balanced Binary Tree
    Image result for balanced binary tree
    4.1. Balanced Binary Tree, sumber: https://upload.wikimedia.org/wikipedia/commons/thumb/0/06/AVLtreef.svg/251px-AVLtreef.svg.png
    Balanced binary tree adalah kondisi dimana jumlah perbedaan antara subtree kiri dan subtree kanannya paling banyak berjumlah satu.
Sekian dan Terima Kasih! 😄

Comments

Post a Comment