Hash TableHash Table

22

TabelTabel

Tabel mempunyai beberapa Tabel mempunyai beberapa fields fields (tipe informasi)(tipe informasi) Buku telepon mempunyai beberapa Buku telepon mempunyai beberapa fieldfield diantaranya: diantaranya:

nama, alamat, nomor teleponnama, alamat, nomor telepon Tabel Tabel user accountuser account mempunyai mempunyai field field diantaranya id, diantaranya id,

password, dan nama folderpassword, dan nama folder Untuk menemukan data/Untuk menemukan data/entryentry yang kita butuhkan dari tabel, yang kita butuhkan dari tabel,

kita harus mengetahui nilai dari salah satu field(bukan kita harus mengetahui nilai dari salah satu field(bukan semuanya). Field tersebut biasanya disebut sebagai semuanya). Field tersebut biasanya disebut sebagai keykey KeyKey di buku telepon adalah nama di buku telepon adalah nama KeyKey di user account adalah di user account adalah id id

KeyKey idealnya harus bersifat unik yang berarti bahwa tidak idealnya harus bersifat unik yang berarti bahwa tidak ada isi dari ada isi dari keykey yang bernilai sama yang bernilai sama

33

Operasi tabelOperasi tabel

insertinsert: diberikan sebuah : diberikan sebuah keykey dan nilai, dan nilai, insert nilai dalam tabelinsert nilai dalam tabel

findfind: diberikan sebuah : diberikan sebuah keykey, temukan nilai , temukan nilai yang berhubungan dengan yang berhubungan dengan keykey

removeremove: diberikan sebuah : diberikan sebuah keykey,temukan ,temukan nilai yang berhubungan dengan nilai yang berhubungan dengan key key kemudian hapus nilai tersebutkemudian hapus nilai tersebut

getIteratorgetIterator: mengambalikan iterator,yang : mengambalikan iterator,yang memeriksa nilai satu demi satumemeriksa nilai satu demi satu

44

Bagaimana tabel harus Bagaimana tabel harus diimplementasikan?diimplementasikan?

Seberapa sering nilai di-Seberapa sering nilai di-insertinsert dan di- dan di-removeremove?? Berapa banyak jumlah Berapa banyak jumlah key key yang dipergunakan? yang dipergunakan? Bagaimana model Bagaimana model searchingsearching dari dari keykey??

Contoh: apakah pencarian dilakukan terhadap satu nilai Contoh: apakah pencarian dilakukan terhadap satu nilai keykey atau atau langsung dua nilai langsung dua nilai keykey

Apakah ukuran tabel cukup jika dimasukkan dalam memori?Apakah ukuran tabel cukup jika dimasukkan dalam memori? Sampai berapa lama tabel akan dipergunakan?Sampai berapa lama tabel akan dipergunakan?

Pilihan kita tentang bagaimana tabel sebaiknya direpresentasikan tergantung dari jawaban dari pertanyaan-pertanyaan dibawah ini

55

TableNode: TableNode: keykey dan dan entryentry

Untuk keperluan Untuk keperluan searching/searching/pencarian,sangat dianjurkan pencarian,sangat dianjurkan untuk menempatkan untuk menempatkan keykey dan dan entryentry di tempat yang di tempat yang terpisah (walaupun nilai dari terpisah (walaupun nilai dari keykey mungkin ada di dalam mungkin ada di dalam entryentry))

“Smith” “Smith”, “124 Hawkers Lane”, “9675846”

“Yeo” “Yeo”, “1 Apple Crescent”, “0044 1970 622455”

key entry

TableNode

66

Implementasi Tabel 1:Implementasi Tabel 1:unsorted sequential arrayunsorted sequential array

Array dimana TableNodes disimpan Array dimana TableNodes disimpan tidak berurutantidak berurutan

insertinsert: ditambah di bagian paling : ditambah di bagian paling belakang array/array yang belakang array/array yang terakhir;O(1)terakhir;O(1)

