COLLISION

Collision merupakan kondisi di mana terdapat lebih dari satu key yang menempati slot address yang sama. Collision dapat diminimalisir dengan cara::

1. Mengganti fungsi hash
2. Mengurangi packing factor

Packing Factor / packing density / lload factor adalah perbandingan antara jjumlah data yang tersimpan tterhadapjjumlah slot address yang ttersedia.

COLLISION RESOLUTION

Mengganti fungsi hash atau mengurangi packingffactor hanyalah suatu tteknik untuk mengurangi terjadinya collision, tetapi tidak mengeliminasinya. Karenanya, diperlukan Collision Resolution, yaitu prosedur untuk menempatkan data yang memiliki home address yang sama, sedemikian hingga banyaknya akses dari home address seminimum mungkin.

Terdapat beberapa metode collision resolution :

1. With links : Coalesced Hashing
2. Without links :

a) Static positioning of records : Progressive Overflow, Linear Qoutient

b) Dynamic positioning of records:: Binary Tree, Brent’s method

With pseudolinks : Computed Chainnig

KONSEP FILE HASH

Merupakan organisasi file dengan metode akses langsung((direct acsess), yang menggunakan suatu fungsi untuk memetakan key menjadi address. Fungsi yang digunakan disebut fungsi hash/KAT (key to address transformation). Address yang dihasilkan dari hasil perhitungan fungsi hash disebut dengan istilah home address. Jadi, terdapat dua komponen dalam file hash :

1. Ruang rekord,, yang terdiri atas m slot address
2. Fungsi hash,, yang mentransformasi key menjadi address

Transfomasi key akan mudah jika key telah berupa nilai integer, untuk key untuk key berupa karakter alphanumerik terdapat proses prakondisi untuk mengubahnya menjadi suatu nilai integer.

FUNGSI HASH

Ada beberapa fungsi hash yang dapat digunakan, seperti ::

1. Key Mod N,, dengan N = jjumlah slot address ((ukuran tabel data)

Contoh : 25 mod 11 = 3

jika key bernilai negatif, maka bagi |key| dengan N untuk mendapatkan sisa r :

untuk r = 0, maka k mod N = 0

untuk r <> 0, maka k mod N = N-r

2. Key Mod P,, dengan P = bilangan primatterkecil yang >= N
3. Truncation/substringing, carattransformasi yang dilakukan dengan mengambil hanya sebagian digit dari key. Misal jjika key = 123--45--6789 akan dipetakan pada address yangtterdiri atas 1000 slot, maka dapat dilakukan pengambilan tiga digit (secara acak atau tterurut) dari key ttersebut untuk menentukan addressnya.

ORGANISASI BERKAS

Organisasi Berkas adalah suatu teknik / cara yang digunakan untuk menyatakan / menggambarkan dan menyimpan record-record dalam sebuah file.
Ada 4 teknik dasar organisasi file, yaitu :
1. Sequential File
2. Relatif File
3. Index Sequential File
4. Multi-Key file
Secara umum keempat teknik dasar tersebut berbeda dalam cara pengaksesannya, yaitu :
• Direct Access
Suatu cara pengaksesan record yang langsung tanpa mengakses seluruh record yang ada.
Contoh
o Magnetic disc
o CD
o Dll
• Sequential Access
Suatu cara pengaksesan record, yang didahului pengaksesan record-record didepannya
o Magnetic tape
o Punch card
o Dll
Faktor-faktor yang mempengaruhi dalam proses pemilihan organisasi file:
1. Karakteristik dari media penyimpanan yang digunakan
2. Volume dan frekuensi dari transaksi yang diproses
3. Respontime yang diperlukan

HASH FILE

Apakah Fungsi Hash Itu?

Fungsi hash H adalah transformasi yang
mengambil input dengan ukuran m dan
mengembalikan sebuah string berukuran
tetap yang disebut sebagai nilai hash h (di
mana, h = H(m)). Fungsi hash sederhana ini
memiliki berbagai jenis kegunaan
komputasi, tetapi ketika digunakan untuk
masalah kriptografi, fungsi hash selalu
ditambahkan dengan sejumlah properti
tambahan.

Yang dibutuhkan untuk fungsi kriptografi
hash, yaitu:
1. input dengan panjang sembarang
2. hasilnya mempunyai keluaran
dengan panjang yang fixed
3. H(x) umumnya mudah dikalkulasi
untuk sembarang nilai x
4. H(x) adalah satu-arah
5. H(x) tidak pernah bermasalah
dengan yang lain

Fungsi hash H merupakan fungsi satu-arah
sebab sulit untuk dibalikkan yang berarti
untuk nilai fungsi hash h, kita sulit
menemukan nilai input x yang memenuhi
persamaan H(x) = h

Selain itu, jika diberikan sebuah pesan x
untuk dikomputasi dalam fungsi hash H, kita
akan kesulitan dalam mencari pesan y yang
akan menyamai nilai dari H(x) (berarti sulit
menemukan nilai H(x) = H(y)) yang dapat
kita katakan bahwa fungsi hash x tidak
mungkin bertabrakan dengan fungsi hash y.
Hal ini menyebabkan fungsi hash H adalah
sebuah fungsi yang sulit untuk menemukan
kesamaan antara 2 pesan (strongly collisionfree).
Nilai dari fungsi hash menyatakan sebuah
pesan atau dokumen yang lebih panjang
yang berasal dari proses komputasi. Hal ini
menarik sebab dengan fungsi hash, kita
dapat membuat sebuah digital fingerprint
untuk sebuah dokumen. Contoh yang paling
terkenal dari fungsi hash adalah MD2, MD5
dan SHA.

Mungkin penggunaan yang umum dari
fungsi kriptografi hash adalah pembuatan
digital signatures. Karena fungsi hash
umumnya lebih cepat daripada algoritma
digital signature lainnya, fungsi hash lebih
sering digunakan untuk mendapatkan nilai
fungsi hash dengan mengkalkulasikan
signature yang menghasilkan sebuah nilai
hash yang lebih kecil daripada dokumen itu
sendiri. Selain itu, publik dapat memberikan
sebuah saran atau pendapat tanpa
membeberkan isi dari pendapat yang
terdapat di dalamnya. Cara ini digunakan
dalam memberikan tanggal pada sebuah
dokumen dimana dengan menggunakan
fungsi hash, setiap orang dapat memberikan
tanggal pada dokumen tanpa
memperlihatkan isi dari dokumennya pada
saat proses pemberian tanggal.
Karena fungsi hash erat berkaitan dengan
kriptografi, bagian selanjutnya akan
membahas sedikit tentang kriptografi.