Sistem Berkas
Master File: Merupakan file yg digunakan untuk menyimpan data dari sistem informasi tertentu secara lengkap dan dipelihara secara teratur.
Contohnya:
Konsep Metode Hash Search
Metode Hash Search merupakan salah satu metode penempatan dan pencarian data yang dilakukan secara langsung (Direct Access).
Setiap data pada metode Hash Search dapat ditemukan dengan sekali pemasukan terhadap tabel yang digunakan untuk menyimpan data tersebut, karena lokasi data dalam tabel hanya tergantung pada key yang digunakan dan tidak tergantung pada key yang lain seperti pada tree.
Terdapat 2 jenis metode Hash Search pada umumnya, yakni
Close Hash (Hash Tertutup) : Ukuran tabel terbatas sehingga jumlah data yang dapat ditempatkan juga terbatas.
Open Hash (Hash Terbuka) : Ukuran tabel terbatas, tetapi setiap index dari tabel memanfaatkan linked list untuk menempatkan data sehingga jumlah data tidak terbatas.
Secara umum fungsi Hash (H) adalah fungsi untuk mengkonversi himpunan key (K) menjadi himpunan alamat (L).
H (K) = L
Close Hash
Fungsi Close Hash ditentukan sebagai :
Untuk index tabel mulai dari 0 s/d N – 1
H (K) = K mod N
Untuk index tabel mulai dari 1 s/d N
H (K) = (K mod N) + 1
Misalnya L terdiri dari 100 alamat mulai dari index 0, maka untuk menyimpan data 10347, 87492, dan 34212 adalah :
H (10347) = 10347 mod 100 = 47
H (87492) = 87492 mod 100 = 92
H (34212) = 34212 mod 100 = 12
Jika 2 buah data atau lebih dengan key yang berbeda tetapi memiliki alamat hash yang sama, maka akan terjadi tabrakan (Collision).
Solusi untuk mengatasi collision pada hash disebut Collision Resolution.
Collision Resolution dapat dilakukan dengan 3 strategi, yakni :
Linier Resolution
Overflow
Double Hash
Linier Resolution
Resolusi linear memanfaatkan nilai H (K) yang sebelumnya untuk mencari alamat kosong dengan menghitung nilai hash yang baru (Rehashing).
H’i (K) = (H’i – 1 (K) + 1) mod N
Hal ini dilakukan hingga ditemukan tempat kosong untuk menampung K atau sampai dilakukan penelusuran 1 kali lintasan ukuran tabel dan tidak ditemukan tempat kosong karena tabel telah penuh.
Overflow
Overflow mengurangi frekwensi tabrakan dengan membagi tabel menjadi 2 buah yakni tabel Utama dan tabel Overflow, dengan ketentuan ukuran tabel Utama harus lebih besar. Penempatan / pencarian data diprioritaskan pada tabel Utama, jika terjadi tabrakan maka dilakukan penempatan / pencarian pada tabel Overflow.
Penempatan / pencarian pada Tabel Overflow dapat dilakukan secara sequential atau menggunakan fungsi Hash yang baru.
Double Hash
Double Hash mirip dengan Overflow, bedanya ukuran ke-2 tabel adalah sama. Ke-2 tabel dapat diberi nama T1 dan T2.
Penempatan / pencarian data diprioritaskan pada T1, jika terjadi tabrakan, maka cek ke T2. Apabila posisi pada T2 juga terjadi tabrakan, maka dilakukan Linier Resolution dengan mengecek alamat pada T1 dan T2 hingga diperoleh tempat kosong atau tabel telah penuh.
Open Hash
Open Hash atau pengandengan (Chaining) merupakan strategi lain yang digunakan untuk mengatasi kemungkinan terjadi tabrakan terhadap alamat hash. Open hash memanfaatkan prinsip linked list yang dipasangkan pada setiap alamat hash.
Setiap alamat hash merupakan kepala tunggal dari linked list untuk menyimpan data dengan alamat yang sama.
Open Hash terdiri dari 2 bentuk, yakni :
Modification Open Hash : Terdiri atas Hash Luar dan Hash Dalam, dimana Hash Luar merupakan tabel alamat hash dan Hash Dalam untuk menyimpan data. Pada Open Hash Modifikasi ini, data yang disimpan masih terbatas karena ukuran Hash Dalam terbatas.
Linked List Open Hash : Semua data akan disimpan ke dalam linked list yang ditunjukkan oleh alamat hash. Data yang dapat disimpan tidak terbatas.
Modification Open Hash
Penempatan / pencarian data dimulai dari fungsi hash dari hash luar, kemudian fungsi hash dari hash dalam. Jika terjadi tabrakan, maka lakukan Linear Resolution terhadap hash dalam.
Apabila tabel hash dalam dari alamat hash luar yang ditunjuk telah penuh, maka lakukan Linear Resolution terhadap hash luar.
Linked List Open Hash
Penempatan / pencarian data dilakukan dengan fungsi hash untuk mendapatkan alamat hash.
Alamat hash yang telah diperoleh akan menunjukkan dimana data akan disisipkan.
Penyisipan data dapat dilakukan secara sisip depan atau sisip belakang.
Kelebihan dan Kelemahan
Close hash :
Kelebihan : Akses data lebih cepat
Kelemahan : Jumlah data terbatas
Open hash :
Kelebihan : Selain akses data lebih cepat, jumlah data tidak dibatasi
Kelemahan : Waktu akses lebih lama karena banyaknya pointer yang digunakan, yakni
Jumlah Pointer = Ukuran Tabel + (2 x Ukuran Cell)
Probe
Probe digunakan untuk menentukan besar efisiensi fungsi hash dengan mengukur banyaknya perbandingan Key yang diperlukan untuk mencari alamat dari data.
Contoh Soal
Diketahui data dengan key 25, 76, 63, 98, 58, 19.
Tempatkan data tersebut ke dalam close hash dengan ukuran tabel = 5 dengan penanganan collision :
Linier Resolution
Overflow dengan ukuran overflow = 3 dan penempatan overflow dengan fungsi hash
Double Hash
Tempatkan data tersebut ke dalam open hash dengan :
Modification Open Hash dengan ukuran hash luar = 3 dan hash dalam = 4
Linked List Open Hash dengan ukuran tabel = 3
Kemudian tentukan probe.
Pembahasan Soal
Linier Resolution :
H (25) = 25 mod 5 = 0
H (76) = 76 mod 5 = 1
H (63) = 63 mod 5 = 3
H (98) = 98 mod 5 = 3
H’1 (98) = (3 + 1) mod 5 = 4
H (58) = 58 mod 5 = 3
H’1 (58) = (3 + 1) mod 5 = 4
H’2 (58) = (4 + 1) mod 5 = 0
H’3 (58) = (0 + 1) mod 5 = 1
H’4 (58) = (1 + 1) mod 5 = 2
H (19) = 19 mod 5 = 4
H’1 (19) = (4 + 1) mod 5 = 0
H’2 (19) = (0 + 1) mod 5 = 1
H’3 (19) = (1 + 1) mod 5 = 2
H’4 (19) = (2 + 1) mod 5 = 3
H’5 (19) = (3 + 1) mod 5 = 4 {Ditolak karena tabel penuh}
Probe = (1 + 1 + 1 + 2 + 5) / 5 = 10 / 5 = 2
Overflow :
H (25) = 25 mod 5 = 0
H (76) = 76 mod 5 = 1
H (63) = 63 mod 5 = 3
H (98) = 98 mod 5 = 3 (Overflow)
HO (98) = 98 mod 3 = 2
H (58) = 58 mod 5 = 3 (Overflow)
HO (58) = 58 mod 3 = 1
H (19) = 19 mod 5 = 4
Double Hash :
H (25) = 25 mod 5 = 0 (T1)
H (76) = 76 mod 5 = 1 (T1)
H (63) = 63 mod 5 = 3 (T1)
H (98) = 98 mod 5 = 3 (T2)
H (58) = 58 mod 5 = 3
H’1 (58) = (3 + 1) mod 5 = 4 (T1)
H (19) = 19 mod 5 = 4 (T2)
Modification Open Hash :
Hluar (25) = 25 mod 3 = 1
Hdalam (25) = 25 mod 4 = 1
Hluar (76) = 76 mod 3 = 1
Hdalam (76) = 76 mod 4 = 0
Hluar (63) = 63 mod 3 = 0
Hdalam (63) = 63 mod 4 = 3
Hluar (98) = 98 mod 3 = 2
Hdalam (98) = 98 mod 4 = 2
Hluar (58) = 58 mod 3 = 1
Hdalam (58) = 58 mod 4 = 2
Hluar (19) = 19 mod 3 = 1
Hdalam (19) = 19 mod 4 = 3
Apabila disisipkan lagi key :
Hluar (34) = 34 mod 3 = 1
Hdalam (34) = 34 mod 4 = 2
Hdalam (34) = (2 + 1) mod 4 = 3
Hdalam (34) = (3 + 1) mod 4 = 0
Hdalam (34) = (0 + 1) mod 4 = 1
Hluar (34) = (1 + 1) mod 3 = 2
Hdalam (34) = 34 mod 4 = 2
Hdalam (34) = (2 + 1) mod 4 = 3
Probe = (1 + 1 + 1 + 1 + 1 + 1 + 6) / 4 = 12 / 4 = 3
Linked List Open Hash :
H (25) = 25 mod 3 = 1
H (76) = 76 mod 3 = 1
H (63) = 63 mod 3 = 0
H (98) = 98 mod 3 = 2
H (58) = 58 mod 3 = 1
H (19) = 19 mod 3 = 1
Probe = (1 + 2 + 1 + 1 + 3 + 4) / 6 = 12 / 6 = 2
Perfect Hash Function
Perfect Hash Function merupakan metode hash yang tidak akan mengalami tabrakan (collision).
Digunakan untuk data-data dalam jumlah besar dan tidak akan mengalami penyisipan atau perubahan nilai dalam jangka waktu lama.
Umumnya Perfect Hash Function digunakan untuk data-data yang berupa string.
Hasil dari alamat hash tidak akan menyisakan tempat kosong pada tabel hash sehingga disebut sebagai Minimal Perfect Hash.
Salah satu algoritma untuk mencari fungsi minimal perfect hash untuk string adalah algoritma Cichelli.
H (S) = (size + G (1st char) + G (last char)) mod N
Size = length of String
Algoritma Cichelli
Algoritma
Tentukan frekwensi dari setiap karakter pertama dan terakhir dari setiap string.
Hitung total frekwensi dari karakter pertama dan terakhir untuk setiap string.
Urutkan string berdasarkan total frekwensi secara descending.
Tentukan nilai dari fungsi G untuk setiap karakter pertama dan terakhir dari setiap string.
Tentukan alamat hash H, jika terjadi tabrakan, maka kembali ke langkah sebelumnya dan tambahkan nilai fungsi G (nilai fungsi G harus sesuai dengan himpunan subset yang telah diketahui sebelumnya).
Minimal Perfect Hash
Tabel hash dinyatakan valid / sah apabila tidak ada ruang kosong atau tabrakan.
Tabrakan muncul jika ada 2 string atau lebih dimana karakter pertama dan terakhir untuk string tersebut adalah sama serta panjang string adalah sama, misalnya DoublE dan Delete.
Penanganan tabrakan dapat dilakukan dengan 2 cara yakni :
Memanfaatkan fungsi G untuk alternatif sembarang karakter ke-3 dari string selain karakter pertama dan terakhir.
Memisahkan string menjadi 2 string.
Contoh Soal
Tempatkan 9 string berikut ke dalam tabel dengan algoritma Cichelli :
DO DOWNTO ELSE
END IF IN
TYPE VAR WITH
Dengan subset {0, 1, 2, 3}
Pembahasan Soal
Tentukan frekwensi dari setiap karakter pertama dan terakhir dari setiap string :
Hitung total frekwensi dari karakter pertama dan terakhir untuk setiap string :
Urutkan string berdasarkan total frekwensi secara descending :
Hitung fungsi G untuk setiap string :
ELSE : Length = 4
G (E) = 0 H (S) = 4 + G (E) + G (E)
= 4 + 0 + 0 = 4 {4}
END : Length = 3
G (D) = 0 H (S) = 3 + G (E) + G (D)
= 3 + 0 + 0 = 3 {34}
DO : Length = 2
G (O) = 0 H (S) = 2 + G (D) + G (O)
= 2 + 0 + 0 = 2 {234}
DOWNTO : Length = 6
H (S) = 6 + G (D) + G (O) = 6 + 0 + 0 = 6 {2346}
TYPE : Length = 4
G (T) = 0 H (S) = 4 + G (T) + G (E)
= 4 + 0 + 0 = 4
G (T) = 1 H (S) = 4 + 1 + 0 = 5 {23456}
IF : Length = 2
G (I) = 0; G (F) = 0 H (S) = 2 + G (I) + G (F)
= 2 + 0 + 0 = 2
G (I) = 1; G (F) = 0 H (S) = 2 + 1 + 0 = 3
G (I) = 2; G (F) = 0 H (S) = 2 + 2 + 0 = 4
G (I) = 3; G (F) = 0 H (S) = 2 + 3 + 0 = 5
G (I) = 3; G (F) = 1 H (S) = 2 + 3 + 1 = 6
G (I) = 3; G (F) = 2 H (S) = 2 + 3 + 0 = 7 {234567}
IN : Length = 2
G (N) = 0 H (S) = 2 + G (I) + G (N)
= 2 + 3 + 0 = 5
G (N) = 1 H (S) = 2 + 3 + 1 = 6
G (N) = 2 H (S) = 2 + 3 + 2 = 7
G (N) = 3 H (S) = 2 + 3 + 3 = 8 {2345678}
VAR : Length = 3
G (V) = 0; G (R) = 0 H (S)= 3 + G (V) + G (R)
= 3 + 0 + 0 = 3
G (V) = 1; G (R) = 0 H (S) = 3 + 1 + 0 = 4
G (V) = 2; G (R) = 0 H (S) = 3 + 2 + 0 = 5
G (V) = 3; G (R) = 0 H (S) = 3 + 3 + 0 = 6
G (V) = 3; G (R) = 1 H (S) = 3 + 3 + 1 = 7
G (V) = 3; G (R) = 2 H (S) = 3 + 3 + 2 = 8
G (V) = 3; G (R) = 3 H (S) = 3 + 3 + 3 = 9
= 9 mod 9 = 0 {02345678}
WITH : Length = 4
G (W) = 0; G (H) = 0 H (S) = 4 + G (W) + G (H)
= 4 + 0 + 0 = 4
G (W) = 1; G (H) = 0 H (S) = 4 + 1 + 0 = 5
G (W) = 2; G (H) = 0 H (S) = 4 + 2 + 0 = 6
G (W) = 3; G (H) = 0 H (S) = 4 + 3 + 0 = 7
G (W) = 3; G (H) = 1 H (S) = 4 + 3 + 1 = 8
G (W) = 3; G (H) = 2 H (S) = 4 + 3 + 2 = 9 = 0
G (W) = 3; G (H) = 3 H (S) = 4 + 3 + 3 = 10
= 10 mod 9 = 1 {012345678}
Sehingga diperoleh G-Values adalah :
E = D = O = 0
T = 1
F = 2
I = N = V = R = W = 3
Hasil akhir pada tabel hash adalah :
Konsep File Hash
Merupakan organisasi file dengan metode akses langsung (Direct Access), yang menggunakan suatu fungsi untuk memetakan key menjadi address.
Fungsi yang digunakan adalah fungsi hash / KAT (Key to Address Transformation).
Address yang dihasilkan dari hasil perhitungan fungsi hash disebut dengan istilah Home Address.
Terdapat 2 komponen dalam file hash :
Ruang record, yang terdiri atas M slot address
Fungsi hash, yang mentransformasikan key menjadi address
Transformasi key akan mudah jika key telah berupa nilai integer. Untuk key berupa karakter alphanumerik, terdapat proses pra kondisi untuk mengubahnya menjadi suatu nilai integer.
Fungsi Hash
Ada beberapa fungsi hash yang dapat digunakan :
Key mod N, dengan N = jumlah 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 Key mod N = 0
Untuk r <> 0, maka Key mod N = N – r
Key mod P, dengan P = bilangan prima terkecil yang >= N
Truncation / Substringing, cara transformasi yang dilakukan dengan mengambil hanya sebagian digit dari Key.
Misalnya jika Key = 123-45-6789 akan dipetakan pada address yang terdiri atas 1000 slot, maka dapat dilakukan pengambilan 3 digit (secara acak atau terurut) dari Key tersebut untuk menentukan addressnya.
Folding, dapat dilakukan dengan cara :
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 :
Folding by Shifting
Contoh jika Key = 123456789, maka transfomasi ke-3 digit address dengan teknik Folding by Shifting dapat dilakukan dengan membagi digit Key tersebut dengan cara seolah-olah menggeser batas pembagian digit seperti berikut :
Radix Convertion, dengan mentransformasikan key menjadi bilangan basis lain untuk mendapatkan nilai hashnya. Umumnya basis yang digunakan diluar dari basis 2 – 10.
Misalnya jika Key = 38652 akan ditempatkan dalam tabel berukuran 10000 dengan basis 11, maka :
3×114 + 8×113 + 6×112 + 5×111 + 2×110 = 5535411
Nilai hash 55354 telah melampaui batas hash, maka pecahan terbesar dari hash tersebut akan dibuang, sehingga didapatkan hash 5354.
Mid-Square, mentransformasikan key dengan cara dikuadrat dan diambil bagian tengah sebagai nilai hash.
Misalnya jika Key = 3121 akan ditempatkan pada tabel berukuran 1000, maka 31212 = 9740641, diambil 406 sebagai nilai hashnya.
Collision
Collision merupakan kondisi dimana terdapat lebih dari 1 key yang menempati slot address yang sama.
Collision dapat diminimalisir dengan cara :
Mengganti fungsi hash
Mengurangi packing factor
Packing Factor / Packing Density / Load Factor adalah perbandingan antara jumlah data yang tersimpan terhadap jumlah slot address yang tersedia.
Collision Resolution
Mengganti fungsi hash atau mengurangi packing factor hanyalah suatu teknik 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 :
Dengan link : Coalesced Hashing
Tanpa link
Posisi record static : Progressive Overflow, Linear Quotient
Posisi record dinamis : Binary Tree, Cuckoo Hashing, Brent’s Method
Dengan pseudolink : Computed Chaining
Coalesced Hash
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.
Progressive Overflow
Disebut juga metode Linear Probing
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.
Linear Quotient
Disebut juga dengan metode Double Hashing.
Menggunakan 2 fungsi hash, yaitu fungsi H1 untuk menentukan home address dan fungsi H2 untuk menentukan increment jika terjadi collision.
Metode ini dapat digunakan dengan syarat ukuran tabel merupakan bilangan prima sehingga kemungkinan terjadinya siklus pencarian pada slot yang sama dapat dihindari.
Linear Quotient
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.
Binary Tree
Metode ini dikembangkan oleh Gonnet & Munro.
Menggunakan struktur Binary Tree untuk pencarian address ketika terjadi collision, dengan memberikan 2 pilihan langkah :
Continue : Melanjutkan pencarian address berikutnya yang mungkin ditempati oleh record yang akan di-sisipkan.
Move : Memindahkan record yang menempati address ke address berikutnya yang memungkinkan untuk ditempati record lama.
Binary Tree yang digunakan berorientasi Breadth First.
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 :
CREATE cabang kiri dengan menjumlahkan increment (new key) + current address.
CREATE cabang kanan dengan menjumlahkan increment (key pada node) + current address.
END WHILE
………
{Tabel penuh atau new address kosong}
IF tabel penuh THEN
Proses sisip tidak dilakukan, keluarkan pesan “Tabel Penuh”.
ELSE
Sisip record pada new address dengan cara :
IF new address didapatkan di cabang kiri THEN
Sisip record baru ke posisi new address.
ELSE
Pindahkan parent (new address) ke new address.
Sisip record baru ke posisi parent (new address).
Cuckoo Hashing
Metode ini dikemukakan oleh Rasmus Pagh dan Flemming Friche Rodler pada tahun 2001.
Dapat menggunakan 1 atau 2 tabel hash.
Menggunakan 2 fungsi hash (H1 dan H2) untuk melakukan pertukaran / pemindahan key.
Apabila dengan 1 tabel, maka H1 dan H2 akan mengacu pada tabel yang sama, tetapi dengan fungsi yang berbeda.
Untuk 1 tabel, fungsi H1 menghasilkan hash untuk ½ tabel, dan H2 menghasilkan hash untuk ½ tabel yang tersisa.
Apabila dengan 2 tabel, maka H1 adalah fungsi untuk tabel – 1, dan H2 adalah fungsi untuk tabel – 2.
Key baru akan menyisihkan key lama pada posisi yang ditunjuk. Key lama yang tersisih akan menyisihkan lagi Key lama pada posisi yang ditunjuk berikutnya. Proses ini akan berjalan terus hingga ditemukan tempat kosong atau tabel telah penuh.
Dapat terjadi deadlock apabila alamat hash yang dihasilkan dari H1 dan H2 adalah sama untuk 3 kali perulangan pencarian tempat kosong secara berturut-turut.
Penanganan deadlock dapat dilakukan dengan 2 cara yakni :
Menambahkan fungsi hash modifikasi dari H1 atau H2 sedemikian hingga alamat hash yang dihasilkan dari H1 dan H2 menjadi berbeda.
Membatasi perulangan hingga suatu “MaxLoop” sedemikian hingga apabila jumlah perulangan telah mencapai MaxLoop dan masih belum menemukan tempat kosong maka proses penyisipan selesai.
Algoritma dengan 1 tabel :
Nyatakan x = new key.
Tentukan home address dari x dengan H1 dan H2 H1 (x) dan H2 (x).
WHILE new address belum kosong dan tabel belum penuh DO
IF key [ H1 (x) ] atau key [ H2 (x) ] = x THEN
Proses sisip tidak dilakukan, keluar pesan “key telah ada”.
ELSE
pos = H1 (x).
WHILE tabel belum penuh dan belum terjadi deadlock DO
IF key (pos) kosong THEN
Sisip record baru pada pos.
Proses sisip selesai.
ELSE
………
Tukarkan key (pos) x.
IF pos = H1(x) THEN
pos = H2 (x).
ELSE
pos = H1 (x).
END WHILE
END WHILE
Algoritma dengan 2 tabel :
Nyatakan x = new key.
Tentukan home address dari x dengan H1 dan H2 H1 (x) dan H2 (x).
WHILE new address belum kosong dan tabel belum penuh DO
IF key T1 [ H1 (x) ] atau key T2 [ H2 (x) ] = x THEN
Proses sisip tidak dilakukan, keluar pesan “key telah ada”.
ELSE
WHILE belum terjadi deadlock DO
IF key T1 [ H1 (x) ] kosong THEN
Sisip record baru pada T1 [ H1 (x) ].
Proses sisip selesai.
ELSE
………
Tukarkan key T1 [ H1 (x) ] x.
IF key T2 [ H2 (x) ] kosong THEN
Sisip record baru pada T2 [ H2 (x) ].
Proses sisip selesai.
ELSE
Tukarkan key T2 [ H2 (x) ] x.
END WHILE
END WHILE
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.
Pengurutan Eksternal
Waktu yang paling banyak dihabiskan dalam pengelolaan file adalah waktu untuk menata ulang record dan waktu aktivitas pencarian.
Alasan diperlukan pengurutan data :
Penyajian data : Hasil laporan dari analisis data dari file dapat disajikan kepada user dengan cepat dan akurat.
Penggabungan file : Adanya 2 atau lebih file dengan susunan record yang berbeda harus digabungkan untuk keperluan analisis data.
Pembuatan index : Index diperlukan untuk proses pencarian data.
Ketika data yang akan disortir terlalu besar untuk dapat masuk ke dalam memori utama, maka diperlukan Pengurutan Eksternal (External Sorting).
Algoritma External Sorting ini digunakan untuk meminimalkan waktu akses disk.
Pengurutan eksternal yang paling efektif adalah algoritma Merge Sort.
Pengurutan eksternal merge sort dibagi dalam 2 tahap, yakni :
Sort Phase : Pengurutan terhadap masing-masing blok file sumber dan mengisinya ke dalam sort-block buffer.
Merge Phase : Penggabungan blok-blok file sumber yang telah terurut di dalam buffer menjadi 1 blok file tujuan.
Two-Way Merge Sort
External Sorting memanfaatkan algoritma Two-Way Merge Sort.
Hanya memanfaatkan 3 halaman memori utama, sedangkan halaman memori utama yng tersedia sangat banyak.
Pengurutan dilakukan dalam beberapa tahap.
Tahap pertama, halaman dalam file dibaca satu per satu, record didalamnya diurutkan dan halaman yang telah terurut ditulis kembali.
Pengurutan di dalam halaman dapat menggunakan algoritma pengurutan yang umum digunakan.
Pada tahap berikutnya, pasangan run dari output pada tahap sebelumnya akan dibaca dan digabungkan untuk menghasilkan run yang panjangnya 2 kali lipat sebelumnya.
Jika jumlah halaman dalam file input = 2k, untuk beberapa k, maka :
Tahap 0 diperoleh 2k run terurut masing-masing 1 halaman
Tahap 1 diperoleh 2k–1 run terurut masing-masing 2 halaman
Tahap 2 diperoleh 2k–2 run terurut masing-masing 4 halaman
Tahap k diperoleh 1 run 2k halaman terurut
External Merge Sort
Jika memori utama memiliki halaman buffer sebanyak B ruang buffer, maka untuk mengurutkan file yang besar yang memiliki N halaman, maka :
Tahap 0, baca B halaman dan urut secara internal, diperoleh run N / B untuk masing-masing B halaman (kecuali run terakhir yang mungkin berisi sedikit halaman).
Tahap i = 1, 2, …, baca (B – 1) halaman buffer untuk input dan gunakan sisa halaman untuk output, dengan demikian, telah dilakukan (B – 1) cara penggabungan dalam tiap tahap.
Jika ingin mengurutkan file yang memiliki 108 halaman dengan menggunakan buffer 5 halaman, maka :
Tahap 0 diperoleh 108 / 5 = 22 run terurut dengan masing-masing 5 halaman, kecuali run terakhir yang hanya 3 halaman.
Tahap 1 diperoleh 22 / 4 = 6 run terurut dengan masing-masing 20 halaman, kecuali run terakhir yang hanya 8 halaman.
Tahap 2 diperoleh 6 / 4 = 2 run terurut dengan 1 run 80 halaman dan sisanya 28 halaman.
Tahap 3 diperoleh 2 / 2 = 1 run dengan menggabungkan 2 run dari tahap 2 untuk menghasilkan file terurut.
Contohnya:
- Payroll Master File
- Customer Master File
- Inventory Master file
- Reference Master File, file yg tetap/berubah. Cth, File pelanggan yang berisi nama, alamat dan no. rekening.
- Dynamic Master File, file yg berisi record yg terus menesrus berubah dalam kurun waktu tertentu/berdasarkan suatu peristiwa transaksi. Cth, File stock barang & file pemesanan tempat duduk.
Konsep Metode Hash Search
Metode Hash Search merupakan salah satu metode penempatan dan pencarian data yang dilakukan secara langsung (Direct Access).
Setiap data pada metode Hash Search dapat ditemukan dengan sekali pemasukan terhadap tabel yang digunakan untuk menyimpan data tersebut, karena lokasi data dalam tabel hanya tergantung pada key yang digunakan dan tidak tergantung pada key yang lain seperti pada tree.
Terdapat 2 jenis metode Hash Search pada umumnya, yakni
Close Hash (Hash Tertutup) : Ukuran tabel terbatas sehingga jumlah data yang dapat ditempatkan juga terbatas.
Open Hash (Hash Terbuka) : Ukuran tabel terbatas, tetapi setiap index dari tabel memanfaatkan linked list untuk menempatkan data sehingga jumlah data tidak terbatas.
Secara umum fungsi Hash (H) adalah fungsi untuk mengkonversi himpunan key (K) menjadi himpunan alamat (L).
H (K) = L
Close Hash
Fungsi Close Hash ditentukan sebagai :
Untuk index tabel mulai dari 0 s/d N – 1
H (K) = K mod N
Untuk index tabel mulai dari 1 s/d N
H (K) = (K mod N) + 1
Misalnya L terdiri dari 100 alamat mulai dari index 0, maka untuk menyimpan data 10347, 87492, dan 34212 adalah :
H (10347) = 10347 mod 100 = 47
H (87492) = 87492 mod 100 = 92
H (34212) = 34212 mod 100 = 12
Jika 2 buah data atau lebih dengan key yang berbeda tetapi memiliki alamat hash yang sama, maka akan terjadi tabrakan (Collision).
Solusi untuk mengatasi collision pada hash disebut Collision Resolution.
Collision Resolution dapat dilakukan dengan 3 strategi, yakni :
Linier Resolution
Overflow
Double Hash
Linier Resolution
Resolusi linear memanfaatkan nilai H (K) yang sebelumnya untuk mencari alamat kosong dengan menghitung nilai hash yang baru (Rehashing).
H’i (K) = (H’i – 1 (K) + 1) mod N
Hal ini dilakukan hingga ditemukan tempat kosong untuk menampung K atau sampai dilakukan penelusuran 1 kali lintasan ukuran tabel dan tidak ditemukan tempat kosong karena tabel telah penuh.
Overflow
Overflow mengurangi frekwensi tabrakan dengan membagi tabel menjadi 2 buah yakni tabel Utama dan tabel Overflow, dengan ketentuan ukuran tabel Utama harus lebih besar. Penempatan / pencarian data diprioritaskan pada tabel Utama, jika terjadi tabrakan maka dilakukan penempatan / pencarian pada tabel Overflow.
Penempatan / pencarian pada Tabel Overflow dapat dilakukan secara sequential atau menggunakan fungsi Hash yang baru.
Double Hash
Double Hash mirip dengan Overflow, bedanya ukuran ke-2 tabel adalah sama. Ke-2 tabel dapat diberi nama T1 dan T2.
Penempatan / pencarian data diprioritaskan pada T1, jika terjadi tabrakan, maka cek ke T2. Apabila posisi pada T2 juga terjadi tabrakan, maka dilakukan Linier Resolution dengan mengecek alamat pada T1 dan T2 hingga diperoleh tempat kosong atau tabel telah penuh.
Open Hash
Open Hash atau pengandengan (Chaining) merupakan strategi lain yang digunakan untuk mengatasi kemungkinan terjadi tabrakan terhadap alamat hash. Open hash memanfaatkan prinsip linked list yang dipasangkan pada setiap alamat hash.
Setiap alamat hash merupakan kepala tunggal dari linked list untuk menyimpan data dengan alamat yang sama.
Open Hash terdiri dari 2 bentuk, yakni :
Modification Open Hash : Terdiri atas Hash Luar dan Hash Dalam, dimana Hash Luar merupakan tabel alamat hash dan Hash Dalam untuk menyimpan data. Pada Open Hash Modifikasi ini, data yang disimpan masih terbatas karena ukuran Hash Dalam terbatas.
Linked List Open Hash : Semua data akan disimpan ke dalam linked list yang ditunjukkan oleh alamat hash. Data yang dapat disimpan tidak terbatas.
Modification Open Hash
Penempatan / pencarian data dimulai dari fungsi hash dari hash luar, kemudian fungsi hash dari hash dalam. Jika terjadi tabrakan, maka lakukan Linear Resolution terhadap hash dalam.
Apabila tabel hash dalam dari alamat hash luar yang ditunjuk telah penuh, maka lakukan Linear Resolution terhadap hash luar.
Linked List Open Hash
Penempatan / pencarian data dilakukan dengan fungsi hash untuk mendapatkan alamat hash.
Alamat hash yang telah diperoleh akan menunjukkan dimana data akan disisipkan.
Penyisipan data dapat dilakukan secara sisip depan atau sisip belakang.
Kelebihan dan Kelemahan
Close hash :
Kelebihan : Akses data lebih cepat
Kelemahan : Jumlah data terbatas
Open hash :
Kelebihan : Selain akses data lebih cepat, jumlah data tidak dibatasi
Kelemahan : Waktu akses lebih lama karena banyaknya pointer yang digunakan, yakni
Jumlah Pointer = Ukuran Tabel + (2 x Ukuran Cell)
Probe
Probe digunakan untuk menentukan besar efisiensi fungsi hash dengan mengukur banyaknya perbandingan Key yang diperlukan untuk mencari alamat dari data.
Contoh Soal
Diketahui data dengan key 25, 76, 63, 98, 58, 19.
Tempatkan data tersebut ke dalam close hash dengan ukuran tabel = 5 dengan penanganan collision :
Linier Resolution
Overflow dengan ukuran overflow = 3 dan penempatan overflow dengan fungsi hash
Double Hash
Tempatkan data tersebut ke dalam open hash dengan :
Modification Open Hash dengan ukuran hash luar = 3 dan hash dalam = 4
Linked List Open Hash dengan ukuran tabel = 3
Kemudian tentukan probe.
Pembahasan Soal
Linier Resolution :
H (25) = 25 mod 5 = 0
H (76) = 76 mod 5 = 1
H (63) = 63 mod 5 = 3
H (98) = 98 mod 5 = 3
H’1 (98) = (3 + 1) mod 5 = 4
H (58) = 58 mod 5 = 3
H’1 (58) = (3 + 1) mod 5 = 4
H’2 (58) = (4 + 1) mod 5 = 0
H’3 (58) = (0 + 1) mod 5 = 1
H’4 (58) = (1 + 1) mod 5 = 2
H (19) = 19 mod 5 = 4H’1 (19) = (4 + 1) mod 5 = 0
H’2 (19) = (0 + 1) mod 5 = 1
H’3 (19) = (1 + 1) mod 5 = 2
H’4 (19) = (2 + 1) mod 5 = 3
H’5 (19) = (3 + 1) mod 5 = 4 {Ditolak karena tabel penuh}
Probe = (1 + 1 + 1 + 2 + 5) / 5 = 10 / 5 = 2
Overflow :
H (25) = 25 mod 5 = 0
H (76) = 76 mod 5 = 1
H (63) = 63 mod 5 = 3
H (98) = 98 mod 5 = 3 (Overflow)
HO (98) = 98 mod 3 = 2
H (58) = 58 mod 5 = 3 (Overflow)
HO (58) = 58 mod 3 = 1
H (19) = 19 mod 5 = 4
Double Hash :
H (25) = 25 mod 5 = 0 (T1)
H (76) = 76 mod 5 = 1 (T1)
H (63) = 63 mod 5 = 3 (T1)
H (98) = 98 mod 5 = 3 (T2)
H (58) = 58 mod 5 = 3
H’1 (58) = (3 + 1) mod 5 = 4 (T1)
H (19) = 19 mod 5 = 4 (T2)
Modification Open Hash :
Hluar (25) = 25 mod 3 = 1
Hdalam (25) = 25 mod 4 = 1
Hluar (76) = 76 mod 3 = 1
Hdalam (76) = 76 mod 4 = 0
Hluar (63) = 63 mod 3 = 0
Hdalam (63) = 63 mod 4 = 3
Hluar (98) = 98 mod 3 = 2
Hdalam (98) = 98 mod 4 = 2
Hluar (58) = 58 mod 3 = 1
Hdalam (58) = 58 mod 4 = 2
Hluar (19) = 19 mod 3 = 1
Hdalam (19) = 19 mod 4 = 3
Apabila disisipkan lagi key :
Hluar (34) = 34 mod 3 = 1
Hdalam (34) = 34 mod 4 = 2
Hdalam (34) = (2 + 1) mod 4 = 3
Hdalam (34) = (3 + 1) mod 4 = 0
Hdalam (34) = (0 + 1) mod 4 = 1
Hluar (34) = (1 + 1) mod 3 = 2
Hdalam (34) = 34 mod 4 = 2
Hdalam (34) = (2 + 1) mod 4 = 3
Probe = (1 + 1 + 1 + 1 + 1 + 1 + 6) / 4 = 12 / 4 = 3
Linked List Open Hash :
H (25) = 25 mod 3 = 1
H (76) = 76 mod 3 = 1
H (63) = 63 mod 3 = 0
H (98) = 98 mod 3 = 2
H (58) = 58 mod 3 = 1
H (19) = 19 mod 3 = 1
Probe = (1 + 2 + 1 + 1 + 3 + 4) / 6 = 12 / 6 = 2
Perfect Hash Function
Perfect Hash Function merupakan metode hash yang tidak akan mengalami tabrakan (collision).
Digunakan untuk data-data dalam jumlah besar dan tidak akan mengalami penyisipan atau perubahan nilai dalam jangka waktu lama.
Umumnya Perfect Hash Function digunakan untuk data-data yang berupa string.
Hasil dari alamat hash tidak akan menyisakan tempat kosong pada tabel hash sehingga disebut sebagai Minimal Perfect Hash.
Salah satu algoritma untuk mencari fungsi minimal perfect hash untuk string adalah algoritma Cichelli.
H (S) = (size + G (1st char) + G (last char)) mod N
Size = length of String
Algoritma Cichelli
Algoritma
Tentukan frekwensi dari setiap karakter pertama dan terakhir dari setiap string.
Hitung total frekwensi dari karakter pertama dan terakhir untuk setiap string.
Urutkan string berdasarkan total frekwensi secara descending.
Tentukan nilai dari fungsi G untuk setiap karakter pertama dan terakhir dari setiap string.
Tentukan alamat hash H, jika terjadi tabrakan, maka kembali ke langkah sebelumnya dan tambahkan nilai fungsi G (nilai fungsi G harus sesuai dengan himpunan subset yang telah diketahui sebelumnya).
Minimal Perfect Hash
Tabel hash dinyatakan valid / sah apabila tidak ada ruang kosong atau tabrakan.
Tabrakan muncul jika ada 2 string atau lebih dimana karakter pertama dan terakhir untuk string tersebut adalah sama serta panjang string adalah sama, misalnya DoublE dan Delete.
Penanganan tabrakan dapat dilakukan dengan 2 cara yakni :
Memanfaatkan fungsi G untuk alternatif sembarang karakter ke-3 dari string selain karakter pertama dan terakhir.
Memisahkan string menjadi 2 string.
Contoh Soal
Tempatkan 9 string berikut ke dalam tabel dengan algoritma Cichelli :
DO DOWNTO ELSE
END IF IN
TYPE VAR WITH
Dengan subset {0, 1, 2, 3}
Pembahasan Soal
Tentukan frekwensi dari setiap karakter pertama dan terakhir dari setiap string :
Hitung total frekwensi dari karakter pertama dan terakhir untuk setiap string :
Urutkan string berdasarkan total frekwensi secara descending :
Hitung fungsi G untuk setiap string :
ELSE : Length = 4
G (E) = 0 H (S) = 4 + G (E) + G (E)
= 4 + 0 + 0 = 4 {4}
END : Length = 3
G (D) = 0 H (S) = 3 + G (E) + G (D)
= 3 + 0 + 0 = 3 {34}
DO : Length = 2
G (O) = 0 H (S) = 2 + G (D) + G (O)
= 2 + 0 + 0 = 2 {234}
DOWNTO : Length = 6
H (S) = 6 + G (D) + G (O) = 6 + 0 + 0 = 6 {2346}
TYPE : Length = 4
G (T) = 0 H (S) = 4 + G (T) + G (E)
= 4 + 0 + 0 = 4
G (T) = 1 H (S) = 4 + 1 + 0 = 5 {23456}
IF : Length = 2
G (I) = 0; G (F) = 0 H (S) = 2 + G (I) + G (F)
= 2 + 0 + 0 = 2
G (I) = 1; G (F) = 0 H (S) = 2 + 1 + 0 = 3
G (I) = 2; G (F) = 0 H (S) = 2 + 2 + 0 = 4
G (I) = 3; G (F) = 0 H (S) = 2 + 3 + 0 = 5
G (I) = 3; G (F) = 1 H (S) = 2 + 3 + 1 = 6
G (I) = 3; G (F) = 2 H (S) = 2 + 3 + 0 = 7 {234567}
IN : Length = 2
G (N) = 0 H (S) = 2 + G (I) + G (N)
= 2 + 3 + 0 = 5
G (N) = 1 H (S) = 2 + 3 + 1 = 6
G (N) = 2 H (S) = 2 + 3 + 2 = 7
G (N) = 3 H (S) = 2 + 3 + 3 = 8 {2345678}
VAR : Length = 3
G (V) = 0; G (R) = 0 H (S)= 3 + G (V) + G (R)
= 3 + 0 + 0 = 3
G (V) = 1; G (R) = 0 H (S) = 3 + 1 + 0 = 4
G (V) = 2; G (R) = 0 H (S) = 3 + 2 + 0 = 5
G (V) = 3; G (R) = 0 H (S) = 3 + 3 + 0 = 6
G (V) = 3; G (R) = 1 H (S) = 3 + 3 + 1 = 7
G (V) = 3; G (R) = 2 H (S) = 3 + 3 + 2 = 8
G (V) = 3; G (R) = 3 H (S) = 3 + 3 + 3 = 9
= 9 mod 9 = 0 {02345678}
WITH : Length = 4
G (W) = 0; G (H) = 0 H (S) = 4 + G (W) + G (H)
= 4 + 0 + 0 = 4
G (W) = 1; G (H) = 0 H (S) = 4 + 1 + 0 = 5
G (W) = 2; G (H) = 0 H (S) = 4 + 2 + 0 = 6
G (W) = 3; G (H) = 0 H (S) = 4 + 3 + 0 = 7
G (W) = 3; G (H) = 1 H (S) = 4 + 3 + 1 = 8
G (W) = 3; G (H) = 2 H (S) = 4 + 3 + 2 = 9 = 0
G (W) = 3; G (H) = 3 H (S) = 4 + 3 + 3 = 10
= 10 mod 9 = 1 {012345678}
Sehingga diperoleh G-Values adalah :
E = D = O = 0
T = 1
F = 2
I = N = V = R = W = 3
Hasil akhir pada tabel hash adalah :
Konsep File Hash
Merupakan organisasi file dengan metode akses langsung (Direct Access), yang menggunakan suatu fungsi untuk memetakan key menjadi address.
Fungsi yang digunakan adalah fungsi hash / KAT (Key to Address Transformation).
Address yang dihasilkan dari hasil perhitungan fungsi hash disebut dengan istilah Home Address.
Terdapat 2 komponen dalam file hash :
Ruang record, yang terdiri atas M slot address
Fungsi hash, yang mentransformasikan key menjadi address
Transformasi key akan mudah jika key telah berupa nilai integer. Untuk key berupa karakter alphanumerik, terdapat proses pra kondisi untuk mengubahnya menjadi suatu nilai integer.
Fungsi Hash
Ada beberapa fungsi hash yang dapat digunakan :
Key mod N, dengan N = jumlah 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 Key mod N = 0
Untuk r <> 0, maka Key mod N = N – r
Key mod P, dengan P = bilangan prima terkecil yang >= N
Truncation / Substringing, cara transformasi yang dilakukan dengan mengambil hanya sebagian digit dari Key.
Misalnya jika Key = 123-45-6789 akan dipetakan pada address yang terdiri atas 1000 slot, maka dapat dilakukan pengambilan 3 digit (secara acak atau terurut) dari Key tersebut untuk menentukan addressnya.
Folding, dapat dilakukan dengan cara :
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 :
Folding by Shifting
Contoh jika Key = 123456789, maka transfomasi ke-3 digit address dengan teknik Folding by Shifting dapat dilakukan dengan membagi digit Key tersebut dengan cara seolah-olah menggeser batas pembagian digit seperti berikut :
Radix Convertion, dengan mentransformasikan key menjadi bilangan basis lain untuk mendapatkan nilai hashnya. Umumnya basis yang digunakan diluar dari basis 2 – 10.
Misalnya jika Key = 38652 akan ditempatkan dalam tabel berukuran 10000 dengan basis 11, maka :
3×114 + 8×113 + 6×112 + 5×111 + 2×110 = 5535411
Nilai hash 55354 telah melampaui batas hash, maka pecahan terbesar dari hash tersebut akan dibuang, sehingga didapatkan hash 5354.
Mid-Square, mentransformasikan key dengan cara dikuadrat dan diambil bagian tengah sebagai nilai hash.
Misalnya jika Key = 3121 akan ditempatkan pada tabel berukuran 1000, maka 31212 = 9740641, diambil 406 sebagai nilai hashnya.
Collision
Collision merupakan kondisi dimana terdapat lebih dari 1 key yang menempati slot address yang sama.
Collision dapat diminimalisir dengan cara :
Mengganti fungsi hash
Mengurangi packing factor
Packing Factor / Packing Density / Load Factor adalah perbandingan antara jumlah data yang tersimpan terhadap jumlah slot address yang tersedia.
Collision Resolution
Mengganti fungsi hash atau mengurangi packing factor hanyalah suatu teknik 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 :
Dengan link : Coalesced Hashing
Tanpa link
Posisi record static : Progressive Overflow, Linear Quotient
Posisi record dinamis : Binary Tree, Cuckoo Hashing, Brent’s Method
Dengan pseudolink : Computed Chaining
Coalesced Hash
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.
Progressive Overflow
Disebut juga metode Linear Probing
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.
Linear Quotient
Disebut juga dengan metode Double Hashing.
Menggunakan 2 fungsi hash, yaitu fungsi H1 untuk menentukan home address dan fungsi H2 untuk menentukan increment jika terjadi collision.
Metode ini dapat digunakan dengan syarat ukuran tabel merupakan bilangan prima sehingga kemungkinan terjadinya siklus pencarian pada slot yang sama dapat dihindari.
Linear Quotient
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.
Binary Tree
Metode ini dikembangkan oleh Gonnet & Munro.
Menggunakan struktur Binary Tree untuk pencarian address ketika terjadi collision, dengan memberikan 2 pilihan langkah :
Continue : Melanjutkan pencarian address berikutnya yang mungkin ditempati oleh record yang akan di-sisipkan.
Move : Memindahkan record yang menempati address ke address berikutnya yang memungkinkan untuk ditempati record lama.
Binary Tree yang digunakan berorientasi Breadth First.
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 :
CREATE cabang kiri dengan menjumlahkan increment (new key) + current address.
CREATE cabang kanan dengan menjumlahkan increment (key pada node) + current address.
END WHILE
………
{Tabel penuh atau new address kosong}
IF tabel penuh THEN
Proses sisip tidak dilakukan, keluarkan pesan “Tabel Penuh”.
ELSE
Sisip record pada new address dengan cara :
IF new address didapatkan di cabang kiri THEN
Sisip record baru ke posisi new address.
ELSE
Pindahkan parent (new address) ke new address.
Sisip record baru ke posisi parent (new address).
Cuckoo Hashing
Metode ini dikemukakan oleh Rasmus Pagh dan Flemming Friche Rodler pada tahun 2001.
Dapat menggunakan 1 atau 2 tabel hash.
Menggunakan 2 fungsi hash (H1 dan H2) untuk melakukan pertukaran / pemindahan key.
Apabila dengan 1 tabel, maka H1 dan H2 akan mengacu pada tabel yang sama, tetapi dengan fungsi yang berbeda.
Untuk 1 tabel, fungsi H1 menghasilkan hash untuk ½ tabel, dan H2 menghasilkan hash untuk ½ tabel yang tersisa.
Apabila dengan 2 tabel, maka H1 adalah fungsi untuk tabel – 1, dan H2 adalah fungsi untuk tabel – 2.
Key baru akan menyisihkan key lama pada posisi yang ditunjuk. Key lama yang tersisih akan menyisihkan lagi Key lama pada posisi yang ditunjuk berikutnya. Proses ini akan berjalan terus hingga ditemukan tempat kosong atau tabel telah penuh.
Dapat terjadi deadlock apabila alamat hash yang dihasilkan dari H1 dan H2 adalah sama untuk 3 kali perulangan pencarian tempat kosong secara berturut-turut.
Penanganan deadlock dapat dilakukan dengan 2 cara yakni :
Menambahkan fungsi hash modifikasi dari H1 atau H2 sedemikian hingga alamat hash yang dihasilkan dari H1 dan H2 menjadi berbeda.
Membatasi perulangan hingga suatu “MaxLoop” sedemikian hingga apabila jumlah perulangan telah mencapai MaxLoop dan masih belum menemukan tempat kosong maka proses penyisipan selesai.
Algoritma dengan 1 tabel :
Nyatakan x = new key.
Tentukan home address dari x dengan H1 dan H2 H1 (x) dan H2 (x).
WHILE new address belum kosong dan tabel belum penuh DO
IF key [ H1 (x) ] atau key [ H2 (x) ] = x THEN
Proses sisip tidak dilakukan, keluar pesan “key telah ada”.
ELSE
pos = H1 (x).
WHILE tabel belum penuh dan belum terjadi deadlock DO
IF key (pos) kosong THEN
Sisip record baru pada pos.
Proses sisip selesai.
ELSE
………
Tukarkan key (pos) x.
IF pos = H1(x) THEN
pos = H2 (x).
ELSE
pos = H1 (x).
END WHILE
END WHILE
Algoritma dengan 2 tabel :
Nyatakan x = new key.
Tentukan home address dari x dengan H1 dan H2 H1 (x) dan H2 (x).
WHILE new address belum kosong dan tabel belum penuh DO
IF key T1 [ H1 (x) ] atau key T2 [ H2 (x) ] = x THEN
Proses sisip tidak dilakukan, keluar pesan “key telah ada”.
ELSE
WHILE belum terjadi deadlock DO
IF key T1 [ H1 (x) ] kosong THEN
Sisip record baru pada T1 [ H1 (x) ].
Proses sisip selesai.
ELSE
………
Tukarkan key T1 [ H1 (x) ] x.
IF key T2 [ H2 (x) ] kosong THEN
Sisip record baru pada T2 [ H2 (x) ].
Proses sisip selesai.
ELSE
Tukarkan key T2 [ H2 (x) ] x.
END WHILE
END WHILE
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.
Pengurutan Eksternal
Waktu yang paling banyak dihabiskan dalam pengelolaan file adalah waktu untuk menata ulang record dan waktu aktivitas pencarian.
Alasan diperlukan pengurutan data :
Penyajian data : Hasil laporan dari analisis data dari file dapat disajikan kepada user dengan cepat dan akurat.
Penggabungan file : Adanya 2 atau lebih file dengan susunan record yang berbeda harus digabungkan untuk keperluan analisis data.
Pembuatan index : Index diperlukan untuk proses pencarian data.
Ketika data yang akan disortir terlalu besar untuk dapat masuk ke dalam memori utama, maka diperlukan Pengurutan Eksternal (External Sorting).
Algoritma External Sorting ini digunakan untuk meminimalkan waktu akses disk.
Pengurutan eksternal yang paling efektif adalah algoritma Merge Sort.
Pengurutan eksternal merge sort dibagi dalam 2 tahap, yakni :
Sort Phase : Pengurutan terhadap masing-masing blok file sumber dan mengisinya ke dalam sort-block buffer.
Merge Phase : Penggabungan blok-blok file sumber yang telah terurut di dalam buffer menjadi 1 blok file tujuan.
Two-Way Merge Sort
External Sorting memanfaatkan algoritma Two-Way Merge Sort.
Hanya memanfaatkan 3 halaman memori utama, sedangkan halaman memori utama yng tersedia sangat banyak.
Pengurutan dilakukan dalam beberapa tahap.
Tahap pertama, halaman dalam file dibaca satu per satu, record didalamnya diurutkan dan halaman yang telah terurut ditulis kembali.
Pengurutan di dalam halaman dapat menggunakan algoritma pengurutan yang umum digunakan.
Pada tahap berikutnya, pasangan run dari output pada tahap sebelumnya akan dibaca dan digabungkan untuk menghasilkan run yang panjangnya 2 kali lipat sebelumnya.
Jika jumlah halaman dalam file input = 2k, untuk beberapa k, maka :
Tahap 0 diperoleh 2k run terurut masing-masing 1 halaman
Tahap 1 diperoleh 2k–1 run terurut masing-masing 2 halaman
Tahap 2 diperoleh 2k–2 run terurut masing-masing 4 halaman
Tahap k diperoleh 1 run 2k halaman terurut
External Merge Sort
Jika memori utama memiliki halaman buffer sebanyak B ruang buffer, maka untuk mengurutkan file yang besar yang memiliki N halaman, maka :
Tahap 0, baca B halaman dan urut secara internal, diperoleh run N / B untuk masing-masing B halaman (kecuali run terakhir yang mungkin berisi sedikit halaman).
Tahap i = 1, 2, …, baca (B – 1) halaman buffer untuk input dan gunakan sisa halaman untuk output, dengan demikian, telah dilakukan (B – 1) cara penggabungan dalam tiap tahap.
Jika ingin mengurutkan file yang memiliki 108 halaman dengan menggunakan buffer 5 halaman, maka :
Tahap 0 diperoleh 108 / 5 = 22 run terurut dengan masing-masing 5 halaman, kecuali run terakhir yang hanya 3 halaman.
Tahap 1 diperoleh 22 / 4 = 6 run terurut dengan masing-masing 20 halaman, kecuali run terakhir yang hanya 8 halaman.
Tahap 2 diperoleh 6 / 4 = 2 run terurut dengan 1 run 80 halaman dan sisanya 28 halaman.
Tahap 3 diperoleh 2 / 2 = 1 run dengan menggabungkan 2 run dari tahap 2 untuk menghasilkan file terurut.
0 Comments
