Hash Table & Linked List Summary

Hash Table & Binary Tree

 Hashing
Hashing adalah sebuah teknik yang digunakan untuk mengidentifikasikan sebuah objek spesifik dari sebuah kelompok dari objek yang serupa. Contoh penggunaan hashing dalam kehidupan nyata :

  • Di perpustakaan, setiap buku diberikan sebuah nomor unik yang bisa digunakan untuk menentukan informasi tentang buku tersebut, seperti posisi pastinya di perpustakaan atau orang yang sedang meminjamkannya etc.

Hash Function
Sebuah hash function adalah sebuah fungsi yang bisa digunakan untuk memetakan sebuah data set dari ukuran yang berubah-ubah ke sebuah data set dari ukuran yang pasti, yang jatuh ke hash table. Nilai yang dikembalikan oleh sebuah hash function disebut hash values, hash codes, hash sums, atau hanya hashes.
Ciri-ciri hash function yang baik:

  1. Mudah untuk memetakan data, harus mudah untuk dipetakan dan harus tidak menjadi algoritme sendiri.
  2. Distribusi yang seragam, harus memberikan distribusi yang seragam terhadap hash table dan tidak menghasilkan pengelompokan.
  3. Sedikit tabrakan, tabrakan terjadi ketika sepasang elemen dipetakan ke hash value yang sama

Hash Table
Hash Table adalah sebuah data structure yang digunakan untuk menyimpan informasi. Informasi tersebut memiliki dua komponen utama, yaitu Key dan Value. Hash table menggunakan hash function untuk mengcompute sebuah index ke dalam sebuah array di mana sebuah elemen akan dimasukkan atau dicarikan.
https://www.hackerearth.com/practice/data-structures/hash-tables/basics-of-hash-tables/tutorial/



Blockchain
Blockchain adalah sebuah linked list yang mengandung data dan sebuah hash pointer yang menunjuk ke blok sebelumnya, sehingga menciptakan sebuah chain.  Hash pointer mirip dengan sebuah pointer, tetapi daripada hanya mengandung alamat dari blok sebelumnya, ia juga mengandung hash dari sebuah data dalam blok sebelumnya.
https://blockgeeks.com/guides/what-is-hashing/



Binary Tree
Sebuah binary tree adalah sebuah data structre yang hierarkis di mana setiap node memiliki paling banyak dua anak yang umumnya disebut dengan anak kiri dan anak kanan.’Setiap node mangandung tiga komponen:
  1. Pointer ke subtree kiri
  2. Pointer ke subtree kanan
  3. Data elemen

Node yang terletak di paling atas tree disebut dengan root.
https://www.studytonight.com/data-structures/introduction-to-binary-trees

Terminologi Umum
  • Root: Node  yang terletak di ujung atas tree
  • Parent: Setiap node (kecuali sebuah root) dalam sebuah tree terhubung dengan sebuah directed edge tepat dari satu node lainnya. Node ini disebut sebagai parent.
  • Child: Sebuah node yang terhubung langsung ke node lainnya ketika bergerak menjauhi root.
  • Leaf/External node: Node tanpa anak.
  • Internal node: Node dengan setidaknya satu children.
  • Depth of a node: Banyaknya edges dari root ke node.
  • Height of a node: Banyaknya edges dari node ke leaf paling dalam. Height dari tree adalah height dari root.

Tipe Binary Tree
  • Rooted Binary Tree: Memiliki root node dan memiliki paling banyak dua child anak
  • Full Binary Tree: Sebuah tree di mana setiap node memiliki antara 0 atau 2 anak
  • Perfect Binary Tree: Sebuah binary tree di mana interior node memiliki dua anak dan leaves memiliki depth dan level yang sama
  • Complete binary tree: Sebuah binary tree di mana setiap level, kecuali mungkin yang terakhir, diisi penuh, dan semua node berada di posisi paling kiri sebisa mungkin
  • Balanced binary tree: Sebuah binary tree disebut height balanced apabila ia memenuhi batasan berikut:
    1. Heights dari subtree kiri dan kanan berbeda paling banyak satu node
    2. Subtree kiri seimbang
    3. Subtree kanan seimbang
  • Degenarate tree: Sebuah tree di mana setiap parent node hanya memiliki satu child node. Bekerja seperti sebuah linked list.

