double_dhe™

R(NILAI KEY) ADDRESS.

Adalah dengan melakukan kalkulasi terhadap nilai key, hasilnya adalah alamat relatif.

Ide dasar dari kalkulasi alamat adalah mengubah jangkauan nilai key yang mungkin, menjadi sejumlah kecil alamat relative.

Salah satu kelemahan dari teknik pengalamatan relative adalah ruang harus disediakan sebanyak jangkauan nilai key, terlepas dari berapa banyak nilai key.

Salah satu masalah dari teknik ini adalah ditemukannya alamat relative yang sama untuk nilai key yang berbeda.

Keadaan dimana :

R(K1) = R(K2) Disebut benturan atau

K1 ı K2 collision

Sedangkan nilai K1 dan K2 disebut synonym.

Synonim adalah dua atau lebih nilai key yang berbeda pada hash ke home address yang sama.

Teknik-teknik yang terdapat pada kalkulasi alamat :

• Scatter storage techniques
• Randomizing technique
• Key-to-address transformation methods
• Direct addressing techniques
• Hash table methods
• Hashing

Disini yang akan kita bahas menhenai taknik hashing. Kalkulasi terhadap nilai key untuk mendapatkan sebuah alamat disebut fungsi hash.

Keuntungan pemakaian Hashing :

• Nilai key yang sebenarnya dapat dipakai karena diterjemahkan ke dalam sebuah alamat.
• Nilai key adalah address space independent bila berkas direorganisasi, fungsi hash berubah tetapi nilai key tetap.

Kelemahannya :

• Distribusi nilai key yang dipakai
• Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
• Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebakan benturan
• Teknik yang dipakai untuk mengatasi benturan

Hashing dapat digunakan bersama-sama dengan pencarian table, lihat gambar pada halaman 16.

Penampilan fungsi hash bergantung pada :

• Distribusi nilai key yang dipakai
• Banyaknya nilai key yang dipakai relative terhadap ukuran dari ruang alamat
• Banyaknya record yang dapat disimpan pada alamat tertentu tanpa menyebabkan benturan
• Teknik yang dipakai untuk mengatasi benturan

Beberapa fungsi hash yang umum digunakan :

• Division Remainder
• Mid Square
• Folding