Searching : Hash Search

Beberapa metode searching (pencarian) :
1. Hash Search
2. Binary Search → akan dibahas di postingan berikutnya.

Hash Search :
#  Metode penempatan dan pencarian data secara langsung (direct access)
#  Konversi himpunan key (K) menjadi himpunan alamat (L) => H (K) = L

2 jenis metode hash search :
#  Close hash
ukuran tabel terbatas, jumlah data terbatas.
#  Open hash
ukuran tabel terbatas, jumlah data tidak terbatas.
karena memanfaatkan linked list untuk menempatkan data.

1. Close Hash

#  Index tabel : 0 sampai dengan (N - 1)
H (K) = K mod N
#  Index tabel : 1 sampai dengan N
H (K) = (K mod N) + 1

Contoh :
L = 100 alamat
Simpan data = 10347, 34212
H (10347) = 10347 mod 100 = 47
H (34212) = 34212 mod 100 = 12



Collision Resolution
Solusi untuk mengatasi tabrakan (collision) pada hash.
Tabrakan terjadi apabila terdapat 2 data atau lebih yang berbeda tetapi memiliki alamat hash yang sama.
Strategi collision resolution :
#  Linier resolution
#  Overflow
#  Double hash

2. Open Hash / Penggandengan / Chaining

Open hash : salah satu strategi untuk mengatasi tabrakan (collision).
Bentuk open hash :
#  Modification open hash
Terdiri dari hash luar (tabel alamat hash) dan hash dalam (untuk menyimpan data).
Data yang tersimpan 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.

Probe (Rata-rata Pencarian)
Digunakan  untuk menentukan besar efisiensi fungsi hash dengan mengukur banyaknya perbandingan key yang diperlukan untuk mencari alamat data.





Soal 1 (Materi Kuliah Sistem Berkas Ilmu Komputer UNDIP)

Diketahui data dengan key 25, 76, 63, 98, 58, 19.
1. Tempatkan data tersebut ke dalam close hash dengan ukuran tabel = 5 dengan penanganan collision :
a) Linier resolution
b) Overflow dengan ukuran overflow = 3 dan penempatan overflow dengan fungsi hash
c) Double hash
2. Tempatkan data tersebut ke dalam open hash dengan :
a) Modification open hash dengan ukuran hash luar = 3 dan hash dalam = 4. Kemudian sisipkan key 34
b) Linked list open hash dengan ukuran tabel = 3
Kemudian tentukan probe !

Jawaban
1a) 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}

25	0
76	1
58	2
63	3
98	4

K	25	76	63	98	58
T	1	1	1	2	5

Probe = ( 1 + 1 + 1 + 2 + 5) / 5 = 2

1b) 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
Tabel Utama

25	0
76	1
	2
63	3
19	4

Overflow

	58	98
0	1	2

K	25	76	63	98	58	19
T	1	1	1	2	2	1

Probe = ( 1 + 1 + 1+ 2 + 2 + 1) / 5 = 1,6

1c) 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 )

K	25	76	63	98	58	19
T	1	1	1	1	2	1

Probe = ( 1 + 1 + 1 + 1 + 2 + 1 ) / 5 = 1,4

2a) 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

Sisipkan key 34 :

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 ) = ( 4 + 1 ) mod 4 = 1

Hluar (34) = ( 1 + 1 ) mod 3 = 2

    Hdalam ( 34 ) = 34 mod 4 = 2

    Hdalam ( 34 ) = ( 2 + 1 ) mod 4 = 3

K	25	76	63	98	58	19	34
T	1	1	1	1	1	1	6

Probe = ( 1 + 1 + 1 + 1 + 1 + 1 + 6 ) / 4 = 3

2b) 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

K	25	76	63	98	58	19
T	1	2	1	1	3	4

Probe = ( 1 + 2 + 1 + 1 + 3 + 4 ) / 6 = 2