Hashtable dan vektor bit

Yohanes Nugroho

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

worst hash function

• Fungsi hash yang mengembalikan nilai konstan

abc

def

ghi

f

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 Bit

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

Contoh

• Input:4pinusmanggapinuskelapa

• Output:kelapa 1mangga 1pinus 2

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

Contoh input dan output

• Input:2 3ABCINIITUBUKU INI MILIK SIAPAMERK ABC

• Output:BUKU INI MILIK SIAPA BERVIRUS INIMERK ABC BERVIRUS ABC