Page 221 - KEGIATAN BELAJAR 1-15 LENGKAP (2)_Neat

KEGIATAN BELAJAR 13

paling sering digunakan. Penggunaan ’cache’ menghindari pembacaan

informasi berulang-ulang pada disk. Daftar yang telah diurutkan
memperbolehkan pencarian biner dan mengurangi waktu rata-rata pencarian.

Bagaimana pun juga penjagaan agar daftar tetap terurut dapat

merumitkan operasi pembuatan dan penghapusan berkas, karena kita perlu

memindahkan sejumlah direktori untuk mengurutkannya. Tree yang lebih

lengkap dapat membantu seperti B-tree. Keuntungan dari daftar yang terurut
adalah kita dapatkan daftar direktori yang terurut tanpa pengurutan yang

terpisah.

13.2.2 Hash Table
Struktur data lainnya yang juga digunakan untuk direktori berkas adalah

hash table. Dalam metode ini linear list menyimpan direktori, tetapi struktur

data hash juga

digunakan. Hash table mengambil nilai yang dihitung dari nama berkas dan

mengembalikan sebuah penunjuk ke nama berkas yang ada di-linear list. Maka
dari itu dapat memotong banyak biaya pencarian direktori. Memasukkan dan

menghapus berkas juga lebih mudah dan cepat. Meski demikian beberapa

aturan harus dibuat untuk mencegah tabrakan, situasi dimana dua nama berkas

pada hash mempunyai tempat yang sama. Kesulitan utama dalam hash table

adalah ukuran tetap dari hash table dan ketergantungan dari fungsi hash
dengan ukuran hash table. Sebagai contoh, misalkan kita membuat suatu linear-

probing hash table yang dapat menampung 64 data. Fungsi hash mengubah

nama berkas menjadi nilai dari 0 sampai 63. Jika kita membuat berkas ke 65 maka

ukuran tabel hash harus diperbesar sampai misalnya 128 dan kita

membutuhkan suatu fungsi hash yang baru yang dapat memetakan nama
berkas dari jangkauan 0 sampai 127, dan kita harus mengatur data direktori yang

sudah ada agar memenuhi fungsi hash yang baru. Sebagai alternatif dapat

digunakan chained-overflow hash table, setiap hash table mempunyai daftar

yang terkait (linked list) dari pada nilai individual dan kita dapat mengatasi

tabrakan dengan menambah tempat pada daftar terkait tersebut. Pencarian

SISTEM OPERASI 209