Ay_Ayu`s words

“Hashing”, istilah apa ini sebenarnya dalam dunia programming? Pertama kali melihat isitilah ini dalam judul modul 6 praktikum algoritma dan struktur data timbul gejolak hati antara penasaran dan rasa pengen “hashing-hashing” karena praktikum ini koq gak selesai-selesai. :p

Okay, biar modul ini gak tambah modal-madul langsung aja melaksanakan kewajiban yang diberikan oleh sang asisten ini. ^_^

Istilah Hashing dalam dunia programming adalah Teknik mengindeks pada menajemen database dimana nilai kunci (yang mengindentifikasikan record) dimanipulasi secara numerik untuk menghitung langsung lokasi record yang berkaitan atau titik tolak untuk mencari record yang terkait. Hashing Merupakan suatu metode pengindeksan lokasi file pada suatu disk, sehingga dapat mempercepat waktu yang diperlukan untuk mencari letak file pada disk tersebut. Atau istilah gampangnya katanya hashing ini berbentuk array of linked list jadi menggabungkan antara kelebihan linked list yang dinamis dan kelebihan array dengan indexnya agar lebih to the point dalam pencarian data.

Dalam metode hashing ini bakal banyak istilah-istilah yang mungkin asing kita dengarkan seperti hash function, hash table, hash code dan lazy delete. Apa sebenernya arti dari itu semua dan segala macam tetek bengeknya? Penasaran? Baca terus “Ay_Ayu`s words..” ini sampai selesai ya… =b

Hash Function adalah Sebuah fungsi matematis yang melakukan konversi terhadap string masukan yang panjang menjadi menjadi string lain dengan panjang yang selalu sama, tidak bergantung pada panjang string masukannya, dan biasanya dengan ukuran yang jauh lebih kecil daripada string masukannya. Fungsi hash pada umumnya digunakan untuk mempercepat table look-up, atau untuk membandingkan data (misalnya mencari data tertentu dalam sebuah basis data, mendeteksi data yang terduplikasi dalam sebuah file berukuran besar, dan sebagainya).

Pada era saat ini ada berbagai macam hash function yang sudah ada dan sering digunakan diantaranya :

a. Fungsi modulo

- Home address dicari dengan cara mencari sisa hasil bagi nilai key dengan suatu nilai tertentu.

- Fungsi: f(key) = key mod n

- Dengan n adalah:

** Banyaknya ruang alamat yang tersedia

** Atau bilangan prima terdekat yang berada di atas nilai banyak data, setelah itu banyaknya ruang alamat disesuaikan dengan n

Jumlah lokasi memori yang tersedia dihitung, kemudian jumlah tersebut digunakan sebagai pembagi untuk membagi nilai yang asli dan menghasilkan sisa. Sisa tersebut adalah nilai hashnya. Secara umum, rumusnya h(k)= k mod m. Dalam hal ini m adalah jumlah lokasi memori yang tersedia pada array. Fungsi hash tersebut menempatkan record dengan kunci k pada suatu lokasi memori yang beralamat h(k). Metode ini sering menghasilkan nilai hash yang sama dari dua atau lebih nilai aslinya atau disebut dengan bentrokan. Karena itu, dibutuhkan mekanisme khusus untuk menangani bentrokan yang disebut kebijakan resolusi bentrokan.

b. Fungsi Pemotongan

- Home address dicari dengan memotong nilai key ke jumlah digit tertentu yang lebih pendek.

- Contoh: NIM yang tadinya 8 digit, dipotong hanya menjadi 2 digit!

c. Fungsi Pelipatan

- Dilakukan pelipatan terhadap record key dengan bagian yang sama panjang, lalu setiap bagian dijumlahkan

- NIM 8 digit dibagi dua digit, hingga menjadi 4 buah.

- Misal: 22002521, dibagi 22 00 25 21 kemudian dijumlahkan: 68

Metode ini membagi nilai asli ke dalam beberapa bagian, kemudian menambahkan nilai-nilai tersebut, dan mengambil beberapa angka terakhir sebagai nilai hashnya

d. Fungsi Pengkuadratan

- Home address dicari dengan mengkuadratkan setiap digit pembentuk key, lalu semua hasilnya dijumlahkan

