HASH FILE

Hashing
Metode penempatan dan pencarian yang memanfaatkan metode Hash
disebut hashing atau ‘Hash addressing’ dan fungsi yang digunakan disebut fungsi
hashing / fungsi Hash. Fungsi hashing atau fungsi Hash inilah yang dapat menjadi
salah satu alternatif dalam menyimpan atau mengorganisasi File dengan metode
akses langsung. Fungsi Hash berupaya menciptakan “fingerprint” dari berbagai
data masukan. Fungsi Hash akan mengganti atau mentransposekan data tersebut
untuk menciptakan fingerprint, yang biasa disebut Hashvalue (nilai Hash). Hash
value biasanya akan digambarkan sebagai suatu string pendek yang terdiri atas
huruf dan angka yang terlihat random (data biner yang ditulis dalam notasi
heksadesimal).
Berkaitan dengan upayanya untuk menciptakan “fingerprint”, fungsi Hash
digunakan juga pada algoritma enkripsi untuk menjaga integritas sebuah data.
Dalam konsepnya modern ini –selain digunakan pada penyimpanan data-, fungsi
Hash adalah sebuah fungsi matematika, yang menerima masukan string yang
panjangnya sebarang, mengambil sebuah panjang variable dari string masukan
tersebut –yang disebut pre-image, lalu mekonversinkannya ke sebuah string
keluaran dengan ukuran tetap (fixed), dan umumnya lebih pendek dari ukuran
string semula, yang disebut message digest.
Pada penggunaan fungsi Hash, saat keadaan tertentu dapat terjadi
tabrakan (coallision) pada home address yang dihasilkan. Yaitu saat munculnya
nilai Hash yang sama dari beberapa data yang berbeda. Untuk mengantisipasi
keadaan ini ada beberapa metode yang dapat digunakan, seperti perubahan fungsi
Hash atau mengurangi perbandingan antara jumlah data yang tersimpan dengan
slot address yang tersedia. Hal-hal tersebut dapat meminimalisir tabrakan, tetapi
tidak menghilangkannya. Kita tetap memerlukan collision resolution -sebuah
prosedur untuk menempatkan data yang memiliki address yang sama.


1. Konsep-Konsep File Hash
1. Organisasi file dengan metode akses langsung (direct acsess ), yang ),
menggunakan suatu fungsi untuk memetakan key menjadi address
2. fungsi yang digunakan disebut fungsi hash/KAT (key to address
transformation)
3. Address yang dihasilkan dari hasil perhitungan fungsi hash disebut
dengan istilah home address
4. Jadi, terdapat dua komponen file hash :
1. Ruang rekord, yang terdiri atas m slot address
2. Fungsi hash, yang mentransformasi key menjadi address
5. Transfomasi key akan mudah jika key telah berupa nilai integer, untuk
key berupa karakter alphanumerik terdapat proses prakondisi untuk
mengubahnya menjadi suatu nilai integer.

2. Macam- Macam Fungsi Hash
Fungsi Hash diimplementasi untuk mengkonversi himpunan kunci
rekaman (K) menjadi himpunan alamat memori (L). Bisa dinotasikan
dengan H : K -> L
Aspek yang perlu dipertimbangkan dalam pemilihan fungsi Hash adalah :

• fungsi Hash harus mudah dan cepat dihitung
• fungsi Hash sebisa mungkin mendistribusikan

posisi yang dimaksud secara uniform sepanjang himpunan L sehingga
collision yang mungkin terjadi dapat diminimalkan.

Ada beberapa fungsi hash yang dapat digunakan, , seperti :
hash
fungsi
0
...
310
311
312
315
316
317
m 1
key address

