- HASH SEARCH -

Kelompok 3AMuhammad Ikhsan 24010312130047

Andika Putra Pratama 24010312140121

Dhemma Ratananjaya 24010312130122

Konsep Hash Search

• Metode penempatan dan pencarian Direct access

• Dapat ditemukan dengan sekali pemasukan terhadap tabel yang digunakan untuk menyimpan data

• Fungsi Hash (H): Fungsi untuk mengkonversi himpunan key (K) menjadi himpunan alamat (L). [ H (K) = L ]

Apa yang Dibahas??

• Dalam penempatan data, apabila dua buah data atau lebih dengan key yang berbeda, namun memiliki alamat hash yang sama, maka akan terjadi tabrakan (Collision).

• Solusi untuk mengatasi collision pada hash disebut Collision Resolution.

CLOSEHASH

OverflowLinear

Double

prologue- CLOSE HASH• LEARN THE BASIC, CLOSE HASH

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 Contoh:

“ L terdiri dari 10 alamat mulai dari index 0, penyimpanan data: 52, 69, 74 adalah.. ”

{H (K) = K mod H }H (52) = 52 mod 10 = 2H (69) = 69 mod 10 = 9H (74) = 74 mod 10 = 4

01

52------------ 23

74------------ 45678

69------------ 9

• REPRESENTASI CLOSE HASH

Linear Resolution

0 1

K mod 10 = 2 A 2D 3 K 4

5 6 7 8 9

Overflow 0 1

K mod 10= 2 A 2D 3 4 5 6 7 8 9

K

0 1 2 3 4

Sequential/Fungsi Hash

Double Hash

T1 T201

K mod 10 = 2 A B 2C D 3E K 4

56789

OPEN HASH

Linked List

Modification

prologue- OPEN HASH

• LEARN THE BASIC, OPEN HASH

Ingat fungsi HashIngat konsep Linear ResolutionHash pada Open Hash terdiri dari Hash Luar dan

Hash Dalam

Modification Open Hash

0 1 … … M-1

0 O1 O… O… O

N-1 O

Hash Dalam

Hash Luar

Linked List Open Hash

0 O O O

1 O O O O

…

…

N-1 O O

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.

SISTEM BERKAS Hash Search 14

Perfect Hash Function

• 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 NSize = length of String

SISTEM BERKAS Hash Search 15

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).

SISTEM BERKAS Hash Search 16

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.

SISTEM BERKAS Hash Search 17

(+) (-) CLOSE HASH & OPEN HASH• Close hash :

Kelebihan : Akses data lebih cepatKelemahan : Jumlah data terbatas

• Open hash :Kelebihan : Akses data lebih cepat, jumlah data tidak

dibatasiKelemahan : Waktu akses lebih lama karena

banyaknya pointer yang digunakan

PROBE

• Probe: suatu besaran yang menunjukkan tingkat efisiensi fungsi hash

TabelUkuran

DataanPerbandingJmlPROBE

.

TERIMA KASIH

But we HAVEN’T DONE yet

by: andika