Pernah coba mrogram pakai bahasa tingkat Enak (e gede) kayak php atau perl atau ruby? Segalanya sudah enak tersedia disitu. Paling tidak, hampir segalanya.
Ada beberapa yang bisa dicatat, tapi saat ini, enaknya kita ngomongin soal "associative-array", salah satu jenis struktur data yang didukung oleh bahasa-bahasa tersebut. Dengan associative-array ini, kita bisa melakukan hal-hal sebagai berikut:
daftar_harga["apel"] = 2000;
daftar_harga["mangga"] = 3000;
Sekarang, mari bermain dengan bahasa C. Bahasa tingkat enak (e kecil) yang satu ini sungguh ajaib. Konsepnya gak banyak, cukup untuk bisa disimpen di alamat memori akses langsung di otak kita. Ini keliatan awalnya. Nyatanya, setan didalamnya cukup banyak untuk bisa bikin stress orang-orang yang gak siap mental.. :-)
Nah, di C, tidak ada yang namanya associative-array. Jenis data array memang ada di C, namun tidak associative, semua array hanya bisa punya indeks angka. Jadi kalau ingin melakukan hal seperti diatas dalam C, kita jadi harus melakukan, kira-kira, hal berikut:
#define APEL 0
#define MANGGA 1
daftar_harga[APEL] = 2000;
daftar_harga[MANGGA] = 3000;
penjelasan detailnya apa itu #define, silahkan cari di kamus-kamus terdekat.
Problem ini tentu saja selesai, kalau kita memang hanya ingin melihat daftar harga Apel dan Mangga. Bagaimana bila kita tiba-tiba ingin melihat juga daftar harga Jeruk, Salak, dan Semangka?
Di php dan kawan-kawan, ini bukan masalah besar, malah jika ingin kita bisa saja membuat associative-array secara dinamis dengan mengambil daftar buah dan harga dari sebuah file atau mungkin dari tabel di database.
Bagaimana melakukan hal yang sama dalam C?
Untuk itu, kita jadi perlu berkenalan dengan hash dan linked list, dua format struktur data yang bisa digambarkan dengan 1 kata; "Menarik"!
Dari dulu waktu mulai belajar C, kalau ketemu linked list, aku selalu garuk-garuk kepala. Pertama pusing, bagaimana sebenarnya dia bekerja, kemudian pusing, mengapa implementasi linked-list ku selalu berhasil mengeluarkan pesan "Segmentation fault". Dan terakhir, suka terkagum-kagum sendiri karena akhirnya (mengira) berhasil mengerti dan membuat linked list sendiri :-)
Cukup dengan nostalgianya.
Sekarang bagaimana kita bisa menggunakan hash dan linked list untuk implementasi sesuatu seperti associative array?
Konsep-nya sederhana, begini mungkin ceritanya:
1. Mengingat bahwa di C segala array itu hanya bisa diindex dengan angka, maka kita perlu merubah kata-kata yang ingin kita jadikan indeks itu menjadi angka terlebih dahulu. Inilah gunanya hash. Dengan menggunakan fungsi hash, kita bisa merubah kata-kata "pisang" jadi angka 1, misalnya.
2. Keliatannya selesai? Belum. Mengingat bahwa tidak ada fungsi hash yang sempurna, dalam artian selalu menghasilkan angka yang berbeda untuk setiap macam kata, maka tabrakan (collission) pasti akan terjadi. Misalnya, kalau hash("pisang") => 1, maka bukan tidak mungkin kalau hash("rambutan") juga => 1. Kalau begini, apa yang bisa kita lakukan? Ada dua yang kuketahui, 1 yang disebut dengan Chaining, dan 2 yang disebut dengan Open-Addressing.
3. Berhubung kita lagi ngomongin linked-list (dan aku gak ngerti Open-addressing *smile*), maka kita memilih metode Chaining untuk memecahkan masalah tabrakan tadi. Chaining ini artinya, semua data yang mau kita associate-kan kita simpan dalam sebuah hash-table dalam bentuk linked-list.
Susah juga ya menjelaskannya.
Mungkin aku harusnya menjelaskan soal apa itu linked-list dulu kali ya?
to-be continued aja dech... :-)
ps: anyone interested, please lookup the details on Google or Wikipedia, they should have it and should provide better explanations than what I can give.