a. ) Key Mod N, dengan N =jumlah slot address (ukuran tabel data) Contoh : 25 mod 11 = 3 : 25 mod 11 = 3
jika key bernilai negatif, maka bagi |key| |dengan untuk dapatkan sisa r : r
: untuk r = 0, maka k mod N = 0 k mod N = 0
untuk r <> 0, maka k mod N = N-r
b. ) Key Mod P, dengan P = bilangan prima terkecil yang >= N
c. ) Truncation/ /substringing, cara transformasi yang dilakukan dengan mengambil hanya sebagian digit dari key misal jika key = 123 --45 –6789 akan dipetakan pada address yang terdiri atas 1000 slot, maka dapat dilakukan pengambilan tiga digit (secara acak atau terurut) dari key tersebut untuk menentukan addressnya.
d.) Folding, dapat dilakukan dengan cara :
1. Folding by boundary
Contoh jika key = 123456789, maka transformasi ke 3 digit address dengan teknik folding by boundary dapat dilakukan dengan membagi digit key tersebut dengan cara seolah --olah melipat batas pembagian digit seperti berikut :
123 456 789
:
Tiap keompok digit kemudian dijumlahkan dengan atau tanpa melibatkan carry

2. Folding by shifting
Contoh jika key = 123456789, maka transformasi ke 33digit address dengan teknik folding by boundary dapat dilakukan dengan membagi digit key tersebut dengan cara seolah --olah menggeser batas pembagian digit seperti berikut:
3 2 1
4 5 6
 9 8 7
1 2 3
4 5 6
7 8 9
1 2 3
4 5 6
 7 8 9

Tiap keompok digit kemudian dijumlahkan dengan atau tanpa melibatkan carry.
e. ) Radix Convertion
Kunci ditransformasikan menjadi bilangan basis lain untuk mendapatkan nilai hashnya. Umumnya basis yang digunakan di luar dari basis 2-10. Misalnya jika kunci 38652 akan ditempatkan dalam table berukuran 10000 dengan basis 11, maka:
3x114+8x113+6x112+5x111+2x110= 5535411
Nilai Hash 55354 telah melampaui batas Hash, makan pecehan terbesar dari harsh tersebut akan dibuang sehingga diapatkan harsh 5354.
f.) Mid-square
Kunci ditransformasikan dengan cara dikuadratkan dan diambil bagian tengahnya (asalkan jumlah digit kiri dan kanan sama) )sebagai nilai Hash. Misalnya jika kunci = 3121 akan ditempatkan pada table berukuran 1000, maka 31212 = 9740641, diambil 406 sebagai nilai hashnya.
g.) Penambahan Kode ASCII
Jika kunci bukan kode numeric, home address didapatkan dari penjumlahan kode ASCII setiap huruf pembentuk kunci.

3. Tabrakan
Dengan menggunakan hashing, maka hubungan korespondensi satu-satu antara record key dengan alamat record akan hilang. Selalu timbul kemungkinan dimana terdapat dua buah record dengan kunci yang berbeda namun memiliki home address yang sama, dan terjadi tabrakan (collision). Tabrakan dapat diminimalisir dengan melakukan penggantian pada fungsi Hash yang digunakan, atau mengurangi packing factor.
a.) Packing Factor
Packing factor, bisa disebut juga dengan packing density ataupun load
factor adalah perbandingan antara jumlah data yang tersimpan terhadap jumlah slot address yang tersedia. Location Storage of Number Total Stored cord of Number Factor. Penggantian fungsi Hash dan pengurangan packing factor hanya meminimasisasi tabrakan, tetap dibutuhkan collision resolution.
b.) Collision Resolution
Pada hashing untuk penempatan data, output dari fungsi Hash tidak
selalu unik, namun hanya berupa kemungkinan suaru alamat yang dapat ditempati. Jika suatu home address sudah ditempati oleh record lain, maka harus dicarikan alamat lain. Proses pencarian Packing Re = alamat lain inilah yang disebut sebagai prosedur collision resolution.
1. Metode Collision Resolution
a. Open addressing
Metode dengan pencarian alamat alternative di alamat-alamat selanjutnya yang masih kosong.
Cara :
• Linear probing
Pencarian dilakukan dengan jarak pencarian tetap
• Quardratic probing
Pencarian dilakukan dengan jarak pencarian berubah dengan perubahan tetap.


• Double hashing
Pencarian dilakukan menggunakan dua fungsi Hash, yaitu :
fungsi H1 untuk menentukan home address dan fungsi H2 untuk menentukan increment jika terjadi tabrakan. Syarat metode ini adalah ukuran table merupakan bilangan prima sehingga kemungkinan terjadinya siklus pencarian pada slot yang sama dapat dihindari.
Algoritma : Tentukan home address dari key dengan fungsi H1.
IF home address kosong THEN Sisip record pada home address.
ELSE Hitung increment dengan fungsi H2 misalnya H2 (key) = x Temukan slot kosong dengan cara increment sejauh x dari home address.
IF slot kosong ditemukan THEN Sisip record pada slot kosong.
ELSE Tabel telah penuh.