findfind: Pencarian dilakukan pada : Pencarian dilakukan pada seluruh key satu kali setiap saat, ada seluruh key satu kali setiap saat, ada kemungkinan seluruh kemungkinan seluruh keykey dikunjungi; dikunjungi; O(O(nn))

removeremove: temukan node+hapus node+ : temukan node+hapus node+ gantikan node yang telah dihapus gantikan node yang telah dihapus dengan node yang terakhir; O(dengan node yang terakhir; O(nn))

0

…

key entry

1

23

and so on

77

Implementasi Tabel 2:Implementasi Tabel 2:sorted sequential arraysorted sequential array

Array dimana TableNodes Array dimana TableNodes disimpan berurut berdasarkan keydisimpan berurut berdasarkan key

insertinsert:ditambah di tempat sesuai :ditambah di tempat sesuai urutan dari key;O(n)urutan dari key;O(n)

findfind: Pencarian dilakukan dengan : Pencarian dilakukan dengan menggunakan algoritma binary menggunakan algoritma binary search karena key tersusun search karena key tersusun berurut; O(berurut; O(log nlog n))

removeremove: temukan node+hapus : temukan node+hapus node+semua node yang terletak di node+semua node yang terletak di bawah node yang dihapus bawah node yang dihapus dinaikkan satu tingkat; O(dinaikkan satu tingkat; O(nn))

0

…

key entry

1

23

and so on

88

Implementasi Tabel 3:Implementasi Tabel 3:linked list (unsorted or sorted)linked list (unsorted or sorted)

TableNodes disimpan berurutanTableNodes disimpan berurutan insertinsert: ditambah di urutan paling : ditambah di urutan paling

depan; O(1) ataudepan; O(1) atau O(n) O(n) untuk untuk list list yang terurutyang terurut

findfind: cari ke seluruh : cari ke seluruh keykey satu kali satu kali setiap saat; O(setiap saat; O(nn) dan masih ) dan masih O(n) O(n) untuk list yang terurutuntuk list yang terurut

removeremove: temukan node+ hapus : temukan node+ hapus node menggunakan pemindahan node menggunakan pemindahan pointer; O(pointer; O(nn))

key entry

and so on

99

Implementasi Tabel 4:Implementasi Tabel 4:AVL treeAVL tree

AVL tree, disusun terurut AVL tree, disusun terurut berdasarkan berdasarkan keykey

insertinsert: ditambah berdasarkan urutan : ditambah berdasarkan urutan key; O(log key; O(log nn))

findfind: menemukan : menemukan keykey; O(log ; O(log nn)) removeremove: temukan node+hapus node; : temukan node+hapus node;

O(log O(log nn))

key entry

key entry key entry

key entry

and so onO(log n) is very good…

…but O(1) would be even better!

1010

Suatu array dimana TableNodes Suatu array dimana TableNodes tidak disimpan secara berurutan. tidak disimpan secara berurutan. Posisi penyimpanan dihitung Posisi penyimpanan dihitung berdasarkan berdasarkan keykey dan dan hash hash functionfunction

Hashed keyHashed key: Hasil dari : Hasil dari menerapkan suatu menerapkan suatu hash functionhash function pada pada keykey

Key Key dandan entry entry tersebar di seluruh tersebar di seluruh arrayarray

Implementasi Tabel 5:Implementasi Tabel 5:hashinghashing

key entry

Key hash function

array index

4

10

123

1111

insertinsert: hitung alamat lokasi : hitung alamat lokasi penyimpanan, insert TableNode; penyimpanan, insert TableNode; O(1)O(1)

findfind: hitung alamat lokasi : hitung alamat lokasi penyimpanan, masukkan penyimpanan, masukkan entryentry ke tabel ; O(1)ke tabel ; O(1)

removeremove: hitung alamat lokasi : hitung alamat lokasi penyimpanan,ubah nilai di penyimpanan,ubah nilai di dalam alamat tersebut menjadi dalam alamat tersebut menjadi null; O(1)null; O(1)

