Implementasi Metode Hashing Menggunakan Τeknik Open Addressing Sebagai Penanganan Kolisi Untuk Sistem Informasi Al-Qur'an

Abstract

Implementasi metode hashing dalam berbagai pengembangan software atau sistem aplikasi selalu menarik untuk dikaji. Sistem informasi Al-Qur'an dengan metode hashing sebagai sarana untuk manajemen data memiliki keunggulan dalam hal penyimpanan dan pengambilan serta penelusuran data. Karena kompleksitas asimtotik struktur data hash pada kasus terbaik adalah (1), sedangkan pada kasus terburuk adalah (n log n). Masalah yang paling utama ketika menggunakan metode hashing yaitu saat menentukan field yang akan digunakan sebagai key atau lebih dikenal dengan Key to Address Transformation (KAT), yang kemudian berimplikasi dengan pembenturan (kolisi) antar key, yang terjadi baik pada primary storage (RAM) maupun pada secondary storage (Hard Disk). Pengembangan algoritme yang baik untuk menangani kolisi merupakan jalan terbaik dalam pengimplementasian metode hashing untuk sistem aplikasi. Hal ini disebabkan karena waktu rata-rata yang dibutuhkan untuk menempatkan satu record pada tabel hash harus ditentukan melalui peluang kolisi (p). Sedangkan waktu pengambilan data diramalkan sebagai penjumlahan dari waktu yang diperlukan untuk pengacakan, waktu satu kali akses pada tabel, ditambah waktu rata-rata dari satu keadaan kolisi, sedangkan jika N adalah entri data dan M merupakan ukuran tabel, maka nilai peluang kolisi (p) dinyatakan dengan; p = N/(2M) Penelitian ini bertujuan mengimplementasikan hashing untuk sistem informasi Al-Qur'an, teknik penanganan kolisi yang dikembangkan menggunakan teknik open addressing dengan teknik lanjutan linear probing dan double hashing. Linear probing derajat tiga selalu mendefinisikan p(K) = 1 sedangkan double hashing dengan p(K) = 10 dengan p(K) fungsi penanganan kolisi. Nilai p(K) = 1 mengandung arti bahwa bila terjadi kolisi maka teknik lanjutan yang digunakan pertama-tama yaitu linear probing dengan mengurangkan (decrement) satu terhadap alamat relatif (K). Sedangkan p(K) = 10 adalah penanganan lanjutan menggunakan double hashing dengan melakukan decrement sepuluh.