- Contoh: 22002211, semua digit dikuadratkan dan dijumlah

e. Fungsi Penambahan Kode ASCII

- Jika key bukan kode numerik, home address dicari dengan menjumlahkan kode ASCII setiap huruf pembentuk key

ADE = 65 + 68 + 69 = 192

Dan masih banyak lagi hash function lainnya, pasti para pecinta programming ini takkan pernah puas untuk terus berkreasi menciptakan hash function hash function lainnya untuk terciptakan kodingan yang lebih sempurna. :D

Sebuah hash table atau hash map dalam ilmu komputer adalah struktur data yang menggunakan fungsi hash untuk efisiensi peta atau kunci pengidentifikasi tertentu (misalnya, nama orang) untuk nilai-nilai yang terkait (misalnya, nomor telepon). Fungsi hash digunakan untuk mengubah kunci ke indeks (hash) dari elemen array (slot atau ember) dimana nilai yang sesuai yang akan dicari.

Hash Code adalah suatu cara untuk mengenkripsikan data menjadi suatu kode sesuai keinginan pembuat.

Lazy Delete adalah penghapusan yang hanya membuat nilai yang dihapus menjadi NULL tanpa menghapus sepenuhnya.

Hmm… dari penjabaran panjang kali lebar di atas metode hashing tampak sempurna ya dalam permasalahan pencarian data, eits tapi jangan salah dibalik “kesempurnaan” itu ternyata memang tak ada yang sempurna. Karena itulah kekreatifitasan selalu diperlukan untuk menyelesaikan masalah. hehehe =b

Dalam metode hashing yang menggunakan index dalam pencarian data apa yang terjadi kalau ternyata ada data yang memiliki index yang sama atau istilah kerennya terjadi “collision” (tabrakan) . inilah hasil kekreatifitasan dalam menyelesaikan masalah “tabrakan” yang sudah ada (tak menutup kemungkinan akan tercipta kekreatifitasan-kekreatifitasan yang lain) :

a. Linear Probing :

o Pencarian dilakukan dengan jarak pencarian tetap

o contoh:

§ F(key) = key mod 10

§ Ruang memori tersedia 10 alamat

§ Probing jarak 3

§ Urutan kunci: 20, 31, 33, 40, 10, 12, 30, 15

o Jawaban:

KEY	F	Progress	Addres
20	0	0	0
31	1	1	1
33	3	3	3
40	0	0,3,6	6
10	0	0,3,6,9	9
12	2	2	2
30	0	0,3,6,9,2,5	5
15	5	5,8	8

0	20
1	31
2	12
4
5	20
6	40
7
8	15
9	10

b. Quadratic Probing

o Pencarian dilakukan dengan jarak pencarian berubah dengan perubahan tetap

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

c. Separated Chaining

Suatu teknik untuk mengatasi collision (bentrokan) dengan cara menggunakan daerah di luar tabel hash dalam bentuk linier. Bentuk linier ini bisa berupa linked list atau array. Urutan data pada daerah overflow bisa terurut atau random, tergantung cara penyisipan yang dilakukan.

Hashing diciptakan pasti bukan tanpa tujuan, apa saja sebenarnya manfaat dari metode hashing ini? Hashing digunakan sebagai metode untuk menyimpan data dalam sebuah array agar penyimpanan data, pencarian data, penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide dasarnya adalah menghitung posisi record yang dicari dalam array, bukan membandingkan record dengan isi pada array. Fungsi yang mengembalikan nilai atau kunci disebut fungsi hash (hash function) dan array yang digunakan disebut tabel hash (hash table). Secara teori, kompleksitas waktu (T(n)) dari fungsi hash yang ideal adalah O(1). Untuk mencapai itu setiap record membutuhkan suatu kunci yang unik.

Fungsi hash menyimpan nilai asli atau kunci pada alamat yang sama dengan nilai hashnya. Pada pencarian suatu nilai pada tabel hash, yang pertama dilakukan adalah menghitung nilai hash dari kunci atau nilai aslinya, kemudian membandingkan kunci atuau nilai asli dengan isi pada memori yang beralamat nomor hashnya. Dengan cara ini, pencarian suatu nilai dapat dilakukan dengan cepat tanpa harus memeriksa seluruh isi tabel satu per satu.

