Implementasi Direktori Hash

Pada implementasi ini, linier list tetap digunakan untuk menyimpan direktori, hanya saja ada tambahan berupa struktur data hash. Prosesnya yaitu hash table mengambil nilai yang dihitung dari nama berkas dan mengembalikan sebuah pointer ke nama berkas yang ada di linier list. Oleh karena itu, waktu pencarian berkas bisa dikurangi. Akan tetapi, ada suatu keadaan yang menyebabkan terjadinya peristiwa collisions, yaitu suatu kondisi di mana terdapat dua berkas yang memiliki nilai hash yang sama, sehingga menempati lokasi yang sama. Solusi yang dipakai untuk mengatasi hal tersebut yaitu dengan menggunakan chained-overflow hash table, yaitu setiap hash table mempunyai linked list dari nilai individual dan crash dapat diatasi dengan menambah tempat pada linked list tersebut. Efek samping dari penambahan chained-overflow tersebut adalah dapat memperlambat pencarian.

Ada beberapa kelemahan dari implementasi direktori hash, yaitu ukurannya yang tetap dan adanya ketergantungan fungsi hash dengan ukuran hash table. Sebagai contoh, misalnya kita membuat sebuah linear-probing hash table yang memiliki 32 entry. Sebuah fungsi hash dibutuhkan untuk mengubah nama berkas menjadi bilangan bulat dari 0 s.d. 31, misalnya dengan menggunakan fungsi modulo 32. Jika kita ingin untuk menambahkan sebuah berkas yang harus diletakkan pada lokasi yang ke-33, kita harus memperbesar ukuran dari hash table tersebut, sehingga diperlukan sebuah fungsi hash baru untuk disesuaikan dengan ukuran hash table tersebut. Oleh karena itu, berkas-berkas yang sebelumnya sudah ditempatkan di suatu lokasi pada hash table yang lama harus dicari tempat yang bersesuaian dengan menggunakan fungsi hash yang baru.