Hash Table & Tree

Hashing

Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi.Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai key yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.



Hash Function

Ada banyak cara untuk hash sebuah string menjadi sebuah key. berikut cara penting untuk membuat sebuah hash function:

Mid Square
Kuadratkan string/identifier, lalu kita mengambil angka tengah dari kuadrat identifier sebagai hash key.

Function : h(k) = s

k = key, s = hash key yang didapatkan dari mengambil tengah dari k^2

Division
 String/identifier dibagi dengan menggunakan modulus.

Function : h(z) = z mod M

z = key, M = angka yang digunakan untuk membagi key (biasanya menggunakan angka prima)

Folding
Langkah :

• bagi key value menjadi beberapa bagian
• jumlahkan bagian individal(usually last carry is ignored)

Digit Extraction
Beberapa bagian digit dari angka dijadikan sebagai hash address.
Contoh :
x=14568. Jika kita Mengambil angka ke 1,3, dan 5, kita akan mendapatkan hashcode : 158.

Rotating hash
Gunakan hash mehod apa saja, lalu kita balik(angka perama menjad angka terakhir, dst.


Hashing table didalam block chain digunakan untuk  cryptocurrencies, yaitu sebuah teknologi membuat mata uang digital. Teknologi ini menggunakan kriptografi untuk keamanan yang membuatnya tidak dapat dipalsukan. transaksi dengan panjang bervariasi dijalankan melalui algoritma hashing yang diberikan, dan menghaslkan output dengan panjang yang tetap terlepas dari panjang transaksi input. Output adalah sebuah hash.


Tree dan binary tree

Tree adalah non linear data sructure yang mempunyai tingkatan dari data objek. seperti struktur organisasi, dll. data diubungkan dengan pointer.


Tree concept :

Root : Node di paling atas
Edge: Garis yang menghubungkan parent dengan child
Leaf: node yang tidak mempunyai anak
Siblings: node yang mempnyai parent yang sama
Degree: total subtree dari sebuah node
Height/depth: maksimum degree dari sebuah tree
jika ada garis yang menghubungkan p kepada q, p disebut ancestor dari q dan q adalah descendant dari p.

Binary tree adalah sebuah tree yang setiap node mepunyai 2 anak. Anaknya dibedakan menjadi left chld dan right child.






Tipe Binary tree:
Perfect Binary Tree : Binary tree yang semua level mempunyai depth yang sama.


Complete Binary Tree : binary tree yang kedalamannya sebesar n atau n-1 untuk beberapa n. Jadi tidak seperti PBT yang harus sama semuanya, melainkan boleh sama ataupun tidak (namun pada simpul kedua dari terakhir saja). Dan dalam penempatan simpulnya diutamakan yang sebelah kiri yang terpenuhi.


Skewed Binary Tree : binary tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.

Balanced Binary tree : bianry tree yang tinggi antara anak sebelah kiri dan kanannya hanya berselisih maksimal satu. PBT dan CBT juga merupakan binary tree yang seimbang.







Binary tree dapat diterapkan menggunaakan array maupun linked list
Array :
Index on array represents node number
Index 0 is Root node
Index Left Child is 2p + 1, where p is parent index
Index Right Child is 2p + 2
Index Parent is (p-1)/2





Linked List :


Expression Tree Concept




Menggunakan konsep matematika dalam penggunaan nya. Antara lain dalam penggunaan prefix, postfix dan infix.

Prefix : *+ab/-cde
Postfix : ab+cd-e/*
Infix : (a+b)*((c-d)/e)



Threaded binary tree adalah binary tree yang memiliki cara menunjuk pointer NULL yang berbeda dengan binary tree.


Binary tree tanpa threading:

Binary tree dengan menggunakan threading:

Terlihat perbedaan pointer NULL yang ada.


Ada 2 tipe threading:
1. Yang menggunakan threading 1 arah yang berarti masing masing pointer hanya menunjuk satu arah
2. Yang menggunakan threading 2 arah yang berarti masing masing pointer bisa menunjuk arah