Selain digunakan pada penyimpanan data, fungsi hash juga digunakan pada algoritma enkripsi sidik jari digital (fingerprint) untuk mengautentifikasi pengirim dan penerima pesan. Sidik jari digital diperoleh dengan fungsi hash, kemudian nilai hash dan tanda pesan yang asli dikirim kepada penerima pesan. Dengan menggunakan fungsi hash yang sama dengan pengirim pesan, penerima pesan mentransformasikan pesan yang diterima. Nilai hash yang diperoleh oleh penerima pesan kemudian dibandingkan dengan nilai hash yang dikirim pengirim pesan. Kedua nilai hash harus sama, jika tidak, pasti ada masalah. Hashing selalu merupakan fungsi satu arah.

Fungsi hash yang ideal tidak bisa diperoleh dengan melakukan reverse engineering dengan menganalisa nilai hash. Fungsi hash yang ideal juga seharusnya tidak menghasilkan nilai hash yang sama dari beberapa nilai yang berbeda. Jika hal yang seperti ini terjadi, inilah yang disebut dengan bentrokan (collision). Kemungkinan terjadinya bentrokan tidak dapat dihindari seratus persen. Fungsi hash yang baik dapat meminimalkan kemungkinan terjadinya bentrokan.

Pastinya belum afdol kalau kita ngomongin programming tanpa ada contoh kodingannya berikut adalah contoh program hashing data siswa dengan menggunakan separated chaining dalam penyelesaian masalah collision-nya. Selamat menikmati ^_^

#include

#include

#include

#include

#include

//definisi struct

struct data {

int no;

char nama[100];

char job[100];

char alamat[100];

int tahun;

struct data *next;

};

//fungsi untuk membuat struct baru

data *dataMaker(int no,char nama[],char job[],char alamat[], int tahun)

{

data *entry=(data*) malloc (sizeof(data));

entry->no=no;

strcpy(entry->nama,nama);

strcpy(entry->job,job);

strcpy(entry->alamat,alamat);

entry->tahun=tahun;

entry->next=NULL;

return entry;

}

//fungsi untuk mengencode kode job dengan return integer

int encodeJob(char job[])

{

if(strcmp(job,"swordsman")==0)

{return 11;}

else if(strcmp(job,"monk")==0)

{return 12;}

else if(strcmp(job,"wizard")==0)

{return 21;}

else if(strcmp(job,"summoner")==0)

{return 22;}

else if(strcmp(job,"alchemist")==0)

{return 31;}

else if(strcmp(job,"mechanics")==0)

{return 32;}

else if(strcmp(job,"physician")==0)

{return 33;}

else if(strcmp(job,"singer")==0)

{return 41;}

else if(strcmp(job,"crafter")==0)

{return 42;}

}

//fungsi untuk mengidentifikasi tahun

int pamungkas(int tahun)

{

return tahun%100;

}

//fungsi untuk membuat nrp

int nrp(int nrp,int tahun, int urut)

{

return nrp*10000+tahun*100+urut;

}

//fungsi untuk menginputkan dalam hashtable

void input(char nama[],char job[],char alamat[], int tahun, int urut, data hashTable[])

{

int no=nrp(encodeJob(job),pamungkas(tahun),urut);//no=ID

int index=no%100;//index=2 digit terakhir ID

if(strlen(hashTable[index].nama)==0)//jika pada index tersebut belum ada datax

{

hashTable[index].no=no;

strcpy(hashTable[index].nama,nama);

strcpy(hashTable[index].job,job);

strcpy(hashTable[index].alamat,alamat);

hashTable[index].tahun=tahun;

}

else//jika pada index tersebut sudah ada datax, maka data dibuat dinextnya

{

if(hashTable[index].next!=NULL)

{

data *pointer=hashTable[index].next;

while(pointer->next!=NULL)

{

pointer=pointer->next;

}

pointer->next=dataMaker(no,nama,job,alamat,tahun);

}

else

{

hashTable[index].next=dataMaker(no,nama,job,alamat,tahun);

}

}

}

