OPTIMALITAS CELLAR DALAM COALESCED HASHING UNTUK MENDUKUNG PROSES SEARCHING PADA BASIS DATA Irene Astuti Lazarusli"
ABSTRACT There are many ways for data management and processing. Coalesced hashing method is one of them. This method can be done either with cellar or without cellar. To find the most optimal size of cellar compared with a given number of data, a number of tests were conducted. This application, which is built in Borland Delphi 3.0 for Windows, is playing the role as supplementary program for conducting those tests. The application will generate a number of integers randomly, and then implements the hashing function to the data. The output of this application is the average number of data probing. Based on the test result we gained, it can be concluded that the using of cellar will be effective when the number of data is greater than 50% of storage size. The most optimal size of cellar, which gained the least number of data probing, ranges between 10% to 20% of storage size, which means the 80% - 90% of storage has to be allocated for main storage area and the 10%20% is allocated for cellar (overflow area). 1. Pendahuluan Satu hal yang dipikirkan oleh masyarakat luas sejak dahulu adalah kebutuhan akan informasi dan ketidaksabaran dalam hal memperolehnya. Dalam hal memperoleh informasi, seringkali terjadi kontradiksi karena manusia menginginkan kemampuan akses yang cepat untuk data yang berukuran besar, tetapi komputer tidak dapat memenuhi keinginan manusia tersebut 3. Dalam hal ini penyimpanan data menjadi sangat penting, Oleh karena itu berbagai teknik penyimpanan dan pencarian data telah diciptakan. Data dapat disimpan secara internal memori maupun secara eksternal dengan menggunakan file. Data yang disimpan secara eksternal memerlukan pengelolaan yang baik untuk mempermudah penyimpanan maupun pengaksesan kembali. Ada beberapa cara pengelolaan data yang telah dikenal, antara lain dengan sequential/ pile file, direct file, indexed file, index sequential file. Untuk mempermudah dan mempercepat pencarian data dalam suatu berkas, dapat digunakan berbagai metoda pemetaan yang disesuaikan dengan kondisi data yang disimpan. Pemetaan adalah menghubungkan antara nilai kunci dari data yang disimpan dengan alamatnya pada media penyimpan. Salah satu teknik yang dikenal dalam pengelolaan berkas secara langsung (direct file organization) untuk mensimulasikan hubungan antara media penyimpan data dengan proses pencarian data adalah metode coalesced hashing. Coalesced hashing adalah suatu metode pengaturan penyimpanan data yang bertujuan untuk mempercepat pengambilan. Meskipun teknik hashing ini telah digunakan beberapa lama, namun teknik ini senantiasa dikembangkan dan disesuaikan dengan situasi saat ini 3. Masalah yang sering muncul dalam coalesced hashing adalah terjadinya ' Asisten Dosen Jurusan Teknik Informatika, FIK-UPH Optimalitas Cellar... (Irene Astuti L.)
53
tabrakan (collision), karena lokasi yang akan ditempati oleh data tertentu ternyata telah ditempati oleh data terdahulu. Apabila terjadi tabrakan semacam itu, maka data yang terakhir ini diletakkan pada sel kosong yang paling bawah. Hal ini menimbulkan masalah lain yaitu data asli seringkali mengumpul di bagian bawah, sehingga untuk mencari tempat kosong perlu dilakukan scan dari bawah ke atas. Hal ini mengakibatkan proses penyimpanan dan pencarian data menjadi lambat. Untuk mengatasi masalah tersebut, maka dialokasikan sebagian tempat paling bawah pada media penyimpan yang disebut gudang (cellar). Cellar ini berfungsi untuk meletakkan nilai kunci yang akan diletakkan pada suatu lokasi tertentu, jika lokasi tersebut ternyata telah ditempati oleh kunci lain. Ukuran cellar yang optimal besarnya tergantung pada ukuran kepadatan data yang akan disimpan. Karena itu penelitian ini dilakukan untuk menemukan persentase perbandingan ukuran cellar terhadap ukuran tabel yang paling optimal untuk kepadatan data tertentu, serta menerapkan optimalitas tersebut untuk mendukung proses searching dalam suatu kasus dengan basis data tertentu. Untuk mencari persentase perbandingan ukuran cellar yang optimal untuk ukuran data tertentu diberikan batasan sebagai berikut, data yang digunakan untuk penelitian berupa bilangan bulat dan penyimpanan data diatur dengan menggunakan dengan metode coalesced hashing. Sedangkan untuk menerapkan persentase paling optimal yang diperoleh untuk mendukung proses searching pada basis data diberikan batasan sebagai berikut, basis data yang digunakan berupa sebuah file bertipe record yang disesuaikan dengan struktur data yang didukung oleh bahasa pemrograman Borland Delphi, dan Record yang disimpan dalam tabel yang digunakan mempunyai field kunci yang berupa bilangan bulat. 2. Konsep Dasar Metode Coalesced hashing Konsep dasar metode coalesced hashing yang akan dibahas pada bagian ini meliputi metode coalesced hashing tanpa cellar, metode coalesced hashing dengan cellar, pencarian optimalitas, dan metode pengorganisasian kunci. 2.1 Metode Coalesced hashing Tanpa Cellar Hashing merupakan suatu metode pengaturan penyimpanan data yang bertujuan untuk mempercepat pengambilan. Fungsi hashing adalah suatu fungsi yang memetakan sebuah jangkauan nilai kunci yang lebih luas ke dalam jangkauan yang lebih sempit 3 . Fungsi hashing akan menghasilkan sebuah alamat berdasarkan nilai kunci yang diterimanya \ Metode ini cocok untuk menyimpan data yang sifatnya relatif statis, dalam arti jumlahnya jarang ditambah/dikurangi. Metode coalesced hashing menyimpan data berdasarkan elemen kunci. Data disimpan dalam tabel yang memuat informasi tentang link data. Ada beberapa kemungkinan fungsi hashing yang dapat digunakan. Fungsi hashing yang digunakan dalam penelitian ini adalah: Hash(key) = key mod n; di mana n = ukuran table, dan n harus berupa bilangan prima3 Contoh: Misalkan ada 7 data dengan elemen kunci 27, 18, 29, 28, 39, 13, 16 akan disimpan dalam array X[0..10] yang berukuran 11. Berarti tabel yang digunakan untuk menyimpan akan berukuran 11 dengan alamat 0 sampai dengan 10. Fungsi hashing yang dipakai : key mod n dengan n=11. Mula-mula data disimpan dalam 54 Jurnal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
lokasi yang bersesuaian dengan hasil perhitungan fungsi hash tersebut. Jika lokasi yang akan ditempati masih kosong, maka data dapat langsung diletakkan di tempat itu. Tetapi jika lokasi yang akan ditempati sudah ditempati oleh data yang lebih dahulu; berarti data tersebut mempunyai sisa bagi atau modulo yang sama, maka data diletakkan pada sel kosong paling bawah. Kemudian field link pada lokasi tersebut diisi dengan alamat sel kosong yang dituju tadi. Maka proses penyisipan data yang terjadi adalah sebagai berikut: 27 mod 1 1 = 5 -> Data 27 disimpan di X[5] 18 mod 11 =7 -> Data 18 disimpan di X[7] 29 mod 1 1 = 7 -> Karena X[7] telah ditempati, maka data 29 disimpan di X[10] dan field link pada X[7] diatur ke alamat 10 28 mod 1 1 = 6 -> Data 28 disimpan di X[6] 39 mod 1 1 = 5 -> Karena X[6] telah ditempati, maka data 39 disimpan di X[9] dan field link pada X[6] diatur ke alamat 9 13 mod 11 =2 -> Data 13 disimpan di X[2] 16 mod 1 1 = 5 -> Karena X[5] telah ditempati, maka data 16 disimpan di X[8] dan field link pada X[5] diatur ke alamat 8 Contoh di atas dapat dijelaskan dengan ilustrasi pada Garmbar 1. Alamat 0 1 2 3 4 5 6 7 8 9 10
Record
Link
13
A
27 28 18 16 39 29
8 9 10 A (nil) A (nil) A (nil)
(nil)
Gambar 1. Ilustrasi Coalesced Hashing tanpa cellar
Maka untuk mencari data dapat dilakukan dengan cara sebagai berikut: 1. Menerapkan fungsi hashing terhadap elemen kunci dari data tersebut. 2. Mencari data tersebut pada alamat yang diperoleh dari langkah nomor 1. 3. Jika data yang ditemukan tidak sesuai dengan yang dicari, maka lihat alamat yang terdapat pada field link, kemudian cari data di alamat yang ada pada field link tersebut. Sebagai contoh: Elemen kunci dari data yang akan dicari = 39, maka: 1. Fungsi hash: 39 mod 11=6 2. X[6] = 28 3. Karena 28<>39 maka baca link = 9 sehingga X[9] = 39, data ditemukan.
Optimalitas Cellar... (Irene Astuti L.)
2.2 Metode Coalesced hashing Dengan Cellar Masalah yang sering muncul dalam coalesced hashing adalah tabrakan {collision). Masalah ini dapat dikurangi dengan memodifikasi organisasi tabel yaitu dengan mengalokasikan seluruh tempat dalam tabel untuk overflow record dan home address record, dengan cara membagi tabel menjadi dua bagian yaitu sebuah area primer dan sebuah area overflow yang selanjutnya disebut cellar . Masalah yang dihadapi pada penggunaan metode coalesced hashing tanpa cellar adalah data awal (bukan data hasil link) kadang-kadang mengumpul di bawah sehingga untuk mencari tempat kosong yang baru harus dilakukan scan ke sel yang di atasnya. Cara mengatasi masalah tersebut adalah dengan mengalokasikan sebagian tabel paling bawah menjadi gudang (cellar) untuk menyimpan data link. Misalnya digunakan ukuran gudang 4, maka fungsi hash menjadi key mod 7 Dengan data yang sama dengan contoh sebelumnya maka didapat: 27 mod 7 = 6 -> Data 27 disimpan di X[6] 18 mod 7 = 4 -> Data 18 disimpan di X[4] 29 mod 7 = 1 -» Data 29 disimpan di X[1] 28 mod 7 = 0 -> Data 28 disimpan di X[0] 39 mod 7 = 4 -> Karena X[4] telah ditempati, data 39 disimpan di cellar 13 mod 7 = 6 - * Karena X[6] telah ditempati, data 13 disimpan di cellar 16 mod 7 = 2 - * Data 16 disimpan di X[2] Contoh tersebut dapat dijelaskan dengan ilustrasi pada gambar 2. Alamat 0 1 2 3 4 5 6 7 8 9 10
Record 28 29 16
Link
18
10
27
9
13 39
A
A A A
A
Gambar 2. Ilustrasi Coalesced Hashing dengan cellar
2.3 Pencarian Optimalitas Efisiensi pencarian data dihitung berdasarkan rata-rata pengambilan dengan rumus: Rata-rata pengambilan = iumlah langkah pengambilan tiap data (masing-masinq satu kali) total data Berdasarkan contoh di atas, maka jumlah pengambilan masing-masing data dalam coalesced hashing tanpa gudang dapat digambarkan seperti pada tabel 1.
56 Jumal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
Tabel 1. Tabel jumlah pengambilan masing-masing data pada coalesced hashing tanpa cellar
Data ke0 1 2 3 4 5 6
Nilai data 27 18 29 28 39 13 16
Jumlah pengambilan 1 1 2 1 2 1 2
Jadi dalam coalesced tanpa gudang, rata-rata pengambilan = 1+1+2+1+2+1+2=10 7 7 Sedangkan jumlah pengambilan masing-masing data dalam coalesced hashing dengan gudang, dapat digambarkan pada tabel 2. Tabel 2. Tabel jumlah pengambilan masing-masing data pada coalesced hashing dengan cellar
Data ke0 1 2 3 4 5 6
Nilai data 27 18 29 28 39 13 16
Jumlah pengambilan 1 1 1 1 2 2 1
Jadi dalam coalesced dengan gudang, rata-rata pengambilan = 1+1+1+1+2+2+1 = 9 7 7 Jadi parameter yang digunakan untuk mengukur optimalitas dalam hal ini adalah efisiensi pencarian data. Ukuran cellar yang paling optimal diperoleh dari ukuran cellar yang menghasilkan efiensi paling kecil. 2.4 Metode Pengorganisasian Kunci Untuk kasus penyimpanan data ke dalam tabel yang sesungguhnya, nilai kunci tidak selalu berupa bilangan bulat. Karena itu ada beberapa metode yang dapat digunakan untuk melakukan pengorganisasian nilai kunci. Pada penelitian ini digunakan metode Hashing by Folding. Pada metode ini, nilai kunci dibagi menjadi beberapa bagian, setiap bagian (kecuali yang terakhir) hams mempunyai jumlah digit yang sama untuk menentukan alamat relatif yang akan digunakan dalam fungsi hash. Partisi ini kemudian dilipat satu sama lain lalu dijumlahkan. Hasilnya, order tertinggi dibuang dan nilai yang diperoleh itulah nilai alamat relatif. Contoh: Nilai kunci "123456789" dipartisi menjadi 3 bagian yaitu: 0001, 2345, dan 6789. untuk memperoleh alamat relatif, partisi "0001" dilipat ke kiri, partisi "2345" dilipat ke kanan, dan partisi "6789" dilipat ke kiri, kemudian ketiga partisi tersebut dijumlahkan. Optimalitas Cellar... (Irene Astuti L.)
57
Maka
1000 2345 9876 + 13221 -> digit paling depan dipotong, sehingga alamat relatif=3221
3. PERANCANGAN DAN IMPLEMENTASI Program yang dibuat dalam penelitian ini berfungsi sebagai alat bantu untuk pemecahan masalah. Inti sesungguhnya dari penelitian ini adalah mencari sejumlah data dan mencoba berbagai ukuran cellar untuk memperoleh persentase perbadingan atau rumus optimalitas ukuran cellar untuk kepadatan data tertentu. Input dari program ini adalah suatu nilai tertentu yang merupakan jumlah data yang akan disimpan. Input tersebut dapat disesuaikan dengan keperluan yaitu untuk keperluan pengguna atau untuk keperluan pencarian ukuran cellar yang optimal. Untuk keperluan yang kedua, program yang dibuat dapat menghasilkan sejumlah data yang nilainya random/acak dengan kepadatan tertentu. Sedangkan proses dari program ini adalah melakukan penempatan data ke dalam ruang penyimpanan dengan berbagai ukuran cellar dan melakukan proses pencarian data. Kemudian program akan menghitung efisiensi dari masing-masing ukuran cellar yang digunakan. Dari proses ini akan diperoleh output yang berupa cellar dengan ukuran tertentu yang memberikan rata-rata proses yang paling kecil atau dapat pula berupa tabel optimalitas untuk berbagai kepadatan data. 3.1 Perancangan Perancangan yang dilakukan peliputi disain masukan dan disain keluaran. 3.1.1 Disain Masukan Program Data masukan untuk program pencarian optimalitas adalah sebagai berikut: a. Untuk implementasi Coalesced Hashing tanpa cellar. • Jumlah Data diisi oleh pengguna, masukan berupa bilangan bulat • Ukuran Tabel diisi oleh pengguna, masukan berupa bilangan bulat, tidak boleh lebih kecil daripada jumlah data b. Untuk implementasi Coalesced Hashing dengan cellar: • Jumlah Data diisi oleh pengguna, masukan berupa bilangan bulat • Ukuran Tabel diisi oleh pengguna, masukan berupa bilangan bulat, tidak boleh lebih kecil daripada jumlah data • Ukuran cellar diisi oleh pengguna, masukan berupa persentase dari ukuran tabel 3.1.2 Disain Keluaran Program Berdasarkan masukan di atas, maka program ini akan menghasilkan keluaran sebagai berikut: • Sejumlah data acak sebanyak jumlah data yang diinginkan oleh pengguna, berupa bilangan bulat yang digenerate oleh program. • Ukuran main area dan overflow area pada coalesced hashing dengan cellar • Data hasil penerapan metode hashing tanpa cellar • Data hasil penerapan metode hashing dengan cellar • Jumlah pengambilan (probe) rata-rata dari semua data tersebut pada hashing tanpa cellar 58 Jurnal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
• •
Jumlah pengambilan (probe) rata-rata dari semua data tersebut pada hashing tanpa cellar Tabel Optimalitas ukuran cellar untuk berbagai kepadatan data.
3.2 Implementasi Perancangan yang telah dibuat, diimplementasikan dalam program.
dirumuskan
dalam
algoritma
kemudian
3.2.1 Algoritma Program Program yang dirancang mempunyai algoritma sebagai berikut: a. Untuk Coalesced Hashing tanpa cellar. 1. Inputkan jumlah data dan ukuran tabel. 2. Lakukan perulangan untuk data pertama sampai data terakhir: (i) Tempatkan data pada lokasi masing-masing dengan perhitungan: lokasi = key mod ukuran tabel (ii) Jika lokasi tersebut masih kosong, simpan data pada alamat lokasi tersebut, kemudian lanjutkan ke langkah (3). Jika lokasi tersebut telah ditempati data sebelumnya, maka lanjutkan ke langkah (iii) (iii) Cari lokasi tabel paling bawah yang kosong. (iv) Lakukan proses (iii) sampai ditemukan lokasi yang kosong untuk menempatkan data tersebut. Simpan data pada lokasi kosong yang telah ditemukan. Simpan alamat lokasi kosong tersebut pada field link untuk data yang bersangkutan. 3. Selesai b.
c.
Untuk Coalesced Hashing dengan cellar. 1. Inputkan jumlah data, ukuran tabel dan persentase cellar 2. Lakukan perulangan untuk data pertama sampai data terakhir: (i) Tempatkan data pada lokasi masing-masing dengan perhitungan: lokasi = key mod (ukurantabel - ukuran cellar) (ii) Jika lokasi tesebut masih kosong, simpan data pada alamat lokasi tersebut, kemudian lanjutkan ke langkah (3). Jika lokasi tersebut telah ditempati data sebelumnya, maka lanjutkan ke langkah (iii) (iii) Cari lokasi tabel paling bawah yang kosong. (iv) Lakukan proses ini sampai ditemukan lokasi yang kosong untuk menempatkan data tersebut. Simpan data pada lokasi kosong yang telah ditemukan. Simpan alamat lokasi kosong tersebut pada field link untuk data yang bersangkutan. 3. Selesai.
Untuk Pencarian Data Ulang dan Penghitungan Jumlah Probe: 1. Lakukan perulangan untuk data pertama sampai data terakhir: (i) Hitung lokasi data yang dicari dengan perhitungan: lokasi = nilai data mod ukurantabel (ii) Jika data yang ditemukan pada lokasi tersebut sesuai dengan data yang dicari, maka lanjutkan langkah (1) untuk data berikutnya dan jumlahprobe=jumlahprobe + 1. Jika data yang ditemukan tidak sesuai dengan yang dicari, lakukan pencarian ke lokasi yang ditunjuk pada field link. Lakukan proses (ii) in; sampai data yang ditemukan sesuai. Optimalitas Cellar... (Irene Astuti L.) 59
2.
Hitung rata-rata jumlah pengambilan seluruh data dengan perhitungan : Rata_rata_probe=jumlahprobe / jumlahdata
3.2.2 Program Pada program pembangkitan data acak yang dilakukan adalah: (i) Mengosongkan array dari data yang telah ada sebelumnya (ii) Jika ukuran tabel yang diinputkan lebih kecil dari jumlah data yang diinputkan, maka proses pengacakan tidak dilakukan, tetapi meminta inputan baru. Jika ukuran tabel lebih besar atau sama dengan jumlah data maka proses pengacakan dilakukan. (iii) Pengacakan dibatasi supaya data yang diacak tidak sama dengan data acak yang pernah dihasilkan sebelumnya. Jadi setiap kali mengacak data dilakukan pembandingan dengan semua data yang sudah dihasilkan sebelumnya. Jika ada yang sama maka pengacakan diulang untuk data tersebut. (iv) Data hasil pengacakan disimpan dalam array, untuk selanjutnya dilakukan proses hashing. Sedangkan yang dilakukan pada program coalesced hashing tanpa cellar adalah: (i) Data yang telah dihasilkan secara acak oleh program dikenai fungsi hash yaitu f(data) = nilai_data mod ukuran_tabel, sehingga menghasilkan nilai tertentu yang akan menentukan lokasi data tersebut akan disimpan. (ii) Jika pada lokasi tersebut tidak ada data yang lain, maka data tadi langsung ditempatkan di lokasi tersebut. Jika ternyata pada lokasi tersebut telah ada data dan alamat link pada lokasi tersebut tidak menunjuk ke lokasi manapun, maka data disimpan pada lokasi paling akhir dari tabel yang masih kosong. Kemudian alamat link dari data tersebut diisi dengan alamat lokasi kosong tersebut. Kemudian penunjuk lokasi paling akhir dinaikkan ke lokasi kosong yang ada di atasnya. (iii) Jika ternyata pada lokasi tersebut telah ada data dan alamat link pada lokasi tersebut juga sudah menunjuk ke lokasi yang lain, maka dilakukan pengecekan seperti langkah (ii) di lokasi yang ditunjukkan oleh alamat link tadi. Proses ini diulang terus sampai ditemukan tempat yang kosong. Proses yang dilakukan pada program coalesced hashing dengan cellar hampir sama dengan proses coalesced hashing tanpa cellar, hanya saja fungsi hash yang digunakan berbeda, yaitu f(data) = nilai_data mod (ukuran_tabel - ukuran_ce//ar) sehingga proses ini tergantung pada persentase cellar yang diinputkan. Nilai pembagi ini sebenarnya merupakan ukuran daerah penyimpan utama, sehingga lokasi akhir dari tabel yang dialokasikan sebagai cellar tidak akan terisi oleh data hasil pengalamatan asli, tetapi hanya berisi data hasil proses link. Demikian pula untuk menghitung jumlah probe sama dengan cara menghitung jumlah probe pada metode coalesced hashing tanpa ce//ar. 4. PERCOBAAN DAN ANALISA Program yang telah dibuat kemudian digunakan untuk melakukan percobaan coalesced hashing. Hasil yang diperoleh kemudian direpresentasikan dalam bentuk tabel dan grafik.
60 Jurnal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
4.1 Menu Hashing Menu Hashing ini digunakan untuk mengimplementasikan metode coalesced hashing yang terdiri dari coalesced hashing tanpa cellar dan coalesced hashing dengan cellar. Informasi yang harus dinputkan adalah jumlah data, ukuran tabel dan persentase cellar. Sedangkan ukuran main area dan ukuran overflow area akan ditampilkan secara otomatis oleh program sesuai dengan persentase cellar yang diinputkan. Dengan menekan tombol Acak Data, maka sejumlah data akan dibangkitkan secara acak oleh program sebanyak jumlah data yang diinputkan tadi, kemudian diatur penempatannya dengan metode coalesced hashing. Metode coalesced hashing tanpa ce//ar dapat dilakukan terhadap sejumlah data tersebut dengan menekan tombol Coalesced hashing Tanpa Cellar. Sedangkan metode coalesced hashing dengan cellar dapat dilakukan dengan menekan tombol Coalesced hashing Dengan Cellar. Kedua proses tersebut akan menempatkan data sesuai dengan fungsi hash masing-masing, sekaligus menghitung jumlah pengambilan (probe) untuk masing-masing data serta menampilkan rata-rata jumlah pengambilan data tersebut. Optimalitas Cellai dalam Coalesced Hashing Dim oleh pengguna Jumlah data
Ukuran
10
Main Aiea
Ukuran Tabel| HI
Overflow Area
Protentace Cellai MO
0 1 2 3 4 5 6 7 8 9
DataAsli
4
% i
Hashing Tanpa Cellar
Acak data Address
I6
Tanpa Cellar
I Link
1 Probe
40
1
9
31
2
1
40
11
-
1
•
49
8
2G
5
31
35
47
26
5
47
-
2
8
49
3
2
11
9
8
2 1
4
1 -
Rata-rata Probe 1A
1
2
H ashing Dengan Ceiiar
1)enqan Cellar
1 J19 ;>6 !i to :)5 1i ii <17 :31
j Link 9 G
8 0 7
Probe 1 1 1 1 1 2 2 3 2 4
Rata-rata Probe [T
&eluar Gambar 3. Hasil keluaran dari Menu Hashing
Untuk keperluan penelitian, proses pembangkitan data acak dapat dilakukan berulang kali. Untuk setiap kali pembangkitan data acak dapat dilakukan satu kali proses coalesced hashing tanpa cellar dan beberapa kali proses coalesced hashing dengan cellar dengan persentase cellar yang bervariasi sesuai yang diinputkan oleh Optimalitas Cellar... (Irene Astuti L.)
61
pengguna. Pada dasarnya informasi yang diharapkan dari program ini untuk keperluan penelitian hanyalah nilai rata-rata jumlah pengambilan (probe) untuk masing-masing data saja. Namun untuk keperluan pemahaman pengguna lebih lanjut mengenai metode coalesced hashing ini maka program ini juga dirancang untuk menghasilkan keluaran yang bersifat visual berupa tabel hash beserta alamat link untuk masing-masing data. Keluaran tersebut ditampilkan dalam bentuk grid untuk mempermudah pengguna melihatnya, seperti yang ditampilkan pada gambar3. 4.2 Analisa Mula-mula dilakukan penelitian untuk ukuran tabel = 1000 dan jumlah data bervariasi mulai 100, 200, 300, dan seterusnya sampai 1000 data. Untuk masingmasing jumlah data, dilakukan pembangkitan data acak 10 kali. Untuk setiap kali mengacak data, diterapkan satu kali proses coalesced hashing tanpa cellar dan beberapa kali proses coalesced hashing dengan cellar dengan persentase cellar mulai 10%, 20%, 30%, dan seterusnya sampai dengan 90%. 4.2.1 Tabel Dan Grafik Hasil Percobaan Dari hasil percobaan yang dilakukan, dihitung rata-rata dari nilai rata-rata jumlah probe untuk 10 kali pengacakan data, sehingga diperoleh kesimpulan bahwa nilai rata-rata jumlah probe yang paling kecil terjadi pada saat proses coalesced hashing dilakukan tanpa cellar dan dengan persentase cellar tertentu. Selanjutnya akan dilakukan langkah-langkah percobaan yang sama dengan di atas, untuk persentase cellar dengan jangkauan yang lebih kecil, yang nilainya berkisar pada nilai optimal tersebut. Hasil percobaan untuk persentase cellar antara 10% sampai 90% tercantum pada tabel 3.
Tabel 3 Tabel rata-rata probe untuk ukuran tabel=1000 dengan berbagai jumlah data dan persentase cellar yang bervariasi antara 10 % - 90%
Jumlah Data 100 200 300 400 500 600 700 800 900 1000
Tanpa Cellar 1 1 1.066 1.11 1.187 1.256 1.316 1.4185 1.5 1.62
10
20
1 1.02 1.077 1.132 1.179 1.236 1.31 1.402 1.49 1.585
1 1.031 1.09 1.145 1.215 1.282 1.345 1.401 1.523 1.616
Dengan Persentase 40 50 1 1 1 1.085 1.101 1.059 1.12 1.155 1.2 1.174 1.24 1.29 1.26 1.326 1.4 1.505 1.354 1.415 1.4 1.58 1.5 1.679 1.483 1.567 1.58 1.678 1.8 1.67 1.765 1.9 30
Cellar (%) 70 60 1.046 1.1 1.134 1.243 1.28 1.39 1.578 1.373 1.736 1.526 1.65 1.905 2.027 1.785 2.157 1.883 2.03 2.3 2.15 2.4
62 Jurnal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
80 1.164 1.387 1.633 1.856 2.09 2.286 2.47 2.602 2.74 2.844
90 1.426 1.901 2.28 2.6 2.84 3.013 3.15 3.253 3.335 3.4
Untuk lebih mempemudah pembacaan data dan analisa, maka data pada tabel 3 direpresentasikan dalam bentuk grafik pada gambar 4. Grafik Hubungan antara Prosentase Cellar dengan Jumlah Probe rata-rata untuk Kepadatan Data 100 sampai 1000
3.5
Ob
:'0
10
30
40
50
Prosentase Cellar (%)
Gambar 4. Grafik Hubungan antara Persentase Cellar dengan Probe rata-rata untuk data 100 sampai 1000
Pada proses coalesced hashing dengan cellar, terlihat bahwa nilai probe rata-rata yang paling rendah terjadi pada saat persentase cellar antara 10% sampai 20%. Maka untuk mencari nilai yang lebih optimal lagi, dilakukan percobaan yang sama, tetapi dengan jangkauan yang lebih kecil, yaitu untuk persentase cellar antara 10% sampai 20%. Hasil percobaan tersebut ditampilkan pada tabel 4.
Jumlah Data
100 200 300 400 500 600 700 800 900 1000
Tabel 4. Tabel rata-rata probe untuk ukuran tabel=1000, dengan berbagai jumlah data dan persentase cellar yang bervariasi antara 10 % - 20 % Tanpa Denqan Persentase Cellar (%) Cellar 10 12 13 11 17 14 15 16 18
1 1 1.089 1.11 1.19 1.24 1 315 1.323 1.518 1.613
1
1
1
1
1
1
1
1
1
19 1
20 1
1,026 1.08 1.126 1.185 1.247
1.021 1.082 1.141 1.18 1.266 1.31 1.308 1.485 1.58
1.016 1.073 1.142 1.19 1252 1.312
1.021 1.083 1.142 1.19 1.26
1.102 1.077 1.143 1.19 1.25
1.3 1.5
1.304 1.49 1.59
1.317 1.48 1.59
1.026 1.085 1.14 1.347 1.284 1.335 1.338 1.508 1.62
1.04 1.084 1.162 1.214 1.287 1.334 1.35 1.502 1.61
1.047
1.3
1.031 1.07 1.149 1.214 1.258 1.325 1.333 1.485 1.575.
1.036 1.09 1.15
1.3
1.031 1.08 1.143 1.195 1.266 1.265 1.32 1.495
1.3 1.303 1.485 1.59
1.61
Optimalitas Cellar ... (Irene Astuti L.)
1.6
1.2 1.276 1.34 1.336 1.492 1.575
63
1.1 1.162 1.229 1.294 1.35 1 355 1.503 1.602
Untuk lebih mempemudah pembacaan data dan anatisa, maka data pada tabel 4 dicantumkan dalam bentuk grafik pada gambar 5.
Gambar 5. Grafik Hubungart antara Persentase cellar dengan Probe Rata-rata untuk data 100 sampai 1000 dengan persentase cellar 10% sampai 20%
4.3.2 Perbandingan Coalesced Hashing Tanpa Cellar dan Coalesced Hashing Dengan Cellar Pada saat jumlah data=1000, terlihat bahwa proses coalesced hashing baik tanpa cellar maupun dengan cellar yang berukuran 10% sampai dengan 50% menghasilkan nilai probe rata-rata =1. Hal ini menunjukkan bahwa untuk jumlah data yang sangat kecil dibandingkan ukuran tempat penyimpanan yang disediakan, sebenarnya belum diperlukan adanya cellar. 4.3.3 Perbandingan Jumlah Probe Rata-rata untuk Kepadatan Data yang Berbeda Dari tabel 3 terlihat bahwa pada saat jumlah data = 100 sampai 200, proses coalesced hashing tanpa cellar menghasilkan nilai probe rata-rata = 1 . Hal ini menunjukkan bahwa pada saat itu tidak terjadi tabrakan sehingga masing-masing data langsung dapat ditempatkan pada alamatnya masingmasing sesuai dengan fungsi hash. Hal ini disebabkan karena jumlah data yang disimpan jauh lebih kecil dibandingkan ukuran tempat penyimpan yang disediakan. Dari tabel 3 dan gambar 6 terlihat bahwa jika jumlah data makin besar, maka nilai probe rata-rata juga makin besar. Hal ini disebabkan karena data yang harus disimpan dengan fungsi hash semakin banyak, sehingga menyebabkan kemungkinan fungsi hash tertentu menghasilkan nilai yang sama semakin besar. Sebagaimana telah dijelaskan dalam landasan teori bahwa jika fungsi hash 64 Jurnal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
menghasilkan nilai yang sama maka akan terjadi tabrakan antara data yang d\-hash dengan data sebelumnya yang menghasilkan nilai yang sama. Jika terjadi tabrakan maka perlu dilakukan link ke alamat lain. Apabila terjadinya tabrakan semakin sering, maka semakin banyak pula link yang terjadi. Hal ini akan menyebabkan proses pengambilan suatu data perlu dilakukan beberapa kali sebelum akhirnya data yang dimaksud ditemukan. 4.3.4 Perbandingan Persentase Cellar yang berbeda Jika nilai probe rata-rata pada proses coalesced hashing tanpa cellar dan proses coalesced hashing dengan persentase cellar 10% dibandingkan, terlihat bahwa pada saat jumlah data = 100 sampai dengan 400, nilai probe rata-rata untuk proses tanpa cellar lebih kecil daripada untuk proses dengan cellar 10%. Sedangkan pada saat jumlah data = 500 sampai dengan 1000, nilai probe rata-rata pada proses tanpa cellar lebih besar daripada untuk proses dengan cellar 10%. Hal ini menunjukkan bahwa pada kepadatan data kurang lebih 0% - 40% dari ukuran tempat penyimpanan yang disediakan, penggunaan cellar belum terlalu diperlukan. Penggunaan cellar baru dirasakan efektif pada kepadatan data lebih dari 50% karena pada saat itu mulai banyak terjadi tabrakan. Dari tabel 3 juga terlihat bahwa semakin besar persentase cellar, maka nilai probe rata-rata akan makin besar. Hal ini disebabkan karena fungsi hash yang digunakan untuk coalesced hashing tanpa cellar adalah sebagai berikut: Fungsi hash = key mod (ukuran area primer) = key mod (ukuran tabel-ukuran cellar) sehingga semakin besar ukuran cellar berarti akan menyebabkan nilai pembagi pada fungsi hash ; yang juga merupakan ukuran area primer akan semakin kecil. Jika nilai pembagi pada fungsi hash tersebut semakin kecil maka kemungkinan nilai sisa pembagian yang terjadi pada fungsi hash tersebut juga sedikit. Misalnya jika nilai pembagi adalah 10 maka kemungkinan sisa pembagian yang terjadi adalah 0,1,2,3,4,5,6,7,8,dan 9, sedangkan jika pembagi adalah 6 maka kemungkinan sisa pembagian yang terjadi hanyalah 0,1,2,3,4, dan.5. Padahal sebagaimana telah dijelaskan dalam landasan teori bahwa sisa pembagian yang diperoleh dari fungsi hash akan menentukan alamat penyimpanan data yang bersangkutan. Jika kemungkinan nilai sisa pembagian yang terjadi semakin kecil, berarti kemungkinan terjadinya tabrakan akan semakin besar. Hal ini akan memperlambat proses pencarian data karena data disimpan bukan pada alamat sesungguhnya tetapi pada alamat link-nya. 4.3.5 Pencarian Opiimalitas pada Jangkauan Persentase Cellar yang Lebih Kecil Percobaan ini dilakukan pada jangkauan persentase cellar yang lebih kecil yaitu antara 10% sampai 20 %, dengan kenaikan setiap 1%. Seperti halnya pada percobaan sebelumnya yang menggunakan jangkauan persentase cellar yang lebih besar, pada percobaan ini juga terlihat bahwa jika jumlah data makin banyak, maka nilai probe rata-rata juga makin besar. Tetapi pada percobaan ini tidak dapat dipastikan bahwa semakin besar persentase cellar, maka nilai probe rata-rata akan makin besar seperti pada percobaan sebelumnya. Untuk jumlah data yang sama dan ukuran cellar yang berbeda, nilai probe rata-rata yang terjadi hampir sama. Dengan demikian ukuran cellar yang paling optimal dalam hal ini terdapat di antara 10% sampai dengan 20%. Hal ini berlaku untuk setiap kepadatan data.
Optimalitas Cellar... (Irene Astuti L.)
65
5. PENUTUP Berdasarkan penelitian yang dilakukan, diperoleh beberapa kesimpulan dan saran yang terhubungan dengan optimalitas cellar dalam coalesced hashing dan penerapannya pada basis data sederhana. 5.1. Kesimpulan 1. Jika jumlah data yang akan disimpan jauh lebih kecil dibandingkan ukuran tempat penyimpanan yang disediakan, penggunaan cellar kurang diperlukan, bahkan justru dapat mempersulit dan memperbanyak proses penyimpanan dan pencarian. Penggunaan cellar baru terasa dibutuhkan secara efektif pada kepadatan data lebih besar dari 50% dari ukuran tempat penyimpanan. 2. Ukuran cellar yang paling optimal dijurripai pada persentase 10%- 20% dari ukuran tempat penyimpanan yang disediakan. Hal ini berarti tempat penyimpanan yang dialokasikan untuk penyimpanan utama sebesar 80%-90%, sedangkan untuk daerah overflow sebesar 10%-20% . 3. Semakin besar persentase cellar, maka kemungkinan terjadinya tabrakan akan semakin besar karena nilai pembagi untuk fungsi hash semakin kecil, sehingga nilai sisa pembagian; yang akan berfungsi sebagai alamat data; yang mungkin terjadi semakin sedikit. Semakin besar persentase ce//ar akan menyebabkan rata-rata jumlah probe semakin besar. 4. Jika jumlah data semakin besar maka semakin banyak kemungkinan terjadi tabrakan, sehingga rata-rata jumlah probe juga semakin besar. Jika jumlah data jauh lebih kecil dibandingkan ukuran tempat penyimpanan yang disediakan, maka kemungkinan terjadinya tabrakan kecil, sehingga data dapat langsung ditempatkan pada alamatnya masing-masing tanpa perlu melakukan proses link ke alamat lain. 5.2. Saran 1. Analisis yang tepat dan ketelitian data yang tinggi serta makin banyak jumlah percobaan yang dilakukan akan mendukung diperolehnya hasil penelitian yang lebih akurat. Oleh sebab itu masukan yang diberikan oleh pengguna harus bermacam-macam dengan mempertimbangkan kemungkinan data yang terjadi. 2. Penelitian ini masih dapat dikembangkan untuk berbagai jenis kondisi data, tidak hanya untuk data acak saja, tetapi juga kondisi data yang lain. DAFTAR PUSTAKA 1. Folk, Michael J., File Structures, Addison Wesley, 1998 2. Frerking, Gary, Borland Delphi how-to, Emeryville: The Waite Group, 1995 3. Loomis, Mary E.S, Data Management and File Processing, New Jersey: Prentice Hall, 1983 4. Matcho, Jon dan David R. Faulkner. Edisi Khusus Panduan Penggunaan Delphi, Yogyakarta: Penerbit ANDI Yogyakarta, Edisi Pertama, 1997 5. Tharp, Alan L., F/Ve Organization and Processing, New York: John Wiley & Sons, Inc., 1988 6. Vitter, J.S., "Implementations for Coalesced Hashing", Communications of the ACM, 25, December 1982. 7. Vitter.J.S., "Analysis of the Search Performance of Coalesced Hashing", Journal of the ACM, April 1983. 8. Wiederhold, Gio, File Organization for Data Base Design, New York: McGraw Hill Book Company, 1987 66 Jurnal llmiah llmu Komputer, Vol. 1 No. 2 Mei 2003: 53-67
Biodata Penulis Nama Lengkap Gelar yang diperoleh Institusi Bidang Afiliasi Mata kuliah yang diajar
Research Interest
Irene Astuti Lazarusli S1 (Sarjana Komputer) Universitas Kristen Duta Wacana Yogyakarta Teknik Informatika FIK - Teknik Informatika UPH Praktikum Statistika Deskriptif, Praktikum Sistem Informasi Manajemen, Praktikum Pemrograman Modular, Praktikum Analisis Algoritma, Praktikum Pemrograman Berorientasi Objek, Praktikum Sistem Basis Data, Pengantar Komputer Untuk Komunikasi (di Jurusan Komunikasi FISIP UPH) Data Base and Information System, Information Retrieval, Artificial Intelligence & Neural Network
Optimalitas Cellar... (Irene Astuti L.)
67