Implementation 5:Implementation 5:hashinghashing

key entry

4

10

123

All are O(1) !

1212

Contoh Hashing : Contoh Hashing : Toko BuahToko Buah

10 detail stok buah, 10 10 detail stok buah, 10 posisiposisi tabel tabel Nomor stok antara 0-1000Nomor stok antara 0-1000 Gunakan rumus Gunakan rumus hash functionhash function: nomor stok/ : nomor stok/

100100 Bagaimana jika kita memasukkan nomor Bagaimana jika kita memasukkan nomor

stok350?stok350? Position 3 sudah terisi: terjadi Position 3 sudah terisi: terjadi collisioncollision

Collision resolution strategyCollision resolution strategy: insert di lokasi : insert di lokasi sesudahnya yang masih kosong (metode sesudahnya yang masih kosong (metode ini dinamakan ini dinamakan linear probinglinear probing))

Diberikan nomor stok lagi, temukan stok Diberikan nomor stok lagi, temukan stok dengan menggunakan dengan menggunakan hash functionhash function, dan , dan gunakan gunakan collision resolution strategycollision resolution strategy jika jika dibutuhkandibutuhkan

key entry01

2

3

4

5

6

7

8

9

85 85, apples

462 462, pears

912 912, papaya

323 323, guava

350 350, oranges

1313

3 Faktor yang Mempengaruhi 3 Faktor yang Mempengaruhi Performansi Performansi hashinghashing

Hash functionHash function Idealnya Idealnya hash functionhash function harus mendistribusikan seluruh harus mendistribusikan seluruh keykey dan dan entryentry secara secara

merata ke seluruh tabelmerata ke seluruh tabel Hash function harus meminimalisir terjadinya Hash function harus meminimalisir terjadinya collisioncollision, dimana isi dari alamat , dimana isi dari alamat

yang diberikan oleh yang diberikan oleh hash functionhash function telah terisi telah terisi Collision resolution strategyCollision resolution strategy

Separate chainingSeparate chaining: merangkaikan beberapa : merangkaikan beberapa key/entrykey/entry di posisi masing-masing di posisi masing-masing Open addressingOpen addressing: menyimpan : menyimpan key/entrykey/entry di suatu lokasi yang berbeda di suatu lokasi yang berbeda

Ukuran tabelUkuran tabel Terlalu besar akan membuang memori, terlalu kecil akan memunculkan Terlalu besar akan membuang memori, terlalu kecil akan memunculkan

banyak banyak collisioncollision dan pada akhirnya terpaksa harus dilakukan dan pada akhirnya terpaksa harus dilakukan rehashingrehashing (mencopy data ke tabel yang lebih besar)(mencopy data ke tabel yang lebih besar)

Memungkinkan diterapkan Memungkinkan diterapkan hash function hash function pada tabel tersebutpada tabel tersebut

1414

Memilih Memilih hash functionhash function::MMengubah engubah keykey Menjadi Posisi Tabel Menjadi Posisi Tabel

TruncationTruncation Abaikan sebagian nilai dari Abaikan sebagian nilai dari key key dan gunakandan gunakan sebagian yang lain sebagian yang lain

sebagai index dari array (mengkonversi bagian sebagai index dari array (mengkonversi bagian keykey yang non-numeric) yang non-numeric) Teknik yang cepat dan sesuai untuk pendistribusian yang merata ke Teknik yang cepat dan sesuai untuk pendistribusian yang merata ke

seluruh tabelseluruh tabel FoldingFolding

Memisah beberapa kunci menjadi beberapa bagian dan kombinasikan Memisah beberapa kunci menjadi beberapa bagian dan kombinasikan dengan cara yang tepatdengan cara yang tepat

Tidak seperti Tidak seperti truncationtruncation,cara ,cara FoldingFolding ini menggunakan seluruh nilai dari ini menggunakan seluruh nilai dari keykey

