MORENO

Hash

Hashing adalah teknik yang digunakan untuk menyimpan dan mengambil keys dengan cepat.

Dalam hashing string akan diubah menjadi string yang lebih pendek sebagai keys (kunci kata) dari string originalnya.

Hashing digunakan untuk mengindeks dan mengambil data dalam database karena teknik mencari kata kunci ini lebih cepat daripada harus mencari langsung data originalnya.

Hashing juga dapat disebut sebagai konsep mendistribusikan keys dalam array yang disebut hash table menggunakan fungsi yang telah ditentukan yang disebut hash function.

Hash Table

Hash Table adalah tabel (array) tempat menyimpan string original.

Index untuk array pada hash table disebut hashed key, sementara value adalah string original dari key tersebut.

Beberapa string bisa saja memiliki keys yang sama.

Hash Function

berikut beberapa method untuk meng-hash keys  dari string:

• Mid-square
• Division
• Folding
• Digit Extraction
• Rotating Hash

Mid-square:
Value dari string dipangkatkan, kemudian sebagian angka dari hasil pangkat tersebut dipakai sebagai key.

Contoh:
value = 1254; hasil pangkat = 1572516; hash = 725

Division:
String/identifier dimodulo dengan suatu integer (biasanya memakai bil. prima, size dari tabel, atau size memori yang digunakan).

Contoh:
Misal kita punya string berupa "ABCD". Jumlahkan ASCII dari string tersebut dan bagi dengan salah satu angka prima misalnya 2.
(65 + 66 + 67 + 68) / 2 = 266 / 2 = 133
 
Folding:
Pisahkan string/identifier ke beberapa bagian, kemudian jumlahkan bagian-bagian tersebut.

Contoh:
Misal kita memiliki integer 6721, pisahkan menjadi 2 bagian yaitu 67 dan 21, kemudian jumlahkan menjadi 83.

Digit Extraction:
Mengambil beberapa digit dari angka yang diberikan dan digabungkan menjadi key.

Contoh:
Misal kita memiliki integer 1435462. Ambil digit ke-1, ke-3, dan ke-5 maka kita mendapat 134

Rotating Hash:
Gunakan method manapun untuk mendapat hash code/address kemudian putar balik angka yang telah didapat untuk mendapat hash code/address yang baru.

Contoh:
Misal kita menggunakan method division, putar balik hash yang didapat dari 133 menjadi 331

Collision

Collision terjadi saat beberapa string menggunakan hash key yang sama.
Cara yang biasa digunakan untuk mengatasinya adalah:

• Linear Probing : Cari slot kosong berikutnya dan masukkan kesana
• Chaining : Memasukkan string sebagai list berantai (linked list)

Linear probing tidak akan efektif jika collision berjumlah banyak. Kekurangan lainnya adalah saat melakukan pencarian, contoh: kita telah menginput hash key untuk data yang dicari, namun karena collision maka hash key tersebut bukan menunjuk string yang kita inginkan. Oleh sebab itu kita terpaksa melakukan iterate hingga mendapat string yang dicari.

Untuk chaining, kita hanya perlu melakukan iterate untuk mencari string yang diinginkan.

Tree

Tree adalah struktur data non-linear yang menggambarkan hubungan hierarki antara objek data.

Untuk penggambaran, node pada tree tidak perlu digambarkan berdekatan dan boleh ditaruh dimana saja. Node pada tree dihubungkan dengan pointer.

Konsep Tree

• Node teratas disebut root
• Garis yang menyambungkan parent dengan child  disebut edge
• Nodes yang tidak memiliki child disebut leaf
• Nodes dengan parent yang sama disebut sibling 
• Total sub-tree suatu node disebut degree
• Maximum degree suatu node pada tree disebut height / depth
• Node yang berada diatas node lain dan saling terhubung disebut ancestor
• Node yang berada dibawah node lain dan saling terhubung disebut descendant

Binary Tree

Binary tree adalah struktur data rooted tree dimana masing-masing node paling banyak memiliki dua anak. (left child dan right child)

Tiper-tipe binary tree:

• Perfect Binary Tree
• Complete Binary Tree
• Skewed Binary Tree
• Balanced Binary Tree

Perfect binary tree: binary tree dimana tiap level memiliki depth yang sama.

Complete binary tree : binary tree dimana setiap level kecuali yang terakhir, terisi penuh, dan semua anak node pada level terakhir harus menempati titik kiri.

Skewed binary tree : binary tree dimana setiap node setidaknya memiliki satu anak.

Balanced binary tree : jarak setiap leaf dengan root adalah sama.

Implementrasi binary tree pada array :

• Index untuk node root = 0
• Index left child = 2p + 1 (p = index parent)
• Index right child = 2p + 2 (p = index parent)
• Index parent = (p - 1) / 2

Threaded Binary Tree

Threaded Binary Tree sama saja dengan binary tree hanya saja berbeda dalam cara penyimpanan pointer NULL. 

Ruang node yang terbuang karena menyimpan NULL dapat dipakai secara lebih efisien.

Ruang tersebut dapat dipakai untuk menyimpan pointer ke in-order predecessor dan in-order successor (pointer-pointer ini disebut thread).