Hashing, Hash Table & Binary Tree

HASHING & HASHTABLE

Hashing merupakan Data Structures yang menggunakan function yang biasa disebut Hash Function, Hashing digunakan karena dapat mengakses alamat lebih cepat dengan di tandai menggunakan key.

Contoh Gambar :

Gambar disamping salah satu contoh hashing dengan function x % 10. Jika salah satu value dari list disamping 19, maka hashing akan menyimpan value tersebut di Hash Table ke 9.

Lalu bagaimana dengan String?? Akan dicontohkan dibawah ini.



Yang pertama kita buat terlebih dahulu struct atau tables yang nanti akan menampung value. Seperti Linked List, disini juga ada Head dan Tail.

struct Node{
char name[100];
char age[100];
char key[205];

Node *next;
} *tableHead, *tableTail;

lalu ada Create Node, seperti Linked List, function ini menambah data baru dengan memesan memori untuk si data baru ini.

Node *createNode(char name[100], char age[100]){
Node *temp = (Node *)malloc(sizeof(Node));
strcpy(temp->name, name);
strcpy(temp->age, age);
strcpy(temp->nim, "1");
sprintf(temp->key, "%s%s", temp->name, temp->age);

temp->next = NULL;
return temp;
}

Apa yang dimaksud bagian sprintf itu?? Itu merupakan bagian kita membuat key untuk string, untuk formatnya yaitu sprintf(tujuan, apa yang ingin dimasukkan). Contoh untuk bagian tersebut yaitu : Misalkan temp -> name = "Alpha" dan temp -> age = 10 maka hasil di temp -> key = Alpha10.

Function utama kita pada pembahasan kali ini yaitu Hash Function, sebagai berikut :

int hashFunction(char key[205]){
int len = strlen(key);
int total = 0;
for(int i=0;i<len;i++){
total += key[i]*i;
total %= 100;
}
return total;
}

Apa maksudnya diatas ini?? Nah, function di atas ini saya contohkan dengan menggunakan ASCI dari String untuk mencari value di Hash Table atau disebut Hash Index nya. Misalkan pada String "Alpha10", jika kita ikuti function di atas, maka total awal = 0, lalu ditambahkan ASCI dari "A" yaitu  65 dikali loopingannya yaitu 0. Maka value "total" di loopingan ke-0 yaitu 0, pada loopingan ke-1, mak value "total" sebelumnya yaitu 0 ditambah dengan ASCI "l" yaitu 108 dikali 1, maka hasilnya yaitu 108, dan dimodulo 100 menjadi 8, dst sampai key habis.

Untuk peletakan nya pada Hash Table, saya contohkan dengan Push Tail

void pushTail(int hashIndex, Node *newNode){
if(tableHead[hashIndex] == NULL){
tableHead[hashIndex] = tableTail[hashIndex] = newNode;
}else{
tableTail[hashIndex]->next = newNode;
tableTail[hashIndex] = newNode;
}
}

void insert(Node *newNode){
int hashIndex = hashFunction(newNode->key);
pushTail(hashIndex, newNode);
}

Berikut merupakan cara memasukkan data tersebut ke Table, dengan mencari Hash Function dengan Hash Index.

BINARY TREE

Dalam Tree normal, setiap node boleh memliki berapapun jumlah anak. Binary Tree merupakan tree spesial dalam data structure dimana setiap node dengan anak maksimum 2, anak kiri dan anak kanan.

Disamping merupakan contoh gambar dari Binary Tree dengan anak 0, 1, dan 2.

Binary Tree memliki beberapa jenis, yaitu Strictly Binary Tree dan Complete Binary Tree.







1. Strictly Binary Tree

Dalam Binary Tree, setiap node boleh memliki maksimum 2 anak, Namun dalam Strictly Binary Tree, setiap node harus memiliki 2 anak atau tidak memliki anak sama sekali, artinya setiap internal node harus memliki tepat 2 anak. Biasanya Strictly Binary Tree bisa juga disebut Full Binary Tree atau Proper Tree atau 2-Tree, dan digunakan untuk mewakili ekspresi matematik.

2. Compete Binary Tree

Dalam Complete Binary Tree, semua nodes harus memiliki 2 anak dan setiap level Complete Binary Tree harus ada nodes dengan jumlah 2 pangkat level. Jadi misalkan pada level 3 harus ada 8 nodes, karena 2 pangkat 3 = 8.

Sekian teori-teori mengenai Binary Tree dari saya, terima kasih.