Hashing
Adalah aktivitas untuk mengubah
suatu objek menjadi serangkaian angka / karakter / lain sebagainya yang lebih
singkat yang tetap merepresentasikan objek aslinya. Hashing biasa dipake buat
simpen atau ambil objek yang ada dalam sebuah database karena lebih cepat buat
cari objek yang di hash.
Contoh :
Misalkan ada mahasiswa yang
memiliki IPK. Untuk mengubah IPK mahasiswa X menjadi Y, cukup ubah A[X] = Y.
Sedangkan untuk mencari IPK mahasiswa X, cukup return A[X].
Ini adalah konsep hash table.
Key-Value
Key adalah hal yang menjadi indeks,
sedangkan value adalah nilai yang terasosiasi dengannya. Misalnya nama
mahasiswa adalah key, dan IPK nya merupakan value. Key dan value tidak harus
berupa string. Konsep ini berhubungan erat dengan hash table.
Hash Function
Metode penting dalam membuat sebuah fungsi hash :
1. Mid-square
2. Division
3. Folding
4. Digit
Extraction
5. Rotating
Hash
Fungsi hash diharapkan memiliki kriteria berikut :
1. Untuk dua
key yang sama, hasil hashnya selalu sama
2. Memiliki
kompleksitas rendah
3. Meminimalkan
collision
Collision
Beberapa string mungkin memiliki nilai hash yang sama.
Bagaimana cara menanganinya ?
1. Closed
hashing
Contohnya linear probing. Linear probing mencari slot
kosong baru untuk menyimpan objek disana.
2. Open
hashing
Contohnya chaining. Membuat array menjadi “array of
linked list”, misal kita beri nama ‘A’. Setiap elemen pada linked list A[i]
menyimpan pasangan key dan value dan memiliki hash key i.
Binary Tree
Tree adalah struktur data non-linear yang menggambarkan
hubungan hirarkis antara elemen-elemennya. Binary Tree adalah tree yang
memiliki syarat bahwa tiap node hanya memiliki maksimal dua cabang dan kedua
cabang itu terpisah (kiri dan kanan).
Contoh Binary Tree :
1. Perfect
Binary Tree
Setiap daun memiliki kedalaman yang sama
2. Complete
Binary Tree
Disetiap level kecuali yang terakhir, terisi memenuhi
titik terkiri secara teratur.
3. Skewed
Binary Tree
Setiap node memiliki maksimal satu cabang.
Komentar
Posting Komentar