Hash Table

     Hash Table adalah sebuah struktur data yang terdiri atas sebuah tabel dan fungsi yang bertujuan untuk memetakan nilai kunci yang unik untuk setiap record (baris) menjadi angka (hash) lokasi record tersebut dalam sebuah tabel.

Keunggulan dari struktur hash table ini adalah waktu aksesnya yang cukup cepat, jika record yang dicari langsung berada pada angka hash lokasi penyimpanannya. Akan tetapi pada kenyataannya sering sekali ditemukan hash table yang record-recordnya mempunyai angka hash yang sama (bertabrakan).

     Pemetaan hash function yang digunakan bukanlah pemetaan satusatu, (antara dua record yang tidak sama dapat dibangkitkan angka hash yang sama) maka dapat terjadi bentrokan (collision) dalam penempatan suatu data record. Untuk mengatasi hal ini, maka perlu diterapkan kebijakan resolusi bentrokan (collision resolution policy) untuk menentukan lokasi record dalam tabel. Umumnya kebijakan resolusi bentrokan adalah dengan mencari lokasi tabel yang masih kosong pada lokasi setelah lokasi yang berbentrokan.

    Operasi Pada Hash Tabel

Ø  insert: diberikan sebuah key dan nilai, insert nilai dalam tabel

Ø  find: diberikan sebuah key, temukan nilai yang berhubungan dengan key

Ø  remove: diberikan sebuah key,temukan nilai yang berhubungan dengan key, kemudian hapus nilai tersebut

Ø  getIterator: mengambalikan iterator,yang memeriksa nilai satu demi satu

      Struktur dan Fungsi pada Hash Tabel.

Hash table menggunakan struktur data array asosiatif yang mengasosiasikan record dengan sebuah field kunci unik berupa bilangan (hash) yang merupakan representasi dari record tersebut. Misalnya, terdapat data berupa string yang hendak disimpan dalam sebuah hash table. String tersebut direpresentasikan dalam sebuah field kunci k.

Deklarasi utama hash tabel adalah dengan struct, yaitu:

typedef struct hashtbl {

hash_size size;

struct hashnode_s **nodes;

hash_size (*hashfunc)(const char *);

} HASHTBL;

Anggota simpul pada hashtbl mempersiapkan penunjuk kepada unsur pertama yang terhubung dengan daftar. unsur ini direpresentasikan oleh struct hashnode_:

struct hashnode_s {

char *key;

void *data;

struct hashnode_s *next;

};

Inisialisasi

  Deklarasi untuk inisialisasi hash tabel seperti berikut:

HASHTBL *hashtbl_create(hash_size size, hash_size

(*hashfunc)(const char *))

{

HASHTBL *hashtbl;

if(!(hashtbl=malloc(sizeof(HASHTBL)))) return NULL;

free(hashtbl);

return NULL;

}

hashtbl->size=size;

if(hashfunc) hashtbl->hashfunc=hashfunc;

else hashtbl->hashfunc=def_hashfunc;

return hashtbl;

}

 Cleanup

Hash Tabel dapat menggunakan fungsi linked lists untuk menghapus element

atau daftar anggota dari hash tabel .

Deklarasinya:

void hashtbl_destroy(HASHTBL *hashtbl)

{

hash_size n;

struct hashnode_s *node, *oldnode;

for(n=0; n<hashtbl->size; ++n) {

node=hashtbl->nodes[n];

while(node) {

free(node->key);

oldnode=node;

node=node->next;

free(oldnode);

}

}

free(hashtbl->nodes);

free(hashtbl);

}

Menambah Elemen Baru

Untuk menambah elemen baru maka harus menentukan ukuran pada hash tabel. Dengan deklarasi sebagai berikut:

int hashtbl_insert(HASHTBL *hashtbl, const char *key, void

*data)

{

struct hashnode_s *node;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

Penambahan elemen baru dengan teknik pencarian menggunakan linked lists

untuk mengetahui ada tidaknya data dengan key yang sama yang

sebelumnya sudah dimasukkan, menggunakan deklarasi berikut:

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) {

node->data=data;

return 0;

}

node=node->next;

}

Jika tidak menemukan key yang sama, maka pemasukan elemen baru pada

linked lists dengan deklarasi berikut:

if(!(node=malloc(sizeof(struct hashnode_s)))) return -1;

