Download - Hashtable-dan-Vektor-Bit
Hash table / hash map
• Struktur data yang mengasosiasikan sebuah kunci (key) dengan sebuah nilai (value)
• Key biasanya adalah sebuah string, sedangkan nilai bisa apa saja (integer, string, dll)
• Hash table memungkinkan akses rata-rata O(1) dengan worst case O(n)
• Prinsipnya key diubah menjadi nilai integer yang menjadi indeks tabel
Hash function
• Fungsi yang memetakan suatu key menjadi sebuah integer
• Fungsi apa saja bisa dipilih untuk memetakan key menjadi nilai
• Pembahasan mengenai pemilihan fungsi di luar scope materi
• Secara sederhana, pilihlah fungsi yang secara intuitif mendistribusikan nilai
perfect hash function
• Fungsi hash yang bisa memetakan dengan tepat string yang berbeda ke nilai yang berbeda
abc
def
ghi
v1
v2
v3
f
perfect hash
• Secara praktis perfect hash hanya dapat diketahui jika semua key diketahui
• Umumnya untuk data yang tidak diupdate misalnya kamus
Fungsi hash String Java
{hasilnya perlu di-mod dengan indeks tabel}
function hash(s:string):integer;
var h, i:integer;begin
h = 0;
for i:=1 to length(s) h:=31*h + ord(s[1]);
hash:=h;
end;
Colission
• Karena fungsi hash sempurna sulit dicari, maka pasti akan terjadi tabrakan
• Hash suatu string s1 mungkin sama dengan string s2
• Jika terjadi tabrakan, maka apa yang harus dilakukan?
Chaining
• Setiap elemen tabel memiliki tabel
• Jika terjadi colission, maka masukkan ke elemen berikut dalam tabel
• Tidak efisien tanpa alokasi memori dinamik
0
1
2
A B
D E F
A
Bf
Open addressing
• Jika tabel posisi ke-i sudah dipakai, pindahkan ke posisi lain
• Linear probing: coba cari di posisi berikut secara linier i+1, i+2, dst sampai ada lokasi kosong
• quadratic probing: memakai fungsi kuadratik misalnya i+2, i+4, i+8, dst
• double hashing: hasil dari hash dihash lagi
Cuckoo Hashing
• Menggunakan 2 fungsi hash
• Setiap key memiliki 2 kemungkinan lokasi
• Jika mencoba insert ke posisi ‘A’, maka ‘A’ akan ditendang ke ‘B’ dan ‘B’ ke posisi kosong
• Jika mencoba insert ke posisi ‘H’ maka terjadi loop
Cryptographic hash
• Sekedar pengetahuan (kemungkinan besar tidak terpakai di IOI)
• Fungsi hash yang kebalikannya tidak bisa dicari
• Sulit mencari 2 atau lebih nilai S sehingga Hash(S)=F
• Kegunaan: verifikasi pesan, verifikasi password
Kegunaan hashing
• Rabin-Karp string search algorithm
• Bloom filter (akan dibahas bersama dengan bit vector)
• Pencarian data string dengan cepat (best case O(1) dan worst case O(n))
• Kadang lebih baik memakai Binary Search Tree
Rabin-Karp string search
• Cocok untuk pencarian banyak pola (sepanjang m) dalam satu string (sepanjang n)
• Average dan best case O(n), worst case O(mn)
• Ada algoritma lain dengan kompleksitas O(n), namun implementasinya lebih kompleks (Aho Corasick)
• Untuk pencarian satu string, masih banyak algoritma lain yang lebih efisien
naif
• 1 function NaiveSearch(string s[1..n], string sub[1..m]) • 2 for i from 1 to n • 3 for j from 1 to m • 4 if s[i+j-1] <> sub[j] • 5 jump to next iteration of outer loop • 6 return i • 7 return not found
RabinKarp v1•1 function RabinKarp(string s[1..n], string sub[1..m])• 2 hsub := hash(sub[1..m])• 3 hs := hash(s[1..m])• 4 for i from 1 to n• 5 if hs = hsub• 6 if s[i..i+m-1] = sub • 7 return i • 8 hs := hash(s[i+1..i+m]) • 9 return not found
Perhatikan bahwa baris 8 tidak efisien
Rolling hash
• Andaikan hash bisa diupdate dalam O(1), maka fungsi tersebut akan berjalan cepat
• Solusi: menggunakan rolling hash, nilai hash yang bisa diupdate dengan rumus tertentu berdasarkan karakter yang dibuang dan ditambahkan
• Contoh:
• s[i+1..i+m] = s[i..i+m-1] - s[i] + s[i+m]
Rolling hash yg lebih baik
• Menggunakan basis bilangan prima (misal 101), misal untuk hashing ‘ABC’
• h = ord(‘A’)*101*101+or(‘B’)*101 + ord(‘C’)
• Untuk mencari hash ‘BCD’, kurangkan h dengan ord(‘A’)*101, kalikan h dengan 101, tambahkan ord’(D)
• h’ = (h - ord(‘A’)*101*101)*101 + ord (‘D”)
Multi pattern search
•function RabinKarpSet(string s[1..n], set of string subs, m) { • set hsubs := emptySet • for each sub in subs • insert hash(sub[1..m]) into hsubs • hs := hash(s[1..m]) • for i from 1 to n • if hs ∈ hsubs • if s[i..i+m-1] = a substring with hash hs • return i • hs := hash(s[i+1..i+m]) • return not found • }
Vektor
• Struktur data list atau array satu dimensi
• Vektor bit: vektor yang elemennya adalah bit
• Di C++, Java, C#, vektor bit tersedia, di Pascal belum ada
Mengapa vektor bit?
• Hemat memori
• Satu variabel bisa menyimpan banyak bit
• Cepat (cache prosessor terbatas)
• Data yang masuk ke cache prosessor akan diproses lebih cepat
Manipulasi bit
• Menggunakan operasi boolean: or, and, xor, not
• Besar data: 1 byte: 8 bit
• 1 nibble : 4 bit
• Besar tipe data lain: sizeof(tipedata)*8
• Bit dihitung dari indeks ke-0
shr dan shl
• shr: shift right, semua bit digeser ke kanan
• Dapat digunakan untuk membagi dengan 2^n
• shl: shift left, semua bit digeser ke kiri
• Dapat digunakan untuk mengalikan dengan 2^n
test bit
• Menguji apakah bit-n bernilai 1 atau 0
• Cara: and-kan dengan suatu nilai yang bit ke-n bernilai 1, jika hasilnya >0 maka bit bernilai 1
• Contoh: apakah bit ke-2 bernilai 1?
• (b and (1 shl 2))>0
set bit
• Mengeset bit ke-n dalam suatu integer
• Cara: Or-kan nilai dengan nilai yang bit ke-n diset
• Mengeset bit ke-3 (bit dihitung dari bit 0):
• b or (1 shl 3)
unset bit
• Membuat bit ke-n dalam suatu integer menjadi 0
• Cara: and-kan dengan bit yang semua bitnya 1 kecuali bit ke-n
• Contoh: set bit ke-2 menjadi 0
• (b and (not (1 shl 2)))
vektor bit dgn array
• Contoh:
• var a: array [0..100] of integer;
• Bisa memuat 1600-3200 boolean (tergantung implementasi Pascal)
• Mengeset bit ke-n
• i = n div (sizeof(integer)*8)
• m = n mod (sizeof(integer)*8)
• Set bit: a[i] or (1 shl m)
Bloom filter
• Space efficient probabilistic data structure
• Hanya bisa menyimpan dan meng-query data, tidak bisa menghapus
• Digunakan untuk menentukan apakah data A ada pada struktur data B
• Jika A tidak ada di B, pasti mengembalikan false
• Jika A ada di B, mungkin mengembalikan true atau false (kemungkinan besar true)
• Biasanya digabung dengan struktur data lain, untuk memastikan apakah A ada di B
Cara kerja: insert
• Siapkan vektor bit V yang berisi n elemen
• Untuk memakai bloom filter, digunakan satu atau lebih fungsi hash yang berbeda yang mengembalikan nilai 1..n
• Untuk memasukkan data D, hash D, dan set V[hash(D)] menjadi 1
• Ulangi untuk setiap fungsi hash
Cara kerja: query• Untuk menentukan apakah data D ada pada
V:
• Jika V[hash(D)] bernilai 0, D pasti tidak ada di V
• Ulangi untuk fungsi hash berikutnya
• Jika semua fungsi hash mengembalikan nilai sedemikian hingga bit di D, diset kemungkinan D ada di A
Apa gunanya?
• Antivirus:
• Jika pola tertentu tidak ada, maka pasti file bersih dari virus
• Jika pola tertentu ada, maka periksa file dengan pemeriksaan yang lebih akurat
Latihan 1: Not That Kind of Tree
• Masukkan: N adalah jumlah baris, baris berikutnya adalah nama-nama pohon
• Jumlah pohon unik maks ada 10000 (10 ribu)
• Jumlah pohon keseluruhan maks ada 1000000 (1 juta)
• Nama pohon maksimum 100 karakter
• Keluaran: jumlah masing-masing pohon, terurut berdasarkan nama
Latihan 2: AntiVirus
• Diberikan sekumpulan pola virus (sebanyak N), tentukan apakah file bervirus (M File)
• N maksimum 10000
• M maksimum 1000000
• Panjang N dan M maksimum 100 karakter
• Satu file hanya terjangkit satu virus
Masukan dan keluaran
• Masukan:
• Bari pertama M dan N
• M baris pola virus
• N baris isi file
• Keluaran: string isi file yang diikuti dengan kata ‘BERVIRUS’ dan string virus jika file mengandung virus