Hash Table


Hash Table

hash table adalah struktur data uang didesign menggunakan sebuah function baru ayng digunakan untuk mempetakan value dengan memberikan sebuah index yang unik(key) supaya mempercepat pencarian elemen. Biasanya dalam programming, Hash table menggunakan array dalam aksesnya.

Beberapa tipe Pembuatan key

  1. Middle-Square
    Mengambil key dengan cara mengambil value yang ada di tengah untuk menjadikan dia sebagai key
  2. Division(Paling sering dipakai)
    menentukan key dari hasil sisa bagi angka tersebut dengan suatu angka
  3. Digit Extraction
    mengambil ke dengan menentukan digit yang akan diambil.
    Contoh : (ditentukan bahwa akan mengambil digit ke 1,3,5)
    x = 12345
    maka keynya = 1,3,5
  4. Rotating Hash
    mengambil key dengan menukar posisi dari suatu value
    Contoh : x = 12345
    maka keynya 54321

Praktek Dalam Pembuatan Struktur Data Dengan Konsep Hash

Dari beberapa cara pembuatan key yang sudah saya sebutkan di atas, saya akan mencontohkan menggunakan pengambilan key division. Karena menurut saya teknik division lebih mudah dan juga sudah cukup mengelompokan value yang akan diberikan.

Chaining

Data yang di store akan saya buatkan array 1 dimensi dengan max data 20. Setiap index bisa diisi dengan berbagai macam data lagi. Dapat saya simulasikan dengan foto dibawah ini (Sumber BinusMaya)

Chaining yang akan saya contohkan menggunakan single linked list(Sumber : Kodingan training Asisten Labolatorium NAR 20-1).

Mulai dengan membuat struct. Dalam kasus ini saya hanya memasukan 1 data saja.

setelah itu buat table dengan array of pointer node.

variable SIZE sudah saya dideklarasi di preprossesornya

supaya tidak error, inisiasi semua index di table dengan null

setelah itu hash key dengan membaginya dengan SIZE(teknik division)

Lalu berikut adalah cara untuk memasukan datanya. Konsep yang saya pake adalah single linked list

Penjelasan : 
Setelah memory sudah dialokasi dengan fungsi newNode, maka linked list akan di 'tempel' pada table yang ingin dipakai.

Demikian penjelasan saya mengenai hash table.
Sumber : PPT Binus maya, https://www.geeksforgeeks.org/index-mapping-or-trivial-hashing-with-negatives-allowed/ , Kodingan training Asisten Labolatorium NAR 20-1

Binary Search Tree

Binary Search Tree adalah sebuah struktur data yang menerapkan konsep 'pohon' dengan memiliki root dan subtreenya. sebuah root akan memiliki 2 subtree yaitu left and right. value di kiri subtree akan lebih kecil dari value di subtree yang ada di kanan.

Keuntungan BST

  • Pencarian data lebih cepat dari pada linear seacrh (Ologn).
  • Algoritma yang simple dan tidak rumit
  • Data lebih terstruktur
Implementasinya dalam koding c

berikut adalah source code untuk fungsi insert data dalam bst

struct Node{
int value; 
struct Node *left, *right; 
};

struct Node{
int value; 
struct Node *left, *right; 
};

struct Node *createNode(int value){
struct Node *temp = (struct Node*)malloc(sizeof(struct Node));
temp->value = value; 
temp->left = NULL;
temp->right = NULL; 
return temp; 
}

struct Node *insertNode(struct Node *root , int value){
if(root == NULL){
return createNode(value); 
}
else if(root->value < value){
root->right = insertNode(root->right, value); 
}
else if(root->value > value){
root->left = insertNode(root->left, value); 
}else{
printf("Value already exists"); 
}
return root; 
}

Comments

Post a Comment