Hashtable dan Binary Tree

10 Maret 2020

Hashing adalah sebuah peng-imputtan data dengan fungsi yang spesial yaitu disebut dengan 'Hash Table' dengan pencarian dengan sebuah tektik dari sebuah kunci untuk mempercepat pencarian sesuai lokasi record yang telah tersimpan dari sebuah tabel.
Keunggulan yang dapat kita dapatkan dari hash table ini ada waktu untuk pengakses yang cepat, dan tiap penyimpanan yang dilokasi kan sesuai pada table penyimpanannya. Tetapi kebanyakan kasus dimana sering sekali ditemukan hash table yang tiap lokasi nya mempunyai angka hash(tabel) yang sama dimana hal ini dapat menyembabkan tabrakkan.
Operasi pada hash table yaitu:

1. Insert: peng-inputtan sebuah key maupun nilai
2. Find: peng-inputtan sebuah key, dimana akan terhubungkan dengan hash table tersebut
3. Remove: peng-inputtan sebuah key, dimana akan berhubungan dengan nilai table pada hashtable, kemudian penghapusan nilai yang sama dengan key akan terhapus
4. getIterator: memberitahu isi table satu per satu, dengan memeriksa nilai tiap tablenya

Untuk case collusion dimana ada dua angka yang dimasukkan ke dalam fungsi hash menghasilkan nilai yang sama.
Contoh:
Input angka 5,25;
Hash(5) = 5%20 = 5;
Hash(25)=25%20=5;
Disana kita dapat melihat bahwa dari dua angka tersebut menghasilkan nilai yang sama, ini tentu akan menyebabkan tabrakkan. Disini juga kita dapat mengatasi hal ini dengan 2 cara:
    1. Linear Probing
    Dimana ini akan mengecek terus tempat yang belum terisi dan akan memasukkan nya kedalam.
    2. Quadratic Probing
    Penanganannya mirip dengan cara linear probing, hanya pencariannya tidak satu-satu, tetapi quadratic(12, 22, 32, 42, ...)

Binary Search Tree

Binary Search Tree atau dapat disebut dengan (BST) biasanya dapat ditemukan ciri-ciri seperti:

1. Tidak ada node yang tidak memiliki nilai
2. Nilai node cabang kiri lebih kecil daripada nilai node cabang kanan
3. Nilai node cabang kanan lebih besar daripada nilai node cabang kiri
4. Cabang kiri maupun kanan dapat memiliki anak(leaf) secara rekursif