Linked List

Linked list adalah sebuah data structure yang terdiri dari sebuah urutan rekaman data, di mana setiap rekaman data terdapat sebuah referensi ke rekaman selanjutnya dalam sebuah urutan data. Setiap rekaman dari sebuah data dalam linked list biasanya disebut dengan "element" atau "node". Bentuk paling sederhana dari sebuah node biasanya terdiri dari dua bagian, yaitu sebuah data dan referensi ke node selanjutnya yang biasanya ditulis dalam bentuk pointer. Dalam linked list, node paling pertama umumnya disebut dengan "head", sementara node selanjutnya atau node yang berada di posisi paling terakhir disebut dengan "tail".


Linked list terdiri dari banyak tipe, tapi yang akan disebut hanya dua tipe, yaitu:
  • Single Linked List, sebuah linked list di mana setiap nodes dibagi menjadi dua bagian yaitu, sebuah nilai integer, dan pointer ke node selanjutnya.
  • Double Linked List, sebuah linked list di mana setiap nodes dibagi menjadi tiga bagian yaitu, sebuah nilai integer, pointer ke node selanjutnya, dan pointer ke node sebelumnya.
Untuk membuat sebuah linked list, maka pertama-tama kita harus menetapkan sebuah struktur node untuk list tersebut. Misalkan, kita ingin membuat list integer,

Single Linked List
struct tnode{
          int value;
          struct tnode *next;
}*head, *tail;

Double Linked List
struct tnode{
          int value;
          struct tnode *next, *prev;
}*head, *tail;

Untuk memasukkan value baru, kita harus mengalokasikan sebuah node baru dan memberikan value kepadanya dan menyambungkan dengan linked list yang ada. Misal kita ingin menambahkan sebuah node baru di depan head,

Single Linked List
struct tnode *curr = (struct tnode *)malloc(sizeof(struct tnode));
curr->value = value;
curr->next = NULL;

if(head == NULL){
           head = tail = curr;
}
else{
           curr->next = head;
           head = curr;
}

Double Linked List
struct tnode *curr = (struct tnode *)malloc(sizeof(struct tnode));
curr->value = value;
curr->next = curr->prev = NULL;

if(head == NULL){
           head = tail = curr;
}
else{
           curr->next = head;
           head->prev = curr;
           head = curr;
}

Untuk meng-delete sebuah value, maka pertama kita harus mencari lokasi dari sebuah node yang menyimpan nilai dari value yang ingin kita delete, terus kita hilangkan, dan sambungkan linked list yang tersisa. Misalkan kita ingin menghilangkan sebuah value di head,

Single Linked List
struct tnode *curr = head;
if(curr == tail){
          curr = head = tail = NULL;
          free(curr);
}
else{
          head = head->next;
          free(curr);
}

Double Linked List
struct tnode *curr = head;
if(curr == tail){
          curr = head = tail = NULL;
          free(curr);
}
else{
          head = head->next;
          head->prev = NULL;
          free(curr);
}

Keuntungan dari linked list:
  • Dapat melakukan insertion dan/atau deletion data secara mudah.
  • Tidak perlu mendeklarasi size.
Kerugian dari linked list:
  • Untuk mengakses data harus bermulai secara urutan, jadi selalu mulai dari node head.
  • Terdapat size berlebihan yang tidak digunakan.


Kegunaan dari linked list:
  • Linked list bisa melakukan insertion dan deletion dari node apapun di lokasi manapun.
  • Digunakan dalam banyak algoritma untuk menyelesaikan masalah, ketika jumlah elemen yang disimpan tidak dapat diprediksi dan juga ketika akses secara berurutan dari elemen-elemen. 

Referensi:

Komentar

Posting Komentar

Postingan Populer