if(!(node->key=mystrdup(key))) {

free(node);

return -1;

}

node->data=data;

node->next=hashtbl->nodes[hash];

hashtbl->nodes[hash]=node;

return 0;

}

Menghapus sebuah elemen

Untuk menghapus sebuah elemen dari hash tabel yaitu dengan mencari nilai hash menggunakan deklarasi linked list dan menghapusnya jika nilai tersebut ditemukan. Deklarasinya sebagai berikut:

int hashtbl_remove(HASHTBL *hashtbl, const char *key)

{

struct hashnode_s *node, *prevnode=NULL;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) {

free(node->key);

if(prevnode) prevnode->next=node->next;

else hashtbl->nodes[hash]=node->next;

free(node);

return 0;

}

prevnode=node;

node=node->next;

}

return -1;

}

Searching

Teknik pencarian pada hash tabel yaitu dengan mencari nilai hash yang sesuai menggunakan deklarasi sama seperti pada linked list. Jika data tidak

ditemukan maka menggunakan nilai balik NULL. Deklarasinya sebagai berikut:

void *hashtbl_get(HASHTBL *hashtbl, const char *key)

{

struct hashnode_s *node;

hash_size hash=hashtbl->hashfunc(key)%hashtbl->size;

node=hashtbl->nodes[hash];

while(node) {

if(!strcmp(node->key, key)) return node->data;

node=node->next;

}

return NULL;

}

Resizing

Jumlah elemen pada hash tabel tidak selalu diketahui ketika terjadi penambahan data. Jika jumlah elemen bertambah begitu besar maka itu akan mengurangi operasi pada hash tabel yang dapat menyebabkan terjadinya kegagalan memory. Fungsi Resizing hash tabel digunakan untuk mencegah terjadinya hal itu.Dekalarsinya sebagai berikut:

int hashtbl_resize(HASHTBL *hashtbl, hash_size size)

{

HASHTBL newtbl;

hash_size n;

struct hashnode_s *node,*next;

newtbl.size=size;

newtbl.hashfunc=hashtbl->hashfunc;

if(!(newtbl.nodes=calloc(size, sizeof(struct

hashnode_s*)))) return -1;

for(n=0; n<hashtbl->size; ++n) {

for(node=hashtbl->nodes[n]; node; node=next) {

next = node->next;

hashtbl_insert(&newtbl, node->key,

node->data);

hashtbl_remove(hashtbl, node->key);

}

}

free(hashtbl->nodes);

hashtbl->size=newtbl.size;

hashtbl->nodes=newtbl.nodes;

return 0;

}

Lookup pada Hash table

Salah satu keunggulan struktur hash table dibandingkan dengan struktur tabel biasa adalah kecepatannya dalam mencari data. Terminologi lookup mengacu pada proses yang bertujuan untuk mencari sebuah record pada sebuah tabel, dalam hal ini adalah hash table.

Dengan menggunakan hash function, sebuah lokasi dari record yang dicari

bisa diperkirakan. Jika lokasi yang tersebut berisi record yang dicari, maka

pencarian berhasil. Inilah kasus terbaik dari pencarian pada hash table. Namun, jika record yang hendak dicari tidak ditemukan di lokasi yang diperkirakan, maka akan dicari lokasi berikutnya sesuai dengan kebijakan resolusi bentrokan. Pencarian akan berhenti jika record ditemukan, pencarian bertemu dengan tabel kosong, atau pencarian telah kembali ke lokasi semula.

Collision (Tabrakan)

Keterbatasan tabel hash menyebabkan ada dua angka yang jika dimasukkan ke dalam fungsi hash maka menghasilkan nilai yang sama. Hal ini disebut dengan collision.

contoh: Kita ingin memasukkan angka 6 dan 29.

             Hash(6) = 6 % 23 = 6

             Hash(29)= 29 % 23 = 6

Pertama-tama anggap tabel masih kosong. Pada saat angka 6 masuk akan ditempatkan pada posisi indeks 6, angka kedua 29 seharusnya ditempatkan di indeks 6 juga, namun karena indeks ke-6 sudah ditempati maka 29 tidak bisa ditempatkan di situ, di sinilah terjadi collision. Cara penanganannya bermacam-macam :

Collision Resolution Open Addressing

1.      Linear Probing

