Hashing Table


Pengertian Hash Tabel


Hash Table merupakan struktur data yang terdiri atas sebuah tabel dan fungsi. Bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel. Keunggulan dari struktur hash table ini :
  • waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).
  • Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record tidak sama tetapi dapat dibangkitkan dengan angka hash yang sama).      
Operasi Pada Hash Tabel
  •            insert: diberikan sebuah key dan nilai, insert nilai dalam tabel
  •       find: diberikan sebuah key, temukan nilai yang berhubungan dengan key
  •     remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut
  •       getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu
Pengaplikasian
   Berikut contoh penggunaan hash table dengan hash function sederhana yaitu memodulus key value dengan ukuran array : h = k (mod m)
Misal kita memiliki array dengan ukuran 13, maka hash function : h = k (mod 13).
Dengan hash function tersebut didapat :
kH
77
130
2512
271
390
Perhatikan range dari h untuk sembarang nilai k.
Maka data 7 akan disimpan pada index 7, data 13 akan disimpan pada index 0, dst..
Untuk mencari kembali suatu data, maka kita hanya perlu menggunakan hash function yang sama sehingga mendapatkan hash index yang sama pula.
Misal : mencari data 25 → h = 25 (mod 13) = 12
Namun pada penerapannya, seperti contoh di atas terdapat tabrakan (collision) pada k = 13 dan k = 39. Collision berarti ada lebih dari satu data yang memiliki hash index yang sama, padahal seperti yang kita ketahui, satu alamat / satu index array hanya dapat menyimpan satu data saja.


Binary Tree
 Tree (pohon) adalah salah satu bentuk struktur data yang menggambarkan hubungan hierarki antar elemen-elemennya (seperti relasi one to many). Sebuah node dalam tree biasanya bisa memiliki beberapa node lagi sebagai percabangan atas dirinya.
http://sourcecodemania.com/wp-content/uploads/2012/05/tree-general.jpg
Lalu, ada lagi yang namanya Binary Tree. Apa bedanya? Sebenarnya sama sama konsepnya dengan Tree. Hanya saja, kita akan mengambil sifat bilangan biner yang selalu bernilai 1 atau 0 (2 pilihan). Berarti, binary tree adalah tree yang hanya dapat mempunyai maksimal 2 percabangan saja. Untuk lebih jelasnya, lihat gambar di bawah ini.
https://www.cs.cmu.edu/~adamchik/15-121/lectures/Trees/pix/binaryTree.bmp
Lanjut lagi, sekarang kita akan memasuki pembelajaran intinya yaitu Binary Search Tree atau sering disingkat BST. Apalagi BST itu? Dan apa bedanya dengan yang dua diatas? Sebenarnya mirip-mirip saja, Binary Search Tree adalah struktur data yang mengadopsi konsep Binary Tree namun terdapat aturan bahwa setiap clild node sebelah kiri selalu lebih kecil nilainya dari pada root node. Begitu pula sebaliknya, setiap child node sebelah kanan selalu lebih besar nilainya daripada root node.
https://upload.wikimedia.org/wikipedia/commons/thumb/d/da/Binary_search_tree.svg/2000px-Binary_search_tree.svg.png
Kenapa harus membedakan kiri dan kanan sesuai besaran nilainya? Tujuannya untuk memberikan efisiensi terhadap proses searching. Kalau struktur data tree sudah tersusun rapi sesuai aturan mainnya, proses search akan lebih cepat.
Pseucode dalam C


Hash In Blokchain
Struktur data adalah cara khusus menyimpan data. Ada dua properti struktur data yang sangat penting jika Anda ingin memahami cara kerja blockchain. Mereka:
  1. Pointer.
  2. Daftar Tertaut.
