Teknit Pengalamatan : Pengalamatan Relatif

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.

Universitas Gunadarma