Hashing table & Binary Tree

Halo teman-teman, pada blog ini saya akan membahas mengenai hash table dan binary tree.

HASHING

Hashing adalah teknik untuk melakukan penambahan/insertion, penghapusan/deletion dan pencarian/searching dengan constant average time. Hashing merupakan teknik untuk mengubah berbagai key value menjadi berbagai indeks dari sebuah array. Untuk menambahkan data atau pencarian, ditentukan key dari data tersebut dan digunakan sebuah fungsi hash untuk menetapkan lokasi untuk key tersebut. 

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 array sebagai medium penyimpanan dan menggunakan fungsi hash untuk menghasilkan sebuah indeks dimana suatu elemen harus dimasukkan atau ada. Hal ini menyebabkan waktu yang dibutuhkan untuk penambahan data (insertions), penghapusan data (deletions), dan pencarian data (searching) relatif sama dibanding struktur data atau algoritma yang lain.

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. Untuk setiap key, digunakan fungsi hash untuk memetakan key pada bilangan dalam rentang 0 hingga H-size-1. Dengan key value tersebut didapat hash value.

Kelebihan dari hash table antara lain sebagai berikut:

–       Hash table relatif lebih cepat

–       Kecepatan dalam insertions, deletions, maupun searching relatif sama

HASH FUNCTION

Hash function merupakan suatu fungsi sederhana untuk mendapatkan hash value dari key value suatu data. Kita akan menggunakan operator modulo untuk mendapatkan berbagai key value. 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).

Ada banyak cara untuk hash dari string ke key. Berikut adalah beberapa metode penting hash function:

-          Mid-square

Kuadratkan string/Identifier dan kemudian menggunakan angka bit tengah untuk mendapatkan hash-Key. Jika key adalah string, maka akan dikonversi ke angka.

Step:

1.      Kuadratkan nilai key. K2

2.      Ekstrak bit r tengah dari hasil yang diperoleh pada step 1

Fungsi: h (k) = s

k = key

s = hash key yang diperoleh dengan memilih r bit dari K²

-          Division (most common)

Membagi string/Identifier dengan menggunakan operator modulus. Ini adalah metode yang paling sederhana untuk hashing sebuah integer x.

Fungsi: h(z) = z mod M

z  = key

M = value yang digunakan untuk membagi key, biasanya menggunakan bilangan prima, ukuran tabel atau ukuran memori yang digunakan.

-          Folding

Partisi string/Identifier menjadi beberapa bagian, kemudian tambahkan bagian bersama-sama untuk mendapatkan hash key.

Step:

1.      Membagi key value ke dalam beberapa bagian

2.      Tambahkan individual part (biasanya last carry diabaikan)

-          Digit Extraction

Digit yang telah ditetapkan dari nomor yang diberikan dianggap sebagai alamat hash.

Contoh:

Misalkan x = 14.568

Jika kita mengekstrak digit pertama, ketiga, dan kelima, kita akan mendapatkan kode hash: 158.

-          Rotating Hash

Gunakan metode hash (seperti metode division atau Mid-Square). Setelah mendapatkan kode hash/alamat dari metode hash, lakukan rotasi. Rotasi dilakukan dengan menggeser digit untuk mendapatkan alamat hash baru.

Contoh:

Misal alamat hash = 20021

Hasil rotasi: 12002 (membalik angka)

COLLISION

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. Untuk meminimalkan collision gunakan hash function yang dapat mencapai seluruh indeks/alamat. Karena memori yang terbatas dan untuk masukan data yang belum diketahui tentu collision tidak dapat dihindari.

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. Closed hashing mencari alamat lain apabila alamat yang akan dituju sudah terisi oleh data. 3 cara untuk mencari alamat lain tersebut :

a.        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

(h+1) mod m.

b.      Quadratic Probing

Quadratic Probing mencari alamat baru untuk ditempati dengan proses perhitungan kuadratik yang lebih kompleks. Tidak ada formula baku pada quadratic probing ini.

Contoh formula quadratic probing untuk mencari alamat baru:

h,(h+i²)mod m,(h-i²)mod m, … ,(h+((m-1)/2)²)mod m, (h-((m-1)/2)²)mod m

dengan i = 1,2,3,4, … , ((m-1)/2)

Maksud formula di atas adalah jika alamat h telah terisi, maka alamat lain yang digunakan adalah (h+1)mod m, jika telah terisi gunakan alamat (h-1)mod m,  jika telah terisi gunakan alamat (h+4)mod m, jika telah terisi gunakan alamat (h-4)mod m, dan seterusnya.

Jadi jika m=23,maka nilai maksimal i adalah : ((23-1)/2)=11.

c.       Double hashing

Sesuai dengan namanya, alamat baru untuk menyimpan data yang belum dapat masuk ke dalam table diperoleh dengan menggunakan hash function lagi. Hash function kedua yang digunakan setelah alamat yang dihasilkan oleh hash function awal telah terisi tentu saja berbeda dengan hash function awal itu sendiri.

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.