Pointer
Pointer adalah variabel dalam pemrograman yang menyimpan alamat variabel lain. Biasanya variabel normal dalam bahasa pemrograman menyimpan data.
Misalnya. int a = 10, berarti ada variabel “a” yang menyimpan nilai integer. Dalam hal ini, ia menyimpan nilai integer yaitu 10. Ini adalah variabel normal.
Pointer, bagaimanapun, bukannya menyimpan nilai akan menyimpan alamat variabel lain. Itulah sebabnya mereka disebut pointer, karena mereka secara harfiah menunjuk ke lokasi variabel lain.
Daftar Tertaut
Daftar tertaut adalah salah satu item paling penting dalam struktur data. Seperti inilah daftar tertaut:
Ini adalah urutan blok, masing-masing berisi data yang ditautkan ke blok berikutnya melalui pointer. Variabel pointer, dalam hal ini, berisi alamat node berikutnya di dalamnya dan karenanya koneksi dibuat. Node terakhir, seperti yang Anda lihat, memiliki pointer nol yang berarti tidak memiliki nilai.
Satu hal penting yang perlu diperhatikan di sini, pointer di dalam setiap blok berisi alamat dari blok berikutnya. Itulah bagaimana pointing dicapai. Blok pertama disebut “blok genesis” dan penunjuknya terletak pada sistem itu sendiri. Ini terlihat seperti ini:
struktur blockchain:
Blockchain adalah daftar tertaut yang berisi data dan pointer hash yang menunjuk ke blok sebelumnya, sehingga menciptakan rantai. Apa itu hash pointer? Sebuah pointer hash mirip dengan sebuah pointer, tetapi bukan hanya berisi alamat dari blok sebelumnya tetapi juga berisi hash dari data di dalam blok sebelumnya . Tweak kecil ini adalah apa yang membuat blockchains sangat luar biasa andal dan trailblazing.
Bayangkan ini sebentar, seorang hacker menyerang blok 3 dan mencoba mengubah data. Karena sifat fungsi hash, sedikit perubahan dalam data akan mengubah hash secara drastis. Ini berarti bahwa setiap perubahan kecil yang dibuat di blok 3, akan mengubah hash yang disimpan di blok 2, sekarang pada gilirannya akan mengubah data dan hash blok 2 yang akan menghasilkan perubahan di blok 1 dan seterusnya dan seterusnya . Ini sepenuhnya akan mengubah rantai, yang tidak mungkin. Inilah tepatnya bagaimana blockchain mencapai keabadian.
Header blok berisi:
  • Versi: Nomor versi blokir.
  • Waktu: cap waktu saat ini.
  • Target sulit saat ini. (Lebih lanjut tentang ini nanti).
  • Hash dari blok sebelumnya.
  • Nonce (lebih lanjut tentang ini nanti).
  • Hash dari Merkle Root.





Komentar

Posting Komentar

Postingan populer dari blog ini

Gambar
Stack and Queue 1.  Stack Stack   atau tumpukan dapat diartikan sebagai suatu kumpulan data yang seolah-olah terlihat seperti ada data yang diletakkan di atas data yang lain. Kaidah utama dalam konsep  stack  adalah LIFO yang merupakan singkatan dari  Last In First Out,  artinya adalah data yang terakhir kali dimasukkan atau disimpan, maka data tersebut adalah yang pertama kali akan diakses atau dikeluarkan. Operasi pada Stack  : Operasi  push , berfungsi memasukkan sebuah nilai atau data ke dalam  stack . Sebelum itu, nilai atau data dimasukkan ke dalam stack , dengan cara menaikkan posisi  top  satu  level  ke atas. ilustrasi kerja pada operasi  push : Gambar 3.2  Ilustrasi kerja operasi  push Operasi  pop , berfungsi umengeluarkan atau menghapus nilai terakhir (yang berada pada posisi paling atas) dari  stack , dengan cara menurunkan nilai  top  satu  level  ke bawah. Berikut ilustrasi kerja pada operasi  p op : Gambar 3.3  Ilustrasi kerja op
Baca selengkapnya

Heap and Tries

Gambar
Heap Heap adalah complete binary tree berdasarkan struktur data yang memenuhi properti heap. Tujuan dari heap ini adalah untuk menemukan nilai terkecil pada min heap dan nilai terbesar pada max heap.  mempunyai properties sebagai berikut: Min Heap Setiap node lebih kecil dari masing-masing childnya Root merupakan node paling kecil, sedangkan node terbesar terletak pada leaf no         Find-Min Minimum node terletak pada root         Insertion    Insert node selalu berurutan dari level paling rendah dengan urutan left ke right New node selalu menjadi leaf node Sesuikan sesuai heap properties secara rekursif           Deletion-Min pada Min-Heap Node yang dihapus selalu root karena merupakan node paling kecil, lalu diganti dengan node yang paling terakhir di insert Sesuaikan dengan heap properties secara rekursif         Max Heap Setiap node lebih besar dari masing-masing childnya Root merupakan node paling besar, sedangkan node terkecil terletak pa
Baca selengkapnya
Gambar
STRUKTUR DATA - Linked List Linked List Linked List (senarai berantai) adalah struktur data yang terdiri dari urutan record data. Dimana setiap recordnya memiliki field untuk menyimpan alamat/referensi dari record selanjutnya. Elemen data yang dihubungkan dengan link pada Linked List disebut Node. Biasanya didalam suatu linked list, terdapat istilah head dan tail.  Head adalah elemen yang berada pada posisi pertama dalam suatu linked list Tail adalah elemen yang berada pada posisi terakhir dalam suatu linked list Macam - Macam Linked List      1.  Singly Linked List :      Setiap node pada linked list mempunyai field yang berisi pointer ke node berikutnya dan juga memiliki field yang             berisi data.  Pembuatan Single Linked List dapat menggunakan 2 metode: ·          LIFO (Last In First Out), aplikasinya : Stack (Tumpukan) ·          FIFO (First In First Out), aplikasinya : Queue (Antrean) 2.  Double Linked List adalah linked list dengan men
Baca selengkapnya