b. Computed chaining
Menggunakan “pseudolink” untuk menemukan next address
jika terjadi collision. Tidak menyimpan actual address pada pseudolink, tapi address ditemukan dengan menghitung apa yang tersimpan pada pseudolink. Kinerja pseudolink lebih baik dibandingkan non-link karena menghilangkan penebakan lokasi (address).
Algoritma : Temukan home address dari key.
IF home address kosong THEN Sisip record baru ke home address. ELSE
Set 3 prioritas increment untuk mencari new address :
1 : Tentukan increment (new key).
2 : Tentukan increment (key pada current address).
3 : Penjumlahan hasil prioritas 1 dan 2.
WHILE new address belum kosong dan tabel belum penuh DO
Cek posisi mulai dari home address untuk ke – 3 prioritas untuk mencari new address yang kosong.
IF new address belum kosong THEN Set ke – 3 nilai prioritas dengan kelipatannya.
END WHILE
IF tabel penuh THEN Proses sisip tidak dilakukan, keluarkan pesan
“Tabel Penuh”.
ELSE Sisip record baru pada new address.
Set field pseudolink pada home address dengan kode urut prioritas yang digunakan.

c. Coalesced hashing
Algoritma : Tentukan home address dari key.
IF home address kosong THEN Sisip record pada home address.
ELSE Temukan record terakhir dari data yang telah menempati home address, dengan mengikuti link. Temukan slot kosong mulai dari yang terletak pada address paling bawah.
IF slot kosong tidak ditemukan THEN File telah penuh.
ELSE Sisip record pada slot kosong.
Set link field dari record terakhir yang ber-home address sama ke alamat dari record yang baru disisip.
d. Chained progressive overflow
Algoritma : Tentukan home address dari key.
IF home address kosong THEN Sisip record pada home address.
ELSE Temukan slot kosong yang terletak setelah home address.
IF slot kosong ditemukan THEN Sisip record pada slot kosong.
ELSE Tabel telah penuh.
e. Binary tree
Metode yang menggunakan struktur binary tree untuk pencarian address ketika erjadi tabrakan dengan memberikan dua pilihan langkah :
•Continue : melanjutkan pencarian address berikutnya yang mungkin ditempati oleh record yang akan disisipkan.
•Move : memindahkan record yang menempati address ke address berikutnya yang memungkinkan untuk ditempati record lama.
Algoritma : Tentukan home address dari key yang akan di-sisipkan (new key).
IF home address kosong THEN Sisip record pada home address.
ELSE WHILE new address tidak kosong dan tabel belum penuh DO Generate binary tree untuk mendapatkan new address :


4. Fungsi Hash Satu Arah
Fungsi Hash satu arah adalah fungsi Hash yang bekerja dalam satu arah.
Maksud dari satu arah disini adalah bahwa pesan yang sudah diubah menjadi message digest tidak dapat dikembalikan lagi menjadi pesan semula (irreversible).
>> Sifat-sifat fungsi Hash satu-arah adalah sebagai berikut:
1. Fungsi H dapat diterapkan pada blok data berukuran berapa saja.
2. H menghasilkan nilai (h) dengan panjang tetap (fixed-length output).
3. H(x) mudah dihitung untuk setiap nilai x yang diberikan.
4. Untuk setiap h yang dihasilkan, tidak mungkin dikembalikan nilai x sedemikian sehingga H(x) =h. Itulah sebabnya fungsi H dikatakan fungsi Hash satu-arah (one-way Hash function).
5. Untuk setiap x yang diberikan, tidak mungkin mencari y ≠ x sedemikian
sehingga H(y) = H(x).
6. Tidak mungkin mencari pasangan x dan y sedemikian sehingga H(x) = H(y).

>> Beberapa fungsi Hash satu-arah yang sudah dibuat, antara lain:
- MD2, MD4, MD5,
- Secure Hash Function (SHA),
- Snefru,
- N-Hash,
- RIPE-MD.