//fungsi untuk mencari data

void search(data hashTable[],int a,int cek)

{

int tes=0;

if(hashTable[a].no==cek)//mencari yg nrp nya sama

{

tes++;

printf("hasil:\n");

printf("NAMA : %s\n",hashTable[a].nama);

printf("JOB : %s\n",hashTable[a].job);

printf("ALAMAT : %s\n",hashTable[a].alamat);

printf("TAHUN : %d\n\n",hashTable[a].tahun);

}

else

{

data *pointer=hashTable[a].next;

while(pointer!=NULL)

{

if(pointer->no==cek)

{tes++;

printf("hasil:\n");

printf("NAMA : %s\n",pointer->nama);

printf("JOB : %s\n",pointer->job);

printf("ALAMAT : %s\n",pointer->alamat);

printf("TAHUN : %d\n\n",pointer->tahun);

pointer=pointer->next;

}

}

}

if(tes==0)//jika tidak ada datanya

{

printf("hasil:\n");

printf("data tidak ditemukan\n");

}

}

//fungsi untuk mengosongkan dulu semua hashtable

void kosong(data hashTable[],int panjang)

{

for(int a=0;a

{

hashTable[a].no=0;

strcpy(hashTable[a].nama, "");

strcpy(hashTable[a].job, "");

strcpy(hashTable[a].alamat, "");

hashTable[a].tahun=0;

hashTable[a].next=NULL;

}

}

//fungsi untuk menampilkan semua isi hashtable

void view(data hashTable[],int length)

{

for(int a=0;a

{

if(strlen(hashTable[a].nama)==0)

{

}

else

{

printf("ID : %d\n",hashTable[a].no);

printf("NAMA : %s\n",hashTable[a].nama);

printf("JOB : %s\n",hashTable[a].job);

printf("ALAMAT : %s\n",hashTable[a].alamat);

printf("TAHUN : %d\n\n",hashTable[a].tahun);

data *pointer=hashTable[a].next;

while(pointer!=NULL)

{

printf("ID : %d\n",pointer->no);

printf("NAMA : %s\n",pointer->nama);

printf("JOB : %s\n",pointer->job);

printf("ALAMAT : %s\n",pointer->alamat);

printf("TAHUN : %d\n\n",pointer->tahun);

pointer=pointer->next;

}

}

}

}

//fungsi untuk membaca file txt berformat cvs (dipisahkan oleh koma)

void cvs(data hashTable[])

{

//membuka file dengan nama tes.txt

FILE *fbaca=fopen("input.txt", "rt");

int tahun, urut;

char in[100];

printf("DATA : \n");

//pembacaan per baris

while(fscanf(fbaca, "%s", in) != EOF)

{

char nama[100], job[100], alamat[100], *temp, yearS[100], presdS[100];

//pembacaan inputan

// pertama sebelum koma dikopikan ke nama

temp=strtok(in, ",");

strcpy(nama, temp);

// pertama setelah koma dikopikan ke job

temp=strtok(NULL, ",");

strcpy(job, temp);

// kedua setelah koma dikopikan ke alamat

temp=strtok(NULL, ",");

strcpy(alamat, temp);

// ketiga setelah koma dikopikan ke yearS

temp=strtok(NULL, ",");

strcpy(yearS, temp);

// yearS yang bertipe string diconvert ke tipe integer

tahun=atoi(yearS);

// pertama sebelum koma dikopikan ke presdS

temp=strtok(NULL, ",");

strcpy(presdS, temp);

urut=atoi(presdS);//dikonvert ke integer

input(nama,job,alamat,tahun,urut,hashTable);//dimasukkan fungsi input

printf("\t%s %s %s %s %s\n", nama, job, alamat, yearS, presdS);

}

printf("\n\n");

//menutup file

fclose(fbaca);

}

NB : untuk memancing kekreatifitasan para pecinta coding, kodingan ini belum ada fungsi main nya, jadi kalau mau bikin program ini bisa di compile silahkan berlomba-lomba memacu diri untuk berkreatifitas men-coding fungsi main-nya. Pasti ini hal yang sangat mudah buat para coder setia. Semangat ngoding! \^_^/