Weekly Report Data Structure (Week 4)

Materi minggu ini materi nya adalah Hashing dan Binary Tree. Hashing adalah metode yang digunakan untuk mencari dan memasukan data dengan cepat ke database. Konsep yang saya dapatkan itu hashing menggunakan array dan linked list sekaligus. Sehingga blok memori array akan digunakan sebagai head bagi linked list nya nanti.

Contoh syntax untuk hashing:

#include<stdio.h>

#include<string.h>

#include<stdlib.h>

#include<stdbool.h>

#define SIZE 20

struct DataItem{

int data;

int key;

};

struct DataItem* hashArray[SIZE];

struct DataItem* dummyItem;

struct DataItem* item;

int hashcode(int key){

return key % SIZE;

}

struct DataItem *search(int key){

// get the hash

int hashIndex = hashcode(key);

// move in array until an empty

while(hashArray[hashIndex] != NULL){

if(hashArray[hashIndex]->key == key){

return hashArray[hashIndex];

}

// go to next cell

hashIndex++;

// wrap around the table

hashIndex %= SIZE;

}

return NULL;

}

void insert(int key, int data){

struct DataItem *item = (struct DataItem*) malloc (sizeof(struct DataItem));

item->data = data;

item->key = key;

// get the hash

int hashIndex = hashcode(key);

// move in array untul an empty or deleted cell

while(hashArray[hashIndex] != NULL && hashArray[hashIndex]->key != -1){

// go to next cell

hashIndex++;

// wrap around the table

hashIndex %= SIZE;

}

hashArray[hashIndex] = item;

}

struct DataItem* deleteHash(struct DataItem* item){

int key = item->key;

// get the hash

int hashIndex = hashcode(key);

// move in array until an empty

while(hashArray[hashIndex] != NULL){

if(hashArray[hashIndex]->key == key){

struct DataItem* temp = hashArray[hashIndex];

// assign a dummy item at deleted position

hashArray[hashIndex] = dummyItem;

return temp;

}

// go to next cell

++hashIndex;

// wrap around the table

hashIndex %= SIZE;

}

return NULL;

}

void display(){

int i = 0;

for(i = 0; i < SIZE; i++){

if(hashArray[i] != NULL){

printf(" (%d, %d)", hashArray[i]->key, hashArray[i]->data);

} else {

printf("~~");

}

printf("\n");

}

int main(){

dummyItem = (struct DataItem*) malloc (sizeof(struct DataItem));

dummyItem->data = -1;

dummyItem->key = -1;

insert(1, 20);

insert(2, 70);

insert(42, 80);

insert(4, 25);

insert(12, 44);

insert(14, 32);

insert(17, 11);

insert(13, 78);

insert(37, 97);

display();

item = search(37);

if(item != NULL){

printf("Element found: %d\n", item->data);

} else {

printf("Elemert not found\n");

}

deleteHash(item);

display();

item = search(42);

if(item != NULL){

printf("Element found: %d\n", item->data);

} else {

printf("Elemert not found\n");

}

display();

item = search(13);

if(item != NULL){

printf("Element found: %d\n", item->data);

} else {

printf("Elemert not found\n");

}

Pada hashing terdapat banyak cara untuk menkonstruksi hash function yaitu, Mid-square, division, folding, digit extraction, dan rotating hash.

Hashing sekarang banyak digunakan di dalam cryptocurrency seperti Bitcoin, karena transaksi akan diambil sebagai input yang nanti nya akan menghasilkan output berupa string dengan panjang yang tetap. Pada bitcoin algoritma hashing yang digunakan adalah SHA-256 (Secure Hashing Algorithm 256), yaitu algoritma yang menghasilkan output dengan panjang yang sama yaitu 256 bit, dengan panjang input berapapun.

Tree adalah data structure yang non-linear, tree memiliki banyak bagian, bagian paling atas dari tree disebut dengan root yang berada di level 0. Garis yang menghubungkan antar node disebut edge, dan node yang tidak memiliki anak disebut dengan leaf.

Binary tree adalah rooted tree yang setiap node nya memiliki paling banyak 2 anak.

Tipe Binary tree:

· PERFECT Binary tree