Searching
SEARCHING (PENCARIAN) PENDAHULUAN Pada bab ini akan membahas beberapa metoda pencarian data (searching) untuk menemukan suatu informasi dari sejumlah data yang ada. Pada dasarnya cara mengorganisir data sedikit banyak akan mempengaruhi efisiensi pencarian. Dalam kehidupan sehari-hari, misalnya mencari suatu kata dalam sebuah kamus, atau mencari nomor telepon di buku telepon merupakan suatu proses pencarian.
1. ISTILAH-ISTILAH DASAR Ada beberapa istilah dasar yang perlu kita ketahui dalam proses searching (pencarian), yaitu sebagai berikut : Pencarian data (table look-up atau storage and retrieval information) adalah suatu proses untuk mengumpulkan sejumlah informasi di dalam pengingat komputer dan kemudian mencari kembali informasi yang diperlukan secepat mungkin. Secara umum kita akan memakai anggapan bahwa sejumlah N rekaman telah tersimpan dalam pengingat komputer, dan persoalannya adalah mencari suatu rekaman yang kita inginkan Setiap rekaman yang terdiri dari sejumlah data disebut dengan medan (field). Setiap rekaman terdapat suatu medan yang mempunyai nilai tertentu. Medan yang nilainya bisa membedakan satu rekaman dengan rekaman lain disebut dengan medan kunci (field key), disingkat sebagai kunci. Kumpulan dari semua rekaman yang kita miliki disebut dengan berkas (file) atau tabel Hubungan antara kunci dengan rekaman bisa merupakan hubungan yang sederhana atau kompleks. Pada bentuk yang paling sederhana, kunci yang terletak di dalam rekaman disebut dengan internal key atau embedded key. Sedangkan, tabel yang terpisah dari tabel utama yang berisi kunci yang menunjuk pada rekaman tertentu disebut dengan external key. Kunci primer (primary key) adalah sebuah kunci yang terdapat pada setiap rekaman yang dapat membedakan semua rekaman dalam suatu berkas.
1
Searching
Contoh: Data setiap mahasiswa pada suatu universitas. Untuk setiap mahasiswa, dipastikan bahwa nomor mahasiswanya pasti berlainan. Maka nomor mahasiswa dapat dijadikan sebagai kunci primer. Kunci yang digunakan untuk membedakan setiap kunci tidak selalu terdiri dari sebuah medan saja. Ada kalanya terdiri dari beberapa medan sekaligus. Sebagai contoh kita menggunakan data pribadi di atas. Ada kalanya selain nomor mahasiswa, maka kota asal mahasiswa tersebut juga bisa digunakan sebagai kunci. Dalam hal ini tentu akan ada sejumlah mahisiswa yang berasal dari kota yang sama. Kunci yang demikian ini disebut dengan kunci sekunder (secondary key). Algoritma pencarian (searching algorithm) adalah algoritma yang menerima argumen K (sebagai kunci), dan dengan langkah-langkah tertentu akan mencari rekaman yang kuncinya bernilai K. Hasil dari pencarian ada dua yaitu data yang dicari ditemukan (succesful) atau tidak ditemukan (unsuccessful). Pencarian yang berhasil menemukan rekaman disebut retrival. Algoritma pencarian dan penyisipan (search and insertion algorithm) adalah algoritma yang menambahkan ke dalam berkas yang sudah ada jika data yang dicari tersebut tidak ditemukan. Metoda pencarian data bisa dikelompokkan dengan beberapa cara, Kelompok pertama, yaitu : 1. Pencarian internal (internal searching). Pada pencarian ini semua rekaman yang diketahui berada dalam pengingat computer 2. Pencarian eksternal (external searching). Pada pencarian ini tidak semua rekaman yang diketahui berada dalam pengingat komputer, tetapi ada sejumlah rekaman yang tersimpan dalam penyimpan luar, misalnya disket, dll. Kelompok kedua, yaitu : 1. pencarian statis (static searching), dalam pencarian ini banyaknya rekaman yang diketahui dianggap tetap 2. pencarian dinamis (dynamic searching). dalam pencarian ini banyaknya rekaman yang diketahui bisa berubah-ubah yang disebabkan oleh penambahan atau penghapusan suatu rekaman. Pemilihan struktur data yang digunakan untuk menyimpan data yang diketahui akan mempengaruhi efisiensi pencarian itu sendiri. Pada bagian ini struktur data
2
Searching
yang digunakan yaitu, menggunakan vektor dengan deklarasi tipe array dimensi 1, dan senarai berantai (menggunakan pointer). Contoh : Vektor yang digunakan mempunyai deklarasi sebagai berikut: type Larik
= array[l..1000] of integer;
Untuk senarai berantai, deklarasi simpul yang digunakan adalah: type List =
^Simpul;
Simpul
record
=
Info
: integer;
Kanan
: List;
end;
2. METODE PENCARIAN BERURUTAN 2.1 Pada Tabel Acak Metoda ini adalah metode yang paling sederhana dari sejumlah metoda pencarian. Secara garis besar metoda ini bisa dijelaskan sebagai berikut. Dari vektor yang diketahui, data yang dicari dibandingkan satu per satu sampai data tersebut ditemukan atau tidak ditemukan. Pada saat data yang dicari sudah ketemu, maka proses pencarian langsung dihentikan. Tetapi jika data yang dicari belum ketemu, maka pencarian diteruskan sampai seluruh data dibandingkan. Jika tidak ditemukan, maka data tersebut akan ditambahkan sebagai elemen terakhir dari vektor yang diketahui Kelemahan metode ini adalah jika untuk vektor dengan N elemen maka harus dilakukan pencarian sebanyak N kali pula. Algoritma pencarian_vektor_berurut 1. Vektor Ai yang telah terurut, i = 1, 2, 3, ..., N 2. (inisialisasi). Ada=false. 3. Untuk i:=1 sampai N lakukan Jika X = A[i] maka : Ada = true Posisi = i i =N 4. Selain itu N A[i]
= N+1 =X
3
Searching
5. Selesai Perhatikan prosedur program pada bagian lampiran. (Program 1. Pencarian menggunakan metode pencarian berurutan pada sebuah vector) Untuk implementasi menggunakan struktur data yang berupa senarai berantai, prosedurnya disajikan dalam Program 2. Dalam prosedur tersebut, s adalah pointer yang menunjuk pada simpul pertama, dan s1 adalah simpul yang menunjuk pada simpul terakhir dalam senarai berantai. Pointer yang menunjuk ke simpul terakhir diperlukan karena apabila data yang dicari tidak ditemukan, maka simpul baru akan disambungkan pada senarai berantai tersebut. (Program 2. Pencarian menggunakan metoda pencarian berurutan pada rebuah senarai berantai). Bila ingin menambah isi array, perlu diperhatikan jumlah elemen array yang telah dideklarasikan agar tidak terjadi kesalahan. Dengan menggunakan senarai berantai, hal ini tidak perlu terjadi sejauh kapasitas pengingat masih mencukupi. Keuntungan lain pemakaian senarai berantai lebih mempermudah untuk melakukan penghapusan. Dalam array, jika melakukan penghapusan suatu elemen, maka kita harus melakukan penggeseran, yang banyaknya penggeseran tergantung terhadap letak elemen yang akan dihapus. Jika tidak ada penambahan dan penghapusan elemen, berarti kita akan melakukan pencarian pada tabel berukuran tetap, yaitu N, maka banyaknya pembandingan tergantung terhadap letak elemen yang akan dicari. Jika elemen yang dicari terletak sebagai elemen pertama, berarti pembandingan cukup dilakukan satu kali. Sebaliknya jika elemen yang dicari terletak sebagai elemen terakhir, maka kita perlu melakukan pembandingan sebanyak N kali. Notasi yang sering digunakan untuk menyatakan suatu persamaan yang berorde N adalah O(N).
2.2 Pencarian pada Tabel yang Sudah Diurutkan Ada beberapa teknik yang dapat meningkatkan efisiensi pencarian, misalnya pada tabel yang sudah diurutkan dan ukuran tabel tersebut tetap. Secara garis besar proses pencarian pada tabel yang sudah terurut sebagai berikut.
4
Searching
Dimulai dari elemen pertama pada tabel dilakukan pembandingan dengan elemen yang dicari. Jika elemen dalam tabel masih lebih kecil dari elemen yang dicari, pencarian diteruskan. Jika sudah lebih besar, pencarian dihentikan dan bisa dipastikan bahwa elemen yang dicari memang tidak ditemukan. Jika elemen yang dicari tidak ditemukan dan kita ingin menyisipkan elemen tersebut pada posisinya yang tepat, maka seringkali diperlukan adanya penggeseran terhadap eleimen-elemen yang nantinya akan terletak pada subskrib yang lebih besar dari elemen yang dicari. Algoritma di bawah ini menjelaskan proses di atas untuk diterapkan pada sebilah vektor. Algoritma cari_vektor_urut_naik 1. vektor Ai yang telah terurut dengan i= 1, 2, 3, ..., N 2. (inisialisasi)
Ada = false i=1 j=0
3. Untuk i = 1, 2, ..., N atau ada = true : Jika A[i] = X, maka Posisi = i, ada = true Jika tidak, jika A[i] > X, maka j = i dan i = N-1 i = i+1 Jika ada = false maka Jika j = 0 maka A[N+1] =X Jika tidak, maka Untuk i = n, n-1, n-2, ..., j A[i+1] = A[i] A[j] = X 4. N = N+1 5. Selesai. (Program 3.Pencarian menggunakan metoda pencarian berurutan pada vektor yang elemennya telah diurutkan secara urut naik)
5
Searching
Untuk senarai berantai, seperti pada contoh sebelumnya, s adalah pointer yang menunjuk ke simpul pertama dan s1 adalah pointer yang menunjuk simpul terakhir dari senarai berantai. Pointer Templ menunjukkan posisi jika kita ingin menyisipkan simpul yang baru. (Program 4. Pencarian penggunaan metoda pencarian berurutan pada senarai)
3. PENCARIAN BINER Cara lain untuk mencari data pada vektor yang elemennya telah diurutkan adalah menggunakan metoda pencarian biner (binary search). Metoda ini akan jauh lebih cepat dibanding dengan metoda berurutan. Setelah vektor diketahui diurutkan, vektor tersebut dibagi menjadi dua subvektor dengan jumlah elemen yang sama. Kemudian data dibandingkan dengan data terakhir dari subvektor pertama. Jika data yang dicari lebih kecil, maka pencarian diteruskan pada sub vektor pertama dengan terlebih dahulu membagi dua subvektor tersebut. Tetapi jika data yang dicari lebih besar dari data terakhir pada subvektor pertama, berarti data yang dicari kemungkinan terletak pada subvektor kedua. Dengan demikian pencarian dilakukan pada subvektor kedua. Proses di atas diulang sampai data yang dicari ditemukan atau tidak ditemukan. Contoh : kita akan mencari data yang bernilai 20 pada vektor berikut ini. 2
8
11
15
18
19
20
22
35
40
45
Vektor di atas kita pecah menjadi 2 (dua) subvektor sebagai berikut:
2
8
11
15
18
19
20
subvektor 1
22
35
40
45
subvektor 2
karena data yang bernilai 20 terdapat pada subvektor 2, maka pencarian dilaksanakan pada subvektor 2, subvektor 1 tidak perlu dihiraukan lagi. Subvektor 2 kemudian dipecah lagi menjadi: 19
20
22
subvektor 2.1
35
40
45
subvektor 2.2
6
Searching
Sekarang, data yang bernilai 20 terdapat pada subvektor 2.1. Dengan demikian subvektor 2.1 dipecah lagi. Proses diteruskan sampai data yang dicari ketemu atau tidak ketemu. Dari ilustrasi di atas maka algoritmanya sebagai berikut: Algoritma Biner 1. Vektor Ai yang telah terurut, i = 1, 2, 3, ..., N 2. Baca data yang dicari (X). 3. (Inisialisasi.) Ada = f alse Atas = N Bawah = 1. 4. Selama atas >= Bawah, maka lakukan Tengah = (Atas + Bawah) div 2. Jika X > A[Tengah] maka Bawah = Tengah + 1. Jika X < A[Tengah], maka Atas = Tengah - 1. jika tidak (x = A[tengah] ) maka Ada = true Posisi = Tengah Bawah=Atas+l. 5. Jika ada = true, maka data ketemu. Cetak “ DATA KETEMU” Posisi = posisi Jika tidak, cetak “DATA TIDAK ADA” Untuk i = N, N-1, N-2, ..., bawah A[i] = A[ i – 1] A[bawah] = X 6. Selesai. (Program 5. Pencarian menggunakan metoda pencarian biner (binary search)) Sebagai tambahan, untuk pencarian biner ini juga dapat dilakukan pada struktur data bertipe pohon, berikut penjelasannya : Pada materi sebelumnya telah dijelaskan cara membuat. suatu pohon biner, yaitu suatu simpul diletakkan dalam cabang kiri bila isi informasinya lebih kecil dibanding informasi akar; atau sebagai cabang kanan bila informasinya lebih besar, sehingga nantinya pencarian data dapat dengan mudah dilakukan. Untuk jelasnya perhatikan dua buah pohon biner di bawah ini.
7
Searching
9
18 15
10
21
13 23
10
15 18
13
9
21
Pohon 1
Pohon 2 Gambar 1. Contoh Pohon Biner.
Dapat dilihat bahwa pencarian lebih cepat pada pohon 1. Contoh, untuk mencari bilangan 18, pada pohon 1 cukup dilaksanakan dengan satu kali pembandingan, sedangkan pada pohon 2, perlu dilakukan 6 kali pembandingan.
4. PENCARIAN BERURUTAN BERINDEX Metoda lain dari pencarian pada tabel yang sudah dalam keadaan urut adalah metoda pencarian berurutan terindex (indexed sequential search). Dalam hal ini diperlukan tabel tambahan yang disebut tabel index. Setiap elemen dalam tabel index berisi suatu kunci dan pointer yang menunjuk ke rekaman tertentu dalam tabel yang sesuai dengan kunci tersebut. Elemen dalam tabel index juga harus diurutkan seperti halnya dalam tabel yang asli Di bawah ini adalah suatu tabel yang menunjukkan daftar mahasiswa dari suatu universitas yang sudah diurutkan menurut nomor mahasiswanya. No. 1 2: 3. 4. 5. 6. 7 8 9. 10. 11 12: 13. 14. 15.
No. Mhs 851001 851102 851110 861001 861003 861101 861205 861207 871004 871014 871104 871109 871213 871216 871223
Nama Mahasiswa BAMBANG SUSILO SUSILO HADI.KUSUMO HADI SUSILO KUSUMO KUSUMO HADI SUSILO KUSUMO SUSILO HADI SUSILO KUSUMO HADI HADI KUSUMO SUSILO KUSUMO MENGGOLO YUDO MENGGOLO KUSUMO YUDO KUSUMO YUDO MENGGOLO YUDO MENGGOLO KUSUMO NADI SUDIRO HUSODO SUDIRO NADI HUSODO SUDIRO HUSODO NADI HUSODO SUDIRO NADI
Angkatan 85 85 85 86 86 86 86 86 87 67 87 87 87 87 87
Fakultas EKONOMI TEKNIK ELEXTRO TEKNIK ELEXTRO EKONOMI EKONOMI TEKNIK ELEXTRO TEKNIK KOMPUTER TEKNIK KOMPUTER EKONOMI EKONOMI TEKNIK ELEXTRO TEKNIK ELEXTRO TEKNIK KOMPUTER TEKNIK KOMPUTER TEKNIK KOMPUTER
8
Searching
Dari gambar di atas, dua digit paling depan menunjukkan tahun angkatan seorang mahasiswa masuk ke universitas; dua digit di tengah menunjukkan kode fakultas, 10 adalah Ekonomi, 11 adalah Teknik Elektro dan 12 adalah Teknik Komputer. Dua digit terakhir menunjukkan nomor urutnya. Tabel diatas bisa disimpan untuk diimplementasikan menggunakan suatu struktur data tertentu untuk mendukung pencarian berurutan terindex dengan beberapa cara. Cara pertama adalah dengan menggunakan tahun angkatan sebagai kunci. Cara kedua adalah menggunakan kode fakultas untuk kuncinya. Gambar berikut menunjukkan penyimpanan tabel di atas dengan tahun angkatan sebagai kuncinya. Tabel Data
Tabel Index
85 86 87
1 4 9 16
1001 1102 1110 1001 1003 1101 1205 1207 1004 1014 1104 1109 1213 1216 1223
BAMBANG SUSILO SUSILO HADI.KUSUMO HADI SUSILO KUSUMO KUSUMO HADI SUSILO KUSUMO SUSILO HADI SUSILO KUSUMO HADI HADI KUSUMO SUSILO KUSUMO MENGGOLO YUDO MENGGOLO KUSUMO YUDO KUSUMO YUDO MENGGOLO YUDO MENGGOLO KUSUMO NADI SUDIRO HUSODO SUDIRO NADI HUSODO SUDIRO HUSODO NADI HUSODO SUDIRO NADI
EKONOMI TEKNIK ELEXTRO TEKNIK ELEXTRO EKONOMI EKONOMI TEKNIK ELEXTRO TEKNIK KOMPUTER TEKNIK KOMPUTER EKONOMI EKONOMI TEKNIK ELEXTRO TEKNIK ELEXTRO TEKNIK KOMPUTER TEKNIK KOMPUTER TEKNIK KOMPUTER
Setiap elemen dalam tabel index terdiri dari dua buah medan, medan pertama menunjukkan tahun angkatan yang dimaksud, medan kedua berisi pointer yang menunjuk ke tabel data yang rekaman pertamanya berisi sambungan dari nomor mahasiswa yang tahunnya dinyatakan dalam medan pertama. Contoh, rekaman pertama dalam tabel index, pointernya bernilai 1; hal ini menunjukkan, bahwa 1 adalah nomor rekaman pertama dalam tabel data yang tahun angkatannya adalah 85. Dengan cara ini bisa dihitung mahasiswa yang masuk pada universitas tersebut untuk setiap angkatannya. Sebagai contoh, banyaknya mahasiswa yang masuk pada tahun 85 adalah sebanyak pointer tahun 86 dikurangi dengan pointer tahun 85, yaitu sebanyak 3 mahasiswa (4-1). Untuk mengetahui banyaknya, mahasiswa yang masuk pada tahun 87 diperlukan data sentinel yang nilai pointernya apabila dikurangi dengan nilai pointer pada tahun 87 adalah tepat. Dalam contoh di atas, elemen terakhir dari tabel index berisi adalah data sentinel.
9
Searching
Program berikut merupakan contoh pembentukan berkas berurutan berindex berdasarkan tahun angkatan. Dalam program tersebut, tipe data untuk tabel index dan berkas yang dimaksud dibuat berbeda (karena memang biasanya berbeda). Deklarasi tipe data untuk tabel index dan tabel data yang berisi data mahasiswa adalah sebagai berikut: type {* Elemen tabel index*} Index = record Kunci : string[2]; Awal : integer end; {* Elemen data*} Data = record No Mhs Nama,Fakultas end;
: string[4]; : string[20]
{*Tabel index*} Li = array(0..101] of Index; {* Tabel data *} Ld = array(l..100] of Data;
Dalam deklarasi di atas, ukuran tabel index dibuat seperti pada contoh di atas, untuk menyediakan tempat bagi data sentinel yang diperlukan. Data yang akan dicoba, sebelumnya sudah disimpan dalam berkas teks yang diberi nama COBADATA.DAT Secara singkat program di bawah ini bisa dijelaskan sebagai berikut. Setelah data dibaca dari berkas COBADATA.DAT (yang sudah dalam keadaan urut), dibentuk tabel index seperti dijelaskan di atas. Jika kita ingin mencari suatu nomor mahasiswa, terlebih dahulu nomor mahasiswa tersebut dipecah menjadi dua untai, yaitu untai yang berisi tahun angkatan dan untai yang berisi kode fakultas dan nomor urut mahasiswa. Pencarian dimulai dengan mencari tahun angkatan pada tabel index: Jika ditemukan, selanjutnya diteruskan dengan mencari data yang dimaksud pada tabel data. Jika tahun angkatan yang dicari tidak ditemukan, pencarian langsung dihentikan dan tidak perlu mencari pada tabel data, karena dalam tabel data yang terbentuk sesungguhnya merupakan sambungan dari tabel index. Untuk pencarian pada tabel index, dan tabel data dilakukan dengan cara pencarian berurutan. Berikut adalah cara penulisan data untuk disimpan sebagai berkas teks yang disimpan dengan nama COBADATA.DAT
10
Searching 851001 851102 851110 861001 861003 861101 861205 861207 871004 871014 871104 871109 871213 871216 871223
(Program 6.
BAMBANG SUSILO SUSILO HADI KUSUMO HADI SUSILO KUSUMO KUSUMO HADI SUSILO. KUSUMO SUSILO HADI SUSILO KUSUMO HADI HADI KUSUMO SUSILO KUSUMO MENGGOLO YUDO MENGGOLO KUSUMO YUDO KUSUMO YUDO MENGGOLO YUDO MENGGOLO KUSUMO HADI ' SUDIRO HUSODO SUDIRO HADI HUSODO SUDIRO HUSODO HADI HUSODO SUDIRO HADI
EKONOHI TEKNIK ELEKTRO TEKNIK ELEKTRO EKONOMI EKONOMI TEKNIK ELEKTRO TEKNIK KOMPUTER TEKNIK KOMPUTER EKONOMI EKONOMI TEKNIK ELEKTRO TEKNIK ELEKTRO TEKNIK KOMPUTER TEKNIK KOMPUTER TEKNIK KOMPUTER
Pencarian menggunakan metoda pencarian berurutan terindex).
Keuntungan yang bisa dilihat dari metoda ini adalah bahwa pencarian dapat dipercepat karena jika index yang dicari tidak ditemukan, maka berarti data yang akan dicari memang tidak ada dalam tabel data. Tetapi jika indexnya ditemukan, maka hanya sebagian kecil dari tabel data yang perlu kita cari. Hal ini tentu akan mempercepat pencarian dibanding harus mencari pada keseluruhan tabel data.
5. HASHING Pada metode-metode pencarian yang telah kita pelajari, secara umum banyaknya pembandingan untuk mencari suatu data atau rekaman yang diinginkan tergantung dari banyaknya data atau rekaman yang diketahui. Jika setiap data atau rekaman bisa ditemukan dengan sekali pemasupan terhadap tabel yang digunakan untuk menyimpan. data atau rekaman tersebut, maka lokasi data atau rekaman dalam tabel hanya tergantung dari kunci yang digunakan dan tidak tergantung dari kunci yang lain. Cara yang paling eflsien untuk mengorganisir tabel ini adalah dengan menggunakan larik. Jika kunci berupa integer, kunci tersebut sekaligus bisa digunakan sebagai subskrib dari larik yang dimaksud. Perhatikan contoh berikut. Sebagai contoh, suatu toko buku menjual 100 judul buku dan setiap buku mempunyai maksimum dua digit pengenal. Cara yang paling sederhana untuk menyimpan data di atas adalah: type NomorBuku = array [0..99] of string; var Buku : NomorBuku;
dimana Buku [ i ] menunjukkan buku yang mempunyai pengenal (nomor buku) ke i. Dalam contoh ini, nomor buku dimanfaatkan sebagai subskrib larik Buku.
11
Searching
Masalahnya jika nantinya toko buku tersebut menjual lebih dari 100 judul buku, dan buku-buku tersebut dikelompokkan sedemikian rupa sehingga masingmasing buku sekarang harus memerlukan kode dengan 7 buah digit maka dengan menggunakan larik seperti contoh di atas, pemilik toko buku harus menyediakan larik dengan 10 juta elemen untuk menyimpan data buku yang ada, ini jelas tidak praktis, sehingga diperlukan cara yang lebih efisien untuk mengatasi hal ini. Cara yang dimaksud pada dasarnya adalah untuk mengkonversikan kode buku (yang memerlukan 7 digit) menjadi integer dalam batas tertentu. Secara ideal, masingmasing kode buku harus bisa dikonversikan menjadi suatu integer yang berbeda, tetapi hal ini seringkali sukar untuk dilaksanakan. Dengan menggunakan contoh di atas, toko buku tersebut mempunyai kurang dari 1000 judul buku, dan tetap menggunakan kode yang terdiri dari 7 buah digit. Dengan demikian, pemilik toko buku tersebut cukup menyediakan larik dengan 1000 buah elemen yang nomor subskripnya 0-999, dan memanfaatkan 3 digit terakhir dari kode buku untuk menempatkan semua kode buku pada larik yang diketahui. Berikut ilustrasinya : (lihat Gambar. 2), dari gambar tersebut bisa kita lihat, bahwaj arak dua buah kode buku hanya ditentukan oleh 3 digit terakhhir, sehingga dua buku dengan kode 1002372 dan 1002772 akan mempunyai jarak yang lebih besar dibanding dua buku yang mempunyai kode 0001996 dan 5192998. Dari contoh di atas, kita bisa memperhatikan bahwa pemilik toko buku tersebut memerlukan suatu fungsi untuk mengkonversikan kode buku ke dalam nomor posisi dari larik yang diketahui. Fungi ini disebut dengan fungi hash. Metode pencarian yang memanfaatkan fungsi hash disebut dengan hashing atau hash addressing. Tujuan utama dalam penentuan fungsi hash adalah agar dua buah kunci yang berbeda tidak mempunyai nilai hash yang sama. Jika hal ini terjadi, akan menyebabkan terjadinya tabrakan (hash collision/hash clash). 5.1 Fungsi Hash Secara umum fungsi hash (H) adalah fungsi untuk mengkonversikan himpunan kunci rekaman (K) menjadi himpunan alamat pengingat (posisi subskrib dalam larik/L) dan bisa dituliskan dengan menggunakan notasi: H: K
L
Dua hal yang perlu dipertimbangkan dalam pemilihan fungsi hash adalah sebagai berikut:
12
Searching
1. Fungsi H harus mudah dan cepat dicari atau dihitung. 2. Fungsi H sebisa mungkin mendistribusikan posisi yang dimaksud secara uniform sepanjang himpunan L, sehingga banyaknya tabrakan yang mungkin terjadi bisa diminimalkan.
0
1023000
1
1236001
100 101
4321101
102
Gambar 2. Contoh Konversi Kunci 372
1002372
menjadi Posisi
373 374
5467374
772
1002772
773
7671773
774
996
0001996
997
1098997
998
5192998
Ada beberapa metode untuk memotong-motong kunci dalam himpunan K menjadi kombinasi tertentu yang akan dipakai sebagai fungsi H. Berikut disajikan beberapa metode untuk memotong-motong kunci sehingga bisa diperoleh fungi hash yang dengan mudah bisa dihitung. 1. Metode Pembagian Dalam cara ini kita bisa memilih suatu perubah m yang nilainya lebih besar dibanding banyaknya kunci dalam K, misalnya n dan biasanya dipilih suatu bilangan prima. Fungsi hashnya ditentukan sebagai:
13
Searching
H(k) = k mod m atau H(k) = k mod m + 1 Persamaan pertama dipilih apabila dinginkan alamat kunci adalah 0 sampai m - 1. Persamaan kedua dipilih jika diinginkan alamat kunci adalah 1 sampai m. Contoh : nomor mahasiswa terdiri dari 5 buah digit. Misalkan L terdiri dari 100 buah alamat yang masing-masing alamat terdiri dari 2 karakter: 00 ... 99. Nomor mahasiswa yang diketahui misalnya 10347, 87492, 34212, dan 88688. Untuk menentukan alamat dari keempat nomor mahasiswa ini kita pilih suatu bilangan prima yang dekat dengan 99, misalnya m = 97. Dengan menggunakan fungsi H(k) = k mod m, diperoleh: H(10347) = 65
H(87492) = 95
H(34212) = 68
H(88688) = 30
Dengan demikian, nomor mahasiswa 10347 akan disimpan dalam alamat 65, nomor mahasiswa 87492 akan disimpan dalam alamat 95, nomor mahasiswa 34212 akan disimpan dalam alamat 68, dan nomor mahasiswa 88688 akan disimpan dalam alamat 30. Jika dipilih fungsi H(k) = k mod m + 1, maka keempat nomor mahasiswa di atas masing masing akan disimpan dalam alamat 66, 96, 69, dan 81.
2. Metode Midsquare Dalam metoda ini, kunci yang diketahui dikuadratkan, dan fungsi hash yang dipilih adalah: H(k) = I Nilai I diperoleh dengan menghapus digit-digit pada, kedua sisi dari k, dengan catatan bahwa banyaknya digit di sebelah kiri dan sebelah kanan harus sama. Jika tidak sama, maka pada digit kiri seolah-olah ditambahkan sejumlah trailing zero, hingga akan menghasilkan alamat yang benar. Dari contoh diatas, maka alamat dari masing-masing nomor mahasiswa di atas adalah: k k2 H(k)
10347 107060409 06
87492
34212
88688
76548500564 1170460944
7865561344
85
46
56
14
Searching
3. Penjumlahan Digit Dalam penjumlahan digit, kunci yang diketahui bisa dipecah menjadi beberapa kelompok yang masing-masing terdiri dari beberapa buah digit, misalnya dua buah. Kemudian digit-digit dari kelompok kelompok yang ada dijumlahkan. Pemecahan dan penjumlahan terus dilakukan jika jumlah keseluruhan kelompok yang ada. masih lebih besar dari banyaknya alamat yang akan dipakai. Dengan menggunakan nomor mahasis di atas, maka alamat dari masing-masing nomor mahasiswa bisa ditentukan sebagai berikut (dalam hal ini digunakan kelompok dengan dua buah digit, karena alamatnya diketahui dari 0 sampai 99): H(10347) = 1 + 03 + 47 = 51 H(87492) = 8 + 74 + 92 = 174 = I + 74 = 75 H(34212) = 3 + 42 + 12 = 57 H(88688) = 8 + 86 + 88 = 182 = 1 + 82 = 83
5.2 Cara Mengatasi Tabrakan Seperti yang telah dijelaskan sebelumnya bahwa tujuan pemilihan fungsi hash adalah untuk menempatkan rekaman pada alamat tertentu, sehingga bisa dihindari adanya tabrakan, yaitu suatu keadaan dimana dua buah atau lebih rekaman yang mempunyai data kunci yang berbeda mempunyai alamat hash yang sama. Meskipun demikian, kemungkinan adanya tabrakan selalu tetap saja terjadi, meskipun kita sudah menentukan fungsi hash yang cukup baik. Misalkan
dengan
menggunakan
metode
penjumlahan
kita
akan
menentukan alamat hash dari nomor mahasiswa berikut H(10347) = 1 + 03 + 47 = 51 H(87492) = 8 + 74 + 92 = 174 = I + 74 = 75 H(34212) = 3 + 42 + 12 = 57 H(88688) = 8 + 86 + 88 = 182 = 1 + 82 = 83 H(20247) = 2 + 02 + 47 = 51 Dapat dilihat bahwa nomor mahasiswa 10347 dan 20247 memiliki alamat hash yang sama, maka dalam pencarian natinya ini akan mengakibatkan terjadinya tabrakan. Oleh karena itu, kita harus mempunyai satu cara untuk mengatasi tabrakan yang mungkin terjadi, yang disebut dengan collision resolution.
15
Searching
Prosedur yang baik untuk mengatasi adanya tabrakan antara lain terhadap perbandingan banyaknya data kunci (n) dalam K, dan banyaknya alamat hash (m) dalam L. Perbandingan ini, λ= n/m, disebut faktor beban. Efisiensi fungsi hash yang dilengkapi dengan prosedur untuk mengatasi tabrakan diukur dengan banyaknya pembandingan kunci (probe) yang diperlukan untuk mencari alamat dari rekaman yang mempunyai kunci k. Efisiensi ini gayut terhadap faktor beban, dan diukur menggunakan dua besaran berikut ini: B(λ) = rata-rata probe untuk pencarian yang berhasil. G(λ)= rata-rata probe untuk penearian yang gagal. B (λ ) =
1⎛ 1 ⎞ ⎜⎜1 + ⎟ 2 ⎝ (1 − λ ) ⎟⎠
G (λ ) =
1⎛ 1 ⎜1 + ⎜ 2 ⎝ (1 − λ )2
⎞ ⎟ ⎟ ⎠
Berikut ini akan disajikan beberapa cara untuk mengatasi kemungkinan adanya tabrakan. 1. Pengalamatan Terbuka Secara umum, cara ini bisa dijelaskan sebagai berikut. Dimisalkan sebuah rekaman dengan kunci k akan disisipkan ke dalam tabel alamat hash. Berdasarkan fungsi hash yang dipakai, alamat utnuk kunci k tersebut dihitung, misalnya pada alamat h. Jika kemudian ternyata. bahwa alamat h sudah terisi, maka harus dicari alamat lain yang masih kosong. Cara yang termudah adalah dengan mencari alamat berikutnya yang kosong. Cara ini disebut dengan linear probing. Untuk lebih memperjelas apa yang dimaksud dengan linear probing, berikut disajikan sebuah contoh : Rekaman
A B
C K
P Q R Y
Z
H(k)
5
7
0
0
6
5
1
2
9
Dimisalkan bahwa kesembilan rekaman di atas dimasukkan dengan urutan yang sama dengan urutan di atas. Maka rekaman-rekaman di atas akan tersimpan dalam pengingat sebagai: Rekaman
P
Q
R
Z
-
A
B
C
K
Y
Alamat
0
1
2
3
4
5
6
7
8
9
16
Searching
Dari contoh di atas kita bisa melihat bahwa rekaman A, B, C, P, Q, R, dan Y menempati alamat yang tepat. Rekaman K, meskipun alamat hash sebenarnya adalah 5, tetapi karena alamat 5 sudah dipakai oleh A, maka diletakkan pada alamat berikutnya yang kosong. Demikian pula dengan rekaman Z, yang seharusnya menempati alamat 0, tetapi karena alamat 0 sudah dipakai oleh P, maka Z ditempatkan pada alamat 3. Dari contoh di atas bisa dihitung banyaknya probe rata-rata untuk pencarian yang berhasil dan gagal. Sehungga Probe rata-rata untuk pencarian yang berhasil dapat dihitung dengan cara sebagai berikut : Karena A, B, C, P, Q, R, dan Y, sudah menempati alamat yang seharusnya, maka untuk mencari informasi-informasi ini dan berhasil cukup dilaksanakan dengan sebuah probe. Untuk mencari informasi yang lain, banyaknya probe yang diperlukan untuk pencarian yang berhasil adalah dengan menghitung banyaknya alamat dari alamat yang seharusnya informasi tersebut berada sampai alamat dimana informasi tersebut dicatat. Sebagai contoh, karena K sesungguhnya harus berada pada alamat 5, sedangkan kenyatannya K berada pada alamat 8, maka pencarian K yang berhasil memerlukan 4 probe. Dengan cara yang sama, maka pencarian yang berhasil untuk Z memerlukan 4 probe. Dengan demikian, banyaknya probe rata-rata yang diperlukan untuk pencarian yang berhasil (diurutkan dari A sampai Z) adalah: B=
1 + 1 + 1 + 4 + 1 + 1 + 1 + 1 + 4 15 = = 1.667 9 9
Dan probe rata-rata untuk pencarian yang tidak berhasil bisa didapat dihitung dengan cara berikut : Jumlahkan probe yang diperlukan untuk mencari alamat kosong yang terdekat oleh setiap alamat yang ada. Maksudnya jika pencarian sudah sampai pada suatu alamat yang kosong, maka data yang dicari pasti tidak akan ditemukan. Sebagai contoh, pencarian yang tidak berhasil untuk mencari P memerlukan 5 buah probe dihitung dari posisi P sampai tanda -, untuk Q memerlukan 4 buah probe, dan seterusnya. Sedangkan, probe ratarata yang diperlukan untuk pencarian yang tidak berhasil adalah:
17
Searching
G=
5 + 4 + 3 + 2 + 1 + 10 + 9 + 8 + 7 + 6 55 = = 5 .5 10 10
Dari contoh diatas dapat dilihat kelemahan dari linear probing yaitu data cenderung untuk mengumpul pada satu tempat. Maksudnya jika ada suatu data yang akan disisipkan pada suatu alamat, dan alamat yang dimaksud sudah dipakai, maka data baru tersebut akan ditempatkan pada lokasi berikutnya yang letaknya berurutan. Ada dua cara yang bisa dipakai untuk memperbaiki cara di atas. Kedua cara ini disebut dengan quadratic probing dan double hasing. a. Quadratic Probing Dalam quadratic probing, jika alamat untuk suatu data baru yang akan disisipkan sudah dipakai (misalnya alamat h), maka data baru tersebut tidak ditempatkan pada posisi h+1, atau h+2 (karena alamat h+1 juga sudah dipakai), dan seterusnya; tetapi, data baru akan diletakkan pada alamat dengan urutan: h, h + 1, h + 4, h + 9, ... Dengan demikian, pencarian akan dilaksanakan pada urutan alamat di atas. Jika banyaknya alamat yang tersedia adalah merupakan bilangan prima, cara di atas akan melakukan pencarian pada separuh, dari seluruh alamat yang ada.
b. Double hasing Dalam double hashing digunakan dua buah fungsi hash untuk menghindari adanya tabrakan. Secara sederhana cara ini bisa dijelaskan sebagai berikut. Dari kunci k ditentukan alamat hashnya yang pertama, misal H(k) = h. Kemudian ditentukan alamat hash yang kedua, misal H(k) = h’≠m (m adalah banyaknya alamat hash yang dihasilkan dari fungsi hash yang pertama). Dengan demikian, pencarian dilakukan secara urut pada alamatalamat: h, h + h', h + 2h', h + 3h', ...
Suatu kerugian yang mendasar dari metode pengalamatan terbuka yaitu jika dimisalkan kita akan menyisipkan sebuah rekaman baru, misainya rek2, yang akan menempati alamat x pada tabel hash. Tetapi karena alamat x sudah terisi,
18
Searching
maka rekaman rek2 ini akan ditempatkan pada lokasi kosong yang pertama sesudah alamat x, misalnya x1. Sekarang misalnya rekaman yang ada pada alamat x dihapus. Dengan demikian, maka alamat x sekarang menjadi kosong. Jika kemudian kita akan mencari rekaman rek2 kita akan mendapatkan kenyataan bahwa program mungkin tidak akan menemukan rekaman tersebut meskipun sesungguhnya ada. Sebabnya adalah, bahwa pada saat rekaman rek2 akan dicari, maka berdasar fungsi hash yang dipakai, rekaman tersebut akan menempati alamat x. Tetapi karena sekarang alamat x sudah kosong, maka program tidak akan meneruskan pencariannya-ke alamat-alamat yang lain. Salah satu cara untuk mengatasi persoalan di atas adalah dengan memberi tanda khusus pada alamat-alamat yang isi sesungguhnya sudah dihapus. Dengan demikian program akan meneruskan pencarian jika program membaca alamat vang diberi tanda "dihapus". Tetapi persoalan lain bisa timbul, yaitu jika hampir semua alamat diisi dengan tanda "dihapus". Dengan cara ini, maka pencarian bisa menjadi pencarian berurutan.
2. Penggandengan Metoda lain untuk mengatasi kemungkinan adanya tabrakan alamat hash adalah
dengan Penggandengan (chaining). Pada prinsipnya metode ini
memanfaatkan senarai berantai (yang juga bisa diimplementasikan menggunakan larik) yang dipasang pada setiap alamat hash yang diketahui. Dengan demikian, jika kita melihat pada sebuah alamat hash lengkap dengan senarai yang menyimpan rekaman-rekaman yang mempunyai alamat hash yang sama, maka kita akan melihat adanya sebuah senarai berantai tunggal berkepala, dengan kepalanya adalah alamat hash. (Perhatikan Gambar. 3) Sebagai contoh, jika kita mempunyai rekaman-rekaman yang kunci rekamannya bisa dituliskan sebagai : 34
56
123
78
93
70
100
21
11
77
28
dan fungsi hash yang dipilih adalah k mod 10 sehingga : 34 mod 10 = 4 56 mod 10 = 6 Dst.
19
Searching
Dengan demikian, alamat hash akan terdiri dari sepuluh buah alamat yang bernomor 0 sampai dengan 9 Perhatikan Gambar. 3 yang menunjukkan alamat hash lengkap dengan senarai berantainya untuk menyimpan rekaman-rekaman tersebut.
Alamat Hash 0
70
100
1
21
11
3
123
93
4
34
2
5 6
56
7
77
8
78
28
9
Gambar 3. Penggandengan alamat hash pada senarai
Dengan melihat gambar tersebut, kita bisa menyusun struktur data untuk menyajikan metoda penggandengan dengan menggunakan senarai berantai, misalnya: type Sambungan = ^Rekaman; Rekaman = record Kunci : integer; Info : char; Berikut : Sambungan end; Hash = array [0..9] of Sambungan;
20