TREE

Tree merupakan salah satu struktur data tidak linier yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul / node dengan satu elemen khusus yang disebut root dan node lainnya. Subtree adalah tree yang terbagi menjadi himpunan-himpunan yang tak saling berhubungan satu sama lainnya. Berikut adalah istilah umum pada tree:

· parent : predecssor satu level di atas suatu node.

· child : successor satu level di bawah suatu node.

· sibling : node-node yang memiliki parent yang sama dengan suatu node.

· subtree : bagian dari tree yang berupa suatu node beserta descendantnya dan memiliki semua karakteristik dari tree tersebut.

· size : banyaknya node dalam suatu tree.

· height : banyaknya tingkatan/level dalam suatu tree.

· root : satu-satunya node khusus dalam tree yang tak punya predecssor.

· leaf : node-node dalam tree yang tak memiliki seccessor.

· degree : banyaknya child yang dimiliki suatu node.

Contoh:

DEGREE of TREE = 3

DEGREE of C = 2

HEIGHT = 3

PARENT of C = A

CHILDREN of  A = B, C, D

SIBILING of F = G

ANCESTOR of F = A, C

DESCENDANT of C = F, G

BINARY TREE

Binary tree/

pohon biner adalah pohon 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. Implementasi binary tree bisa dilakukan menggunakan linked list. Masing-masing node terdiri dari tiga bagian yaitu sebuah data/info dan dua buah pointer yang dinamakan pointer kiri dan kanan.

Node Pada Binary Tree 
Jumlah maksimum node pada setiap tingkat adalah 2ⁿ, node pada binary tree maksimumnya berjumlah 2ⁿ-1.

Tipe Binary Tree

1. PERFECT binary tree adalah pohon biner di mana setiap tingkat berada pada kedalaman yang sama.

2. COMPLETE binary tree adalah pohon biner di mana setiap tingkat, kecuali yang terakhir, sepenuhnya diisi dan semua node yang sejauh mungkin kiri. Sebuah PERFECT binary tree pasti COMPLETE binary tree.

3. SKEWED binary tree adalah pohon biner di mana setiap node memiliki paling banyak satu anak.

4. BALANCED binary tree is a binary tree in which no leaf is much farther away from the root than any other leaf (different balancing scheme allows different definitions of “much farther”).

Operasi Binary Tree

Operasi-operasi pada Binary Tree :

v Create : Membentuk binary tree baru yang masih kosong.

v Clear : Mengosongkan binary tree yang sudah ada.

v Empty : Function untuk memeriksa apakah binary tree masih kosong.

v Insert : Memasukkan sebuah node ke dalam tree. Ada tiga pilihan insert: sebagai root, left child, atau right child. Khusus insert sebagai root, tree harus dalam keadaan kosong.

v Find : Mencari root, parent, left child, atau right child dari suatu node. (Tree tak boleh kosong)

v Update : Mengubah isi dari node yang ditunjuk oleh pointer current. (Tree tidak boleh kosong)

v Retrieve : Mengetahui isi dari node yang ditunjuk pointer current. (Tree tidak boleh kosong)

v DeleteSub : Menghapus sebuah subtree (node beserta seluruh descendantnya) yang ditunjuk current. Tree tak boleh kosong. Setelah itu pointer current akan berpindah ke parent dari node yang dihapus.

v Characteristic : Mengetahui karakteristik dari suatu tree, yakni : size, height, serta average lengthnya. Tree tidak boleh kosong. (Average Length = [jumlahNodeLvl1*1+jmlNodeLvl2*2+…+jmlNodeLvln*n]/Size)

v Traverse : Mengunjungi seluruh node-node pada tree, masing-masing sekali. Hasilnya adalah urutan informasi secara linier yang tersimpan dalam tree. Adatiga cara traverse : Pre Order, In Order, dan Post Order.

Langkah-Langkahnya Traverse :

Ø PreOrder : Cetak isi node yang dikunjungi, kunjungi Left Child, kunjungi Right Child.

Ø InOrder : Kunjungi Left Child, Cetak isi node yang dikunjungi, kunjungi Right Child.

Ø PostOrder : Kunjungi Left Child, Kunjungi Right Child, cetak isi node yang dikunjungi.

IMPLEMENTASI HASH PADA BLOCKCHAIN

Blockchain adalah sistem pencatatan transaksi di banyak database yang tersebar luas di banyak komputer yang masing-masing memuat catatan yang identikal. Blockchain memiliki tiga mekanisme, salah satunya menggunakan teknik hash. Hash berguna untuk mendeteksi perubahan yang terjadi didalam blockchain. Teknik ini membuat blockchain lebih aman dan kredibel dalam menyimpan data-data penting karena jika ada yang mengubah satu blok dalam blockchain maka nilai hashnya akan berubah menjadi tidak valid. Lalu perubahan tersebut akan menyebabkan seluruh blockchain menjadi tidak valid.

 

Dibuat Oleh:

Nama : Sheila Gracia Angelina

NIM : 2301857456