Hashing Tree

GSLC 10 Maret 2020

Hashing

Hashing adalah teknik utuk menyimpan dan mengambil key dengan cara cepat.

String character diubah menjadi value lebih pendek atau key yang menunjukkan string aslinya.

Hashing digunakan untuk index dan mengambil item di database karena lebih cepat mencari item menggunakan hashed key lebih pendek daripada menggunakan value aslinya.

Hashing dapat dikatakan sebagai konsep yang mendistribusikan key dalam array disebut hash table menggunakan fungsi yang sudah ditentukan yang disebut hash function.

Hash table adalah table array dimana kita menyimpan string asli. Index tablenya adalah hashed key, sementara valuenya adalah string asli.

Ukuran tabel hash biasanya beberapa urutan besarnya lebih rendah dari jumlah total string yang mungkin, sehingga beberapa string mungkin memiliki hash key yang sama.

Ada beberapa cara untuk fungsi hash:

- Mid-square.

Mengambil value tengah untuk mempresentasikan value sebuah key.

- Division.

Membagi string menggunakan modulus dari size table tersebut.

- Folding.

Membagi 2 value tiap key lalu ditambah. Jika hasilnya ada 3, ignore angka paling depan.

- Digit Extraction.

Digit yang sudah didefinisikan adalah hash addressnya.

- Rotating Hash.

Gunakan method hash apa saja (seperti division/mid-square method). Lalu melakukan rotasi. Rotasikan angkanya agar menjadi hash address baru.

Collision adalah ketika terjadi 2 hasil address yang sama. Cara menyelesaikannya adalah:

- Linear Probing. Mencari slot kosong selanjutnya dan menaruh stringnya disana.

- Chaining. Menaruh string di slot sebagai chained list menggunakan linked list.

Tree & Binary Tree

Tree adalah struktur data non-linear yang menunjukkan hubungan hirarki terhadap data object.

Root = Node paling atas.

Edge = Garis yang menyambung Parent ke Child.

Leaf = Node yang tidak mempunyai anak.

Sibling = Node yang mempunyai parent sama.

Degree = Total sub tree di node.

Height/Depth = Tinggi maksimal node di sebuah tree.

Binary tree adalah tree yang memiliki akar yang nodenya paling banyak punya 2 anak, kiri dan kanan.

Tipe-tipe Binary Tree:

- Perfect Binary Tree = Binary tree yang tiap levelnya memiliki depth sama.

- Complete Binary Tree = Binary tree yang tiap level, hampir semuanya terisi.

- Skewed Binary Tree = Binary tree yang tiap node hanya memiliki 1 anak

- Balanced Binary Tree = Binary tree yang leafnya tidak jauh dari root.