Pada saat terjadi collision, maka akan mencari posisi yang kosong di bawah tempat terjadinya collision, jika masih penuh terus ke bawah, hingga ketemu tempat yang kosong. Jika tidak ada tempat yang kosong berarti HashTable sudah penuh. Contoh deklarasi program:

struct { ... } node;

node Table[M]; int Free;

/* insert K */

addr = Hash(K);

if (IsEmpty(addr)) Insert(K,addr);

else {

/* see if already stored */

test:

if (Table[addr].key == K) return;

else {

addr = Table[addr].link; goto test;}

/* find free cell */

Free = addr;

do { Free--; if (Free<0) Free=M-1; }

while (!IsEmpty(Free) && Free!=addr)

if (!IsEmpty(Free)) abort;

else {

Insert(K,Free); Table[addr].link = Free;}

}

2.      Quadratic Probing

Penanganannya hampir sama dengan metode linear, hanya lompatannya tidak satu-satu, tetapi quadratic ( 12, 22, 32, 42, … )

3.      Double Hashing

Pada saat terjadi collision, terdapat fungsi hash yang kedua untuk menentukan posisinya kembali.

Binery Tree

Dalam ilmu komputer, sebuah pohon biner (binary tree) adalah sebuah pohon struktur data di mana setiap simpul memiliki paling banyak dua anak. Secara khusus anaknya dinamakan kiri dan kanan. Penggunaan secara umum pohon biner adalah Pohon biner terurut, yang lainnnya adalah heap biner.

Dalam ilmu komputer, sebuah pohon biner adalah struktur data pohon di mana setiap node memiliki paling banyak dua anak, yang disebut sebagai anak kiri dan anak kanan. Definisi rekursif hanya menggunakan teori himpunan gagasan adalah bahwa (non-kosong) pohon biner adalah tiga (L, S, R), di mana L dan R adalah pohon biner atau himpunan kosong dan S adalah satu set tunggal. Beberapa penulis memungkinkan pohon biner menjadi himpunan kosong juga.

Dari perspektif teori grafik, biner (dan K-ary) pohon seperti yang didefinisikan di sini sebenarnya arborescences. Sebuah pohon biner sehingga dapat juga disebut bifurcating arborescence-istilah yang benar-benar muncul di beberapa buku-buku pemrograman yang sangat tua, sebelum terminologi ilmu komputer modern menang. Hal ini juga memungkinkan untuk menafsirkan sebuah pohon biner sebagai diarahkan, bukan grafik diarahkan, dalam hal pohon biner adalah memerintahkan, berakar pohon. Beberapa penulis menggunakan berakar pohon biner bukan pohon biner untuk menekankan fakta bahwa pohon berakar, tetapi seperti yang didefinisikan di atas, pohon biner selalu berakar. Sebuah pohon biner adalah kasus khusus dari pohon K-ary memerintahkan, di mana k adalah 2.

Dalam komputasi, pohon biner jarang digunakan semata-mata untuk struktur mereka. Jauh lebih khas adalah untuk mendefinisikan fungsi pelabelan pada node, yang menghubungkan beberapa nilai untuk setiap node. Pohon biner berlabel cara ini digunakan untuk mengimplementasikan pohon pencarian biner dan tumpukan biner, dan digunakan untuk pencarian yang efisien dan penyortiran. Penunjukan node non-root sebagai kiri atau kanan anak bahkan ketika hanya ada satu anak hal hadir dalam beberapa aplikasi, khususnya adalah penting dalam pohon pencarian biner. Dalam matematika, apa yang disebut pohon biner dapat bervariasi secara signifikan dari penulis ke penulis. Beberapa menggunakan definisi yang biasa digunakan dalam ilmu komputer, tetapi yang lain mendefinisikannya sebagai setiap non-daun memiliki tepat dua anak dan tidak selalu order (sebagai kiri / kanan) anak-anak baik.

Pengertian Binaary Tree dalam Struktur Data
Pohon biner adalah pohon dengan syarat bahwa tiap node hanya memiliki boleh maksimal dua subtree dan kedua subtree tersebut harus terpisah. Sesuai dengan definisi tersebut, maka tiap node dalam binary tree hanya boleh memiliki paling banyak dua anak/child.

Node pada Binary Tree 
Jumlah maksimum node pada setiap tingkat adalah 2n, Node pada binary tree maksimumnya berjumlah 2n-1.