Modular arithmetic (digunakan juga oleh truncation & folding)Modular arithmetic (digunakan juga oleh truncation & folding) Untuk menjaga agar posisi yang dihitung benar-benar ada dalam Untuk menjaga agar posisi yang dihitung benar-benar ada dalam

tabel,tabel,devidedevide/bagi posisi dengan ukuran dari tabel, dan gunakan sisanya /bagi posisi dengan ukuran dari tabel, dan gunakan sisanya sebagai posisi yang barusebagai posisi yang baru

1515

Contoh Contoh hash functionshash functions (1) (1)

TruncationTruncation: siswa mempunyai NIM dengan 8 digit nilai, : siswa mempunyai NIM dengan 8 digit nilai, gunakan 3 digit yang terakhir sebagai posisi tabelgunakan 3 digit yang terakhir sebagai posisi tabel Contoh: NIM 05560078Contoh: NIM 05560078 menjadi 078 menjadi 078

FoldingFolding: Bagi nomor 8 digit menjadi nomor 3 : Bagi nomor 8 digit menjadi nomor 3 digit,kemudian tambahkandigit,kemudian tambahkan Contoh: 05560078Contoh: 05560078 menjadi 055 + 600 + 78 = 733 menjadi 055 + 600 + 78 = 733

Modular arithmeticModular arithmetic: Jika ukuran tabel 1000,untuk : Jika ukuran tabel 1000,untuk memastikan posisi yang dihitung ada di dalam range dari memastikan posisi yang dihitung ada di dalam range dari tabel maka lakukan operasi modulo pada posisi tabeltabel maka lakukan operasi modulo pada posisi tabel Contoh : 733 mod 1000 = 733Contoh : 733 mod 1000 = 733 Contoh : 1250 mod 1000=250Contoh : 1250 mod 1000=250

1616

Contoh Contoh hash functionshash functions (2) (2)

Gunakan nomor telepon sebagai Gunakan nomor telepon sebagai keykey Kode area tidak random, maka tidak akan mendistribusikan Kode area tidak random, maka tidak akan mendistribusikan

secara merata penyebaran key/entry. secara merata penyebaran key/entry. 3 nomor digit terakhir lebih random sehingga lebih 3 nomor digit terakhir lebih random sehingga lebih

memungkinkan untuk digunakan sebagai penentu posisi pada memungkinkan untuk digunakan sebagai penentu posisi pada tabeltabel

Menggunakan nama sebagai Menggunakan nama sebagai keykey Gunakan Gunakan full namefull name(nama keseluruhan) daripada (nama keseluruhan) daripada surnamesurname (nama (nama

panggilan)panggilan) Koversikan setiap karakter dengan suatu nomor (contoh: a = 1, Koversikan setiap karakter dengan suatu nomor (contoh: a = 1,

b = 2)b = 2) Jumlahkan seluruh nomor. Jumlahkan seluruh nomor.

1717

Memilih Ukuran Tabel untuk Memilih Ukuran Tabel untuk Meminimalisir Meminimalisir CollisionCollision

Karena elemen dari tabel terus meningkat, sejatinya jumlah Karena elemen dari tabel terus meningkat, sejatinya jumlah collisioncollision akan terus meningkat, oleh karena itu ukuran tabel harus akan terus meningkat, oleh karena itu ukuran tabel harus diperhitungkan sebaik mungkindiperhitungkan sebaik mungkin

Jika ukuran tabel 100 dan seluruh nilai Jika ukuran tabel 100 dan seluruh nilai hashed keyhashed key dibagi dengan dibagi dengan 10, maka akan terjadi banyak 10, maka akan terjadi banyak collisioncollision Tidak baik jika ukuran tabel dibentuk dari nomor integer ukuran Tidak baik jika ukuran tabel dibentuk dari nomor integer ukuran

kecil seperti 2 atau 10kecil seperti 2 atau 10 Umumnya Umumnya collisioncollision akan sering terjadi jika: akan sering terjadi jika:

greatest common divisor (hashed keys, table size) > 1greatest common divisor (hashed keys, table size) > 1 Oleh karena itu ukuran tabel sebaiknya adalah bilangan prima (gcd = Oleh karena itu ukuran tabel sebaiknya adalah bilangan prima (gcd =

1)1)Bagaimanapun collision masih mungkin terjadi,oleh karena itu kita membutuhkan collision resolution strategy

1818

Collision resolution:Collision resolution:open addressing (1)open addressing (1)

Linear probingLinear probing: menjumlahkan satu setiap saat [mod dengan : menjumlahkan satu setiap saat [mod dengan ukuran tabel]ukuran tabel]

Quadratic probingQuadratic probing: dari posisi aslinya, tambahkan 1, 4, 9, 16,…: dari posisi aslinya, tambahkan 1, 4, 9, 16,…

Probing: Jika posisi tabel yang diberikan oleh hashed key telah terisi, naikkan/jumlahkan posisi sejumlah tertentu,sampai bertemu dengan posisi tabel yang nilai di dalamnya kosong

Gunakan collision resolution strategy jika melakukan insert dan find (pastikan bahwa kunci yang dicari dan kunci yang didapat cocok)

double hash: hasil dari linear probing hasil dari hash function lain Dengan open addressing,ukuran tabel harus digandakan sesuai dengan

elemen nomor yang diharapkan

1919

Collision resolution:Collision resolution:open addressing (2)open addressing (2)

Jika isi tabel banyak yang kosong dan banyak terjadi cJika isi tabel banyak yang kosong dan banyak terjadi collisionollision, , metode metode linear probinglinear probing akan menimbulkan akan menimbulkan clustercluster/pengelompokan /pengelompokan key/entrykey/entry Hal ini akan meningkatkan waktu untuk melakukan Hal ini akan meningkatkan waktu untuk melakukan insertinsert dan dan findfind

1 2 3 4 5 6 7 8

Jika suatu tabel berukuran Jika suatu tabel berukuran nn dan tabel tersebut kosong,maka dan tabel tersebut kosong,maka kemungkinan kemungkinan entry entry masuk ke posisi tertentu dalam tabel adalahmasuk ke posisi tertentu dalam tabel adalah 1/1/nn

Dalam diagram, kemungkinan posisi 2 terisi sesudahnya adalah 2/Dalam diagram, kemungkinan posisi 2 terisi sesudahnya adalah 2/nn Jika posisi 2 sudah terisi,kemungkinan posisi 4 terisi sesudahnya Jika posisi 2 sudah terisi,kemungkinan posisi 4 terisi sesudahnya

adalah 4/adalah 4/nn dan kemudian posisi 7 adalah 7/ dan kemudian posisi 7 adalah 7/nn

2020

Collision resolution:Collision resolution:open addressing (3)open addressing (3)

Key/entry Key/entry yang kosong menandai akhir dari yang kosong menandai akhir dari clustercluster dan dapat digunakan untuk mengakhiri dan dapat digunakan untuk mengakhiri operasi operasi findfind

Oleh karena itu jika kita menghapus Oleh karena itu jika kita menghapus entryentry dalam dalam cluster cluster kita tidak boleh mengosongkan isinyakita tidak boleh mengosongkan isinya

Agar Agar probingprobing bisa berjalan terus, bisa berjalan terus,entry entry yang yang dihapus harus ditandai dengan ‘dihapus tetapi dihapus harus ditandai dengan ‘dihapus tetapi clustercluster berlanjut terus’ berlanjut terus’

2121

Collision resolution:Collision resolution:open addressing (4)open addressing (4)

Quadratic probingQuadratic probing adalah solusi dari masalah adalah solusi dari masalah clusteringclustering Linear probingLinear probing menambah 1, 2, 3, dst. pada menambah 1, 2, 3, dst. pada original hashed keyoriginal hashed key Quadratic probingQuadratic probing menambah 1 menambah 122, 2, 222, 3, 322 dst. pada dst. pada original original

