Hashing Table & Binary Trees


Hashing Table & Binary Trees

Hashing Table

Adalah data structure mengelompokkan objek dalam kelompok sama. Dalam hashing sebuah string panjang akan di ubah ke dalam key yang merupakan index pada hash table, menggunakan hash function untuk mendapatkan key tersebut. Misalnya untuk mendapatkan informasi mahasiswa kita hanya perlu NIM, karna kata kunci yang banyak maka diperlukan hashing agar lebih cepat.

Intinya Hashing adalah mentransformasi string panjang menjadi sebuah key dan index untuk mencari suatu infromasi di database.

Hash Function
  • Mid-square

Dalam teknik ini untuk mendapatkan key-nya,dilakukan pangkat dua pada valuenya kemudian kita bisa mengambil nilai tengah dari hasilnya. Teknik ini memiliki kemungkinan collision yang kecil karena key yang dihasilkan cukup unik. Overflow bisa terjadi misalnya pada perpangkatan 6 digit menjadi 12 digit, maka perlu menggunakan tipe data long long int atau string.  
Contoh: kita ambil 4 digit angka yaitu 1234.
            Kuadrat dari 1234 adalah 1522756.
            Kita ambil 4 digit tengahnya yaitu 2275 yang akan menjadi key barunya.
            Langkah ini dapat dilakukan terus demi mendapatkan key yang unik.
  • Division

Ini adalah teknik yang paling sering digunakan, yaitu membagi string dengan operasi modulus sesuai besar memori atau hash table yang telah ditentukan.
Contoh: diberikan ukuran hash table 5, dengan nilai 22.
            Maka 22%5 = 2, dihasilkan key atau index hash tablenya 2.

  • Folding

Dalam teknik ini kita memecah string per bagian kemudian ditambahkan untuk mendapatkan key-nya.
Contoh: diberikan nilai 1234.
            Dipecah menjadi 12 dan 34 kemudian ditambahkan.
            12 + 34 = 46, maka key nya adalah 46.
  • Digit Extraction

Teknik ini mengambil digit yang sudah ditentukan menjadi keynya.
Contoh: diberikan digit 1234.
            Diambil digit ke 1 dan 3 maka keynya menjadi 13.
  • Rotating Hash

Teknik ini dapat menggunakan ke-4 teknik diatas, kemudian dilakukan shifting untuk mendapatkan key yang baru.
Contoh: keynya 21121 menjadi 12112 setelah di shift.

Collision

Seperti artinya yaitu tabrakan, dimana kita mau memasukkan sejumlah string tetapi ada beberapa string yang memiliki hash key yang sama. Ada 2 cara untuk mengatasi collision, yaitu:
  • Linear Probing

Melakukan searching untuk mendapatkan slot selanjutnya yang kosong lalu menempatkannya disana.

  • Chaining

Cara ini sama seperti konsep linked list jadi string yang memiliki hash key sama akan diletakkan pada satu slot yang sama namun saling terhubung.

void put(char key[], int value){
            Data *curr = newData(key, value);
            int index = getHash(key) % TABLE_SIZE;
            if(head[index] == NULL){
                        head[index] = curr;
            }
            else{
                        Data *temp = head[index];
                        while(temp->next != NULL){
                                    temp = temp->next;
                        }
                        temp->next = curr;
            }
}

Bisa dilihat bahwa konsepnya sama persis dengan single linked list hanya menambahkan index untuk proses maping atau peletakkan pada hash tablenya.

Contoh implementasi hashtable menggunakan teknik divison:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

#define TABLE_SIZE 15

struct Data{
            char key[100];
            int value;
            Data *next;
}*head[100];

Data *newData(char key[], int value){
            Data *temp = (Data*)malloc(sizeof(Data));
            strcpy(temp->key, key);
            temp->value = value;
            temp->next = NULL;
           
            return temp;
}

int getHash(char key[]){
            int hash = 0;
            for(int i=0; i<strlen(key); i++){
                        hash += key[i];
            }
            return hash;
}

void put(char key[], int value){
            Data *curr = newData(key, value);
            int index = getHash(key) % TABLE_SIZE;
            if(head[index] == NULL){
                        head[index] = curr;
            }
            else{
                        Data *temp = head[index];
                        while(temp->next != NULL){
                                    temp = temp->next;
                        }
                        temp->next = curr;
            }
}

void display(){
           
            for(int i=0; i<TABLE_SIZE; i++){
                        if(head[i] != NULL){
                                    Data *temp = head[i];
                                    while(temp != NULL){
                                                printf(" (%s, %d) -> ", temp->key, temp->value);
                                                temp = temp->next;
                                    }
                                    printf("\n");
                        }
                        else{
                                    printf(" ~~ \n");
                        }
            }
            printf("\n");
}

Data *get(char key[]){
            int index = getHash(key) % TABLE_SIZE;
            Data *temp = head[index];
            while(temp != NULL && strcmp(key, temp->key) != 0){
                        temp = temp->next;
            }
            return temp;
}

int main(){
           
            put("A", 20);
            put("TEST", 15);
            put("B", 10);
            put("C", 25);
            display();
            Data *found = get("C");
            if(found == NULL) printf("No data found\n");
            else printf("%s %d\n", found->key, found->value);
           
            return 0;
}

Pada implementasi diatas saya melakukan hashing dengan menambahkan ASCII dari string kemudian untuk mendapatkan keynya saya melakukan teknik divison dengan modulus sesuai ukuran hash table yang sudah ditentukan yaitu 15. Saya juga membuat kondisi collision yaitu dengan chaining, apabila dijalankan akan menampilkan A menunjuk TEST.

Blockchain

Hash adalah fungsi mengubah input menjadi output yang terenkripsi yang sangat penting dalam manajemen blockchain dan cryptocurrency. Untuk mencegah suatu data dibobol atau dilihat orang lain maka diperlukan suatu kode unik, contoh nya pada chatting dimana teks chattingan akan dienkripsi emnggunakan suatu kode yang hanya bisa diakses kedua pihak. Contoh: SHA-256, fungsi satu arah yang mengubah teks dengan panjang apa pun menjadi string 256 bit, ini adalah fungsi hashing kryptografi yang outputnya hanya memberi tahu sedikit inputnya. Ini sangat berguna dalam transaksi misalnya bitcoin.


Binary Tree

Adalah data structure pohon dimana memiliki dua node anak, biasanya dibedakan anatara kiri dan kanan. Node yang memiliki anak disebut parent dan node teratas disebut root.

  • Full Binary Tree

Memiliki 2 child setiap node dan memiliki panjang path yang sama.



  • Complete Binary Tree

Memilik 0 atau 2 child setiap node dan boleh memiliki panjang path yang berbeda.
  
  • Skewed Binary Tree

Memiliki 1 child setiap node.

        
  • Binary Search Tree

Memiliki data yang terurut unutk memudahkan pencarian kembali data tersebut.
  
Operasi pada binary tree terdiri dari:
  1. Create : membuat binary tree baru.
  2. Clear : mengosongkan binary ree.
  3. Empty : memeriksa kekosongan bianry treee.
  4. Insert : memasukkan node baru ke tree.
  5. Find : mencari root, parent, dan child pada tree.
  6. Update : mengubah isi dari node yang ditunjuk.
  7. Retrieve : mengetahui isi dari node yang ditunjuk.
  8. Delete Sub : menghapus suatu sub yang ditunjuk.
  9. Characteristic : mengetahui karakteristik dari tree seperti size, height, dan length.
  10. Traverse : menjalani masing-masing node pada tree sekali.


 Kesimpulan
Keuntungan hashing adalah membandingkan dua file tanpa harus melihat isi dari file tersebut, membandingkan nilai hash yang dihitung sehingga pemilik bisa mengetahui jika mereka berbeda.

Keuntungan binary tree adalah susunan data structure yang lebih baik dan searching yang cepat karena O(logn) dan bisa melakukan traverse untuk mendapatkan data yang terurut.


Comments

Post a Comment

Popular posts from this blog

Heap & Tries

Image
Heap Heap adalah data structure tree yang terdiri dari 3 properti heap, yaitu: 1. Min Heap: setiap node memiliki value yang lebih kecil dari childnya (value terkecil di root). 2. Max Heap: setiap node memiliki value yang lebih besar dari childnya (value terbesar di root). 3. Min-Max Heap: terdiri dari level dan setiap level memiliki heap yang berbeda. Heap biasa direpresentasikan dalam bentuk array sehingga lebih mudah di digunakan. Index array pada heap dimulai dari 1, dan setiap melakukan insert akan dimasukkan ke index paling akhir. Untuk mengetahui index dari parent, left child, dan right child digunakan: Parent(x) = x/ 2 left-child(x) = 2 * x right-child(x) = 2 * x + 1 Min Heap https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm Max Heap https://www.tutorialspoint.com/data_structures_algorithms/heap_data_structure.htm Min-Max Heap https://www.google.com/url?sa=i&url=https%3A%2F%2Fstackoverflow.com%2Fques
Read more

Linked List II

Image
 Linked List II Circular Singly Linked List Adalah linked list dimana semua node terhubung oleh satu pointer next saja dan membentuk sebuah loop satu arah dan tidak memiliki NULL pada akhir dari node. Node mana saja bisa menjadi starting point karena dia hanya berhenti ketika node yang sama terulang.  https://static.javatpoint.com/ds/images/circular-singly-linked-list.png Doubly Linked List Adalah linked list yang terdiri dari sekumpulan data yang memiliki dua tangan penghubung ke data sebelumnya dan ke data selanjutnya. Setiap ujung atau tail dari data adalah NULL dan dapat dijalankan dua arah karena memiliki dua penunjuk yaitu previous dan next. Jika kita ingin insert data atau delete data kita harus mengubah kedua pointer yang menunjuk ke data sebelum dan selanjutnya. https://www.studytonight.com/data-structures/images/doubly-linked-list-1.png Circular Doubly Linked List Adalah linked list yang mirip dengan Circular Singly Linked L
Read more

AVL Tree

Image
AVL Tree AVL Tree adalah singkatan untuk Adelson-Velskii and Landis, AVL adalah bagian atau subtype dari Binary Search Tree (BST). Konsep AVL Tree adalah selisih dari height kiri dan kanan subtree tidak boleh lebih dari 1. AVL tree harus selalu balance, sehingga setiap melakukan operasi akan di cek selisih height kiri dan kanan subtree jika lebih dari 1 maka disebut violation. Berikut adalah contoh dari violation, jika dilihat height dari subtree kiri 17 adalah 2 dan subtree kananya 0 maka selisihnya 2 ( violation ). https://www.google.com/url?sa=i&url=http%3A%2F%2Fivansrarudiandi.blogspot.com%2F2016%2F05%2Favl-tree.html&psig=AOvVaw0u6xLhAVqqwO6eNKpO-PM4&ust=1588413552562000&source=images&cd=vfe&ved=0CAIQjRxqFwoTCMih2u6zkukCFQAAAAAdAAAAABAE AVL Tree Rotation Seperti yang telah saya katakan bahwa setiap operasi kita perlu mengecek balance nya, jika tidak balance maka kita harus membuatnya balance dengan operasi rotation. Terdapat 2 jenis rot
Read more