Hashing adalah
transformasi aritmatik sebuah string dari karakter menjadi nilai yang
merepresentasikan string aslinya. Menurut bahasanya, hashberarti memenggal
dan kemudian menggabungkan. Hashing digunakan sebagai metode untuk
menyimpan data dalam sebuah array agar penyimpanan data, pencarian data,
penambahan data, dan penghapusan data dapat dilakukan dengan cepat. Ide
dasarnya adalah menghitung posisi recordyang dicari dalam array, bukan
membandingkan record dengan isi pada array. Fungsi yang mengembalikan
nilai atau kunci disebut fungsi hash (hashfunction) dan array yang
digunakan disebut tabel hash (hash table). Hash tablemenggunakan
struktur data array asosiatif yang mengasosiasikan recorddengan
sebuah field kunci unik berupa bilangan (hash) yang merupakan
representasi dari record tersebut.
1. Metode
Open Addresing
·
Bersifat linear probing, contoh sesuai
dengan namanya jika lokasi yang telah ditempati telah terisikan dilihat lokasi
selanjutnya, apakah masih kosong atau sudah terisi
·
Fungsi hash yang dipakai adalah
f(key)
= key mod n
Contoh
:
Dengan
ketentuan sebagai berikut :
1. Ruang
alamat yang tersedia misalkan 10
2. Metode
collosin resolution yang dipakai adalah open addressing dengan linear probing
janrak 3
3. Ukuran
kunci yang masuk adalah 20, 31, 33, 40, 10,12, 30 dan 15
Penyelesaian :
Kunci
|
f(key)
|
Proses
|
Address
|
Kunci
|
|
20
|
0
|
0
|
0
|
0
|
20
|
31
|
1
|
1
|
1
|
1
|
31
|
33
|
3
|
3
|
3
|
2
|
12
|
40
|
0
|
0, 3, 6
|
6
|
3
|
33
|
10
|
0
|
0, 3, 6, 9
|
9
|
4
|
|
12
|
2
|
2
|
2
|
5
|
30
|
30
|
0
|
0, 3, 6, 9, 2, 5
|
5
|
6
|
40
|
15
|
5
|
5, 8
|
8
|
7
|
|
8
|
15
|
||||
9
|
10
|
Maka :
Probe total = 19
Probe total rata rata =
19/8 = 2
Penjelasan dari contoh diatas :
2.
Metode Coalesced Hashing
· Bila terjadi tumbukan dalam pemasukan kunci
rekaman maka, dapat dicari alamat yang paling benar atau alamat yang paling
akhir
·
Gabungan dari chaining dan openaddressing.
Coalesced hashingmenghubungkan ke tabel itu
sendiri. Seperti open addressing, metode ini
memiliki keunggulan pada penggunaan tempat dan cache dibanding metodechaining. Seperti chaining, metode ini menghasilkan lokasi penyimpanan yang lebih
menyebar, tetapi pada metode ini record yang disimpan tidak mungkin lebih banyak daripada ruang
yang disediakan tabel.
Contoh
:
1. Jika
ingin dilakukan penyisipan rekaman rekaman dengan kunci 38, 51, 40, 6183, 24,
dan 60
2. Langkah
1 lakukan proses hassing semua kunci dengan kunci modular 11 ( 11 adalah
kapasitas berkas) maka dihasilkan :
Penyelesaian
:
Kunci
|
f(key)
|
Alamat
|
Rekaman
|
Medan Penghubung
|
38
|
0
|
|||
51
|
1
|
|||
40
|
2
|
24
|
||
61
|
3
|
|||
83
|
4
|
|||
24
|
5
|
38
|
10
|
|
60
|
6
|
61
|
9
|
|
7
|
51
|
8
|
||
8
|
40
|
|||
9
|
83
|
|||
10
|
60
|
Penjelasan dari contoh diatas :
Latihan Soal
