Teknik
ini menjadikan atribut kunci sebagai alamat memorinya, jadi, data dari
NPM dijadikan bertipe numeric(integer) dan dijadikan alamat dari record
yang bersangkutan. Cara ini memang sangat efektif untuk menemukan
kembali record yang sudah disimpan, tetapi sangat boros penggunaan
memorinya. Tentu alamat memori mulai dari 1 hingga alamat ke sekian juta
tidak digunakan karena nilai dari NPM tidak ada yang kecil. Pelajari
keuntungan dan kerugian lainnya.Teknik ini termasuk dalam katagori
address space dependent.
TEKNIK PENCARIAN TABEL
Teknik
ini dilakukan dengan cara, mengambil seluruh kunci atribut dan alamat
memori yang ada dan dimasukkan ke dalam tabel tersendiri. Jadi tabel itu
(misal disebut dengan tabel INDEX) hanya berisi kunci atribut (misalkan
NPM) yang telah disorting (diurut) dan alamat memorinya.
Jadi,
sewaktu dilakukan pencarian data, tabel yang pertama dibaca adalah
tabel INDEX itu, setelah ditemukan atribut kuncinya, maka data alamat
yang ada di sana digunakan untuk meraih alamat record dari data (berkas/
file/ tabel) yang sebenarnya. Pencarian yang dilakukan di tabel INDEX
akan lebih cepat dilakukan dengan teknik pencarian melalui binary search
(dibagi dua-dua, ada di mata kuliah Struktur dan Organisasi Data 2
kelak) ketimbang dilakukan secara sequential.
Nilai
key field (kunci atribut) bersifat address space independent (tidak
terpengaruh terhadap perubahan organisasi file-nya), yang berubah
hanyalah alamat yang ada di INDEX-nya.
TEKNIK KALKULASI ALAMAT
Kalau
pada teknik pencarian tabel kita harus menyediakan ruang memori untuk
menyimpan tabel INDEX-nya, maka pada teknik ini tidak diperlukan hal
itu. Yang dilakukan di sini adalah membuat hitungan sedemikian rupa
sehingga dengan memasukkan kunci atribut record-nya, alamatnya sudah
dapat diketahui. Tinggal masalahnya, bagaimana membuat hitungan dari
kunci atribut itu sehingga hasilnya bisa efisien (dalam penggunaan
memori) dan tidak berbenturan nilainya (menggunakan alamat yang sama).
Misal,
untuk data si ALI di atas yang memiliki NPM = ‘10105787’, di mana akan
kita letakkan ?. Bila yang kita lakukan adalah perhitungan :
INT(VAL(NPM)/1000000) maka haslinya adalah 10, dengan demikian data si
ALI akan disimpan di alamat 10. Tapi, apakah alamat 10 itu tidak akan
digunakan oleh data lain dengan perhitungan yang sama ?, ternyata tidak.
Untuk data si BADU yang NPMnya ’10105656’ juga di alamat tersebut, dan
ternyata masih banyak juga yang ’rebutan’ untuk menempati alamat
tersebut jika dilakukan dengan perhitungan seperti di atas.
Perhitungan
(kalkulasi) terhadap nilai kunci atribut untuk mendapatkan nilai suatu
alamat disebut dengan fungsi hash. Bisa juga fungsi hash digabungkan
dengan teknik pencarian seperti tabel di atas, tetapi akan menjadi lebih
lama pengerjaannya dibanding hanya dengan satu jenis saja (fungsi hash
saja atau pencarian tabel saja).
Fungsi
hash dikatakan baik bila memiliki kalkulasi yang sederhana dan memiliki
kelas ekivalen (synonim) yang kecil, atau sederhananya, memiliki
kalkulasi yang mudah tetapi memiliki benturan alamat yang sedikit.
Ada
beberapa cara untuk mengatasi benturan (collision) penggunaan alamat
seperti di atas, antara lain : scatter diagram techniques, randomizing
techniques, key to address transformation methods, direct addressing
techniques, hash tables methods, dan hashing. Di sini, kita hanya
membahas mengenai hashing.
Beberapa fungsi hash yang umum digunakan
adalah :
1. DIVISION REMAINDER
Idenya
adalah, membagi nilai key field dengan nilai tertentu, dan sisa
pembagian tersebut dijadikan alamat relatifnya. Nilai tertentu itu
terserah kita, ada yang membagi dengan bilangan prima, namun ada juga
yang tidak.Yang jelas, tujuannya adalah agar alamat yang akan digunakan
bisa berbeda sekecil mungkin (menghemat memori) dan menghindari benturan
yang bakal terjadi.
Ada
perhitungan faktor muat (load factor) yaitu, jika kita memiliki
sejumlah record yang akan ditempatkan ke dalam memori, maka setidaknya
kita harus menyediakan memori yang kapasitasnya melebihi dari jumlah
record tersebut. Misalkan, kita memiliki 4000 record, maka sebaiknya
kita memiliki memory space sebanyak 5000 alamat. Faktor muat dihitung
dengan cara membagi jumlah record dalam file dengan jumlah maksimum
record dalam file (alamat yang tersedia). Semakin besar nilai faktor
muat maka semakin baik teknik ini digunakan. Faktor muat untuk contoh di
atas adalah 4000/5000 = 0,8.
2. MID SQUARE
Teknik
ini dilakukan dengan cara melakukan kuadratisasi nilai key field dan
diambil nilai tengahnya sebanyak jumlah digit yang diinginkan. Misalkan,
nilai key-nya = 123456790, setelah dikuadratkan hasilnya =
15241578997104100 dan diambil 4 digit di tengahnya, yaitu 8997. Jadi,
alamat memori untuk data tersebut di 8997.
3. HASING BY FOLDING
Teknik
ini dilakukan dengan cara ’melipat’ nilai dari kunci atribut sebanyak
digit yang dibutuhkan (dari kanan), kemudian dijumlahkan. Nilai terbesar
dari jumlah tersebut dibuang (jika melebihi digit yang dibutuhkan).
Misalkan untuk nilai key 123456790, maka empat angka di belakang setelah
dilipat menjadi 0976, angka tersebut ditambahkan dengan empat angka
kedua (dari kanan) yaitu 2345 dan angka 1 paling kiri :
0976
2345
1
-------- +
4321
Maka, alamat dari data tersebut adalah di 4321.
Berbagai
teknik dalam penentuan penempatan data di memori (sekunder) komputer
terus berkembang. Tentu saja karena data yang direkam biasanya selalu
bersifat dinamis (bisa bertambah, berkurang, di-copy, di-sorting) dan
sebagainya. Kedinamisan tersebut tentu saja bisa berpengaruh terhadap
alamat-alamat yang sudah ditetapkan sebelumnya yang bersifat fixed size
space atau memiliki ukuran alamat yang tetap (satu misalnya, jika kita
meng-copy data tersebut yang semula di hard disk ke dalam disket, apakah
alamat-alamat yang tersedia di disket sama dengan di hard disk ?, tentu
tidak).
Teknik
hash baru yang dikembangkan antara lain dynamic hashing, extendible
hashing, dan virtual hashing. Tujuannya adalah agar alamat-alamat yang
sudah ada tidak berubah meskipun data baru ditambahkan dengan cara
membagi-bagi memori menjadi bagian-bagian tertentu yang disebut dengan
blok atau bucket, bila sebuah record akan dimasukkan ke dalam bucket
yang sudah penuh, maka bucket baru disediakan kembali.
Dynamic
hashing memakai struktur indeks binary tree untuk menyimpan track dari
bucket dan pointer untuk menuju ke record yang diinginkan. Extendible
hashing menggunakan direction untuk menyimpan track dari bucket dan
pointer untuk menuju ke record yang diinginkan. Sedangkan virtual
hashing lebih luas lagi, termasuk di dalamnya dynamic hashing dan
extendible hashing dan berbagai teknik indeks lainnya.