hashed keyhashed key Bagaimanapun,jika Bagaimanapun,jika linear probinglinear probing memastikan bahwa semua posisi memastikan bahwa semua posisi

yang kosong akan diperiksa tidak halnya dengan metode yang kosong akan diperiksa tidak halnya dengan metode quadratic quadratic probing probing Contoh: ukuran tabel 16 dan Contoh: ukuran tabel 16 dan original hashed keyoriginal hashed key 3 memberikan 3 memberikan

sekuen : 3, 4, 7, 12, 3, 12, 7, 4…sekuen : 3, 4, 7, 12, 3, 12, 7, 4… Umumnya dengan menggunakan Umumnya dengan menggunakan quadratic probingquadratic probing, proses , proses insertinsert

akan tidak mungkin dilakukan jika tabel sudah lebih dari setengah akan tidak mungkin dilakukan jika tabel sudah lebih dari setengah penuhpenuh Jika hal ini terjadi perlu dilakukan Jika hal ini terjadi perlu dilakukan rehashrehash

2222

Collision resolution: chainingCollision resolution: chaining

Setiap posisi tabel adalah Setiap posisi tabel adalah linked listlinked list Tambahkan Tambahkan keykey and and entryentry dimanapun dimanapun

dalam list (lebih mudah dari depan)dalam list (lebih mudah dari depan) Keunggulan dibandingkan Keunggulan dibandingkan open open

addressingaddressing:: Proses Proses insertinsert dan dan removeremove lebih lebih

sederhanasederhana Ukuran Array bukan batasan (tetapi Ukuran Array bukan batasan (tetapi

harus tetap meminimalisir harus tetap meminimalisir collisioncollision: buat : buat ukuran tabel sesuai dengan jumlah ukuran tabel sesuai dengan jumlah keykey dan dan entryentry yang diharapkan) yang diharapkan)

Kerugian:Kerugian: Overhead pada memory tinggi jika Overhead pada memory tinggi jika

jumlah entry sedikitjumlah entry sedikit

4

10

123

key entry key entry

key entry key entry

key entry

No need to change position!

2323

RehashingRehashing: : memperbesar ukuran tabel memperbesar ukuran tabel

Untuk me-Untuk me-rehashrehash:: Buat tabel baru dengan ukuran dua kali lebih besar dari ukuran semula Buat tabel baru dengan ukuran dua kali lebih besar dari ukuran semula

(sesuaikan hingga akhirnya ukuran tabel adalah bilangan prima)(sesuaikan hingga akhirnya ukuran tabel adalah bilangan prima) Transfer semua Transfer semua entryentry pada tabel yang lama ke tabel yang baru,dengan pada tabel yang lama ke tabel yang baru,dengan

melakukan perhitungan ulang pada posisi tiap melakukan perhitungan ulang pada posisi tiap entryentry (menggunakan (menggunakan hash hash functionfunction))

Kapan kita harus me-Kapan kita harus me-rehashrehash?? Jika tabel sudah penuhJika tabel sudah penuh Dengan menggunakan metode Dengan menggunakan metode quadratic probingquadratic probing, jika tabel sudah setengah , jika tabel sudah setengah

penuh, maka proses penuh, maka proses insertinsert akan gagal akan gagal Mengapa ukuran tabel baru harus dua kali ukuran semula?Mengapa ukuran tabel baru harus dua kali ukuran semula?

Jika Jika nn adalah nomor dari elemen tabel, seharusnya telah terjadi n/2 proses insert adalah nomor dari elemen tabel, seharusnya telah terjadi n/2 proses insert sebelum dilakukan rehash (jika rehashing dilakukan karena tabel penuh)sebelum dilakukan rehash (jika rehashing dilakukan karena tabel penuh)

Jadi dengan menambah ukuran tabel dengan 2Jadi dengan menambah ukuran tabel dengan 2nn, harga yang konstan akan , harga yang konstan akan didapatkan pada tiap proses didapatkan pada tiap proses insertinsert