Welcome to fibonacciku so kali ini kita akan ngeembahas tentang hashing chaining yang mana hashing chaining itu adalah metode dari Open hashing jadi metode ini adalah kita ingin menghindari Collision atau sebuah tabrakan nih tabrakan itu apa kalau Collision itu ya jadi misalkan kita mau masukin elemen elemen di key Space ini ke Hash table nanti kalau misalkan ada dua elemen ya salah contohnya aja ada dua elemen kita masukkan k Stable dan lalu dua elemen itu masuk ke indeks yang sama nih jadi kan dia bakal tabrakan ya Oleh karena itu itu disebutnya adalah colollision dan hashing chaining ini adalah solusinya untuk menghindari colision itu dan lalu untuk hashing chaining ini aku nanti akan menjelaskan ya tentang insertnya memasukkan elemen ke dalam hashing ini dan lalu kita mencari elemennya itu ya di hashing chaining ini dan lalu kita menghapus dan lalu tentunya juga aku akanakukan analisa ya di hashing chaining ini dan lalu Coba kita lihat perhatikan untuk Hash ini kita punya Hash table yang mana besarannya adalah 10 ya di sini m = 10 Coba kita buat dulu fungsi hashing-nya ya untuk di hashing chaining ini karena kita tahu besarannya adalah 10 ya maka di sini fungsi hashing-nya bisa kita tulis adalah sama dengan x modulo 10 karena di sini besaran has table-nya adalah 10 ya maka di sini modulo 10 dan lalu Coba kita langsung aja Insert elemennya ya yang ada di keypace ini kita masukkan ke Hash table di sini ada 2 ya 2 modulo 10 = 2 ya maka 2 ini Kita masukin ke indeks 2 perhatikan karena di sini kita memakai chaining Kita sebenarnya enggak masukin di bagian sini tapi kita taruh di link list jadi di sini kita akan buat notes ya Yang mana dia adalah linklist sebenarnya Dan kita taruh dua di sini Jadi sebenarnya di hashing chaining ini si Hash table Ini adalah sebuah array pointer karena di sini si indeks 2 dia ngpoint nih dia ngpointer ke link list ini jadi si has table itu adalah untuk hasing chaining ini ya array dari pointer yang mana pointer itu dia ngpoint ke link list ya itu di sini ya link list atau sebenarnya bisa kita sebut juga has table ini Untuk chaining dia adalah array dari chain atau rantai ya Atau bisa kita sebut juga array dari Link list jadi kayak gitu untuk yang elemen dua ya Coba kita Masukin elemen-elemen yang lain ya di sini ada l maka kita masukin ke indeks 5 masukin ke indek 5 kita buat ngepoin dan di sini Kita masukin dan selanjutnya ada 12 ya 12 modul 10 adalah sama 2 nih dia ke indeks 2 sama maka di sini kita lihat ya si not ini dia bakal ngepoin ke1 sini 12 Nah selanjutnya di sini ada 25 ya dia masuk ke indeks 5 maka di sini dia ngepoin lagi ke not 25 dan selanjutnya ada 9 9 modul 10 adalah ke indek 9 ya kita di sini elemen 9 masuk ke indek 9 dan Lalu ada elemen 8 8 modulo 10 adalah 8 ya maka dia ke indeks 8 Kita masukin ke indeks 8 dan selanjutnya ada du 9 29 modulus 10 adalah ama 9 maka dia masuk ke indeks 9 juga nih maka di sini kita ngpoint 29 dan selanjutnya ada 122 122 modulus 10 adalah sama dengan 2 ya masuk ke indeks 2 maka di [Musik] sini 122 kita lihat di sini kan karena elemen-elemen yang kita masukin tuh selalu lebih besar ya jadinya kita taruh di yang paling kanan sebenarnya kalau nanti ada elemen yang lebih kecil ya Daripada misalkan aku masukin yang lebih kecil daripada dua nih Maka nanti kita harus ngearrange nih kita harus selalu berurutan nih posisinya jadi kayak gitu dan selanjutnya di sini ada elemen 1 ya 1 modul 10 adalah sama 1 Kita masukin ke indeks 1 di sini kita buat linklist-nya sini satu ya dan selanjutnya terakhir ada 10 10 modulnya 10 adalah sama 0 kita taruh di indeks 0 dia ngpoin juga nih ke 10 jadi kayak gitu untuk Insert gampang ya kita tinggal pakai si fungsi hhing ini buat menentukan ya Di mana kita taruh elemen itu di has table dan lalu tinggal kita buat aja linklist-nya dan lalu kalau kita perhatikan di sini kan besaran Hash table-nya adalah 10 ya tapi sebenarnya untuk hashing chaining ini kita enggak punya limit kita mau masukin berapapun Elemen Ke hasabin itu bisa karena kita bakal punya chaining jadi kita bisa masukkan elemen berapap pun ke has table dan dia enggak akan punya limit bisa berapap pun banyaknya masukin ke has table ini Jadi sebenarnya si besaran 10 ini enggak begitu berpengaruh ya untuk di hashing chaining ini jadi itu untuk Insert dan lalu kita coba mencari elemen yang ada di Hash table ini untuk di hashing chaining ya caranya untuk mencari elemen adalah contohnya elemen di sini aku Contohkan aja 122 Kita masukin si 122 ini ke fungsi hashing dulu nih maka kita dapat indek 2 ya dari indeks 2 ini kita cari 122 yang pertama kita lihat dua bukan ya maka kita terus ke kanan dan dia bukan juga dan lalu kita ke kanan lagi dan kita ketemu maka di sini 122 ini menggunakan tiga kali perbandingan ya tadi yang pertama di 2 yang kedua adalah di 12 yang ketiga adalah di 122 jadi kita butuh tiga kali perbandingan dan lalu contohnya lagi adalah 5 nih kita mau mencari 5 maka si 5 ini Kita masukin ke fungsi hasing ya 5 modul 10 kita dapat indeks 5 dan kita cari di perbandingan pertama kita langsung ketemu nih lima Maka langsung stop kita enggak perlu cari lagi karena udah ketemu ya dan di sini kita cuma perlu satu kali perbandingan dan lalu contoh aja Aku mau mencari elemen 30 ya walaupun di sini enggak ada tapi aku pengin cari elemen 30 nih 30 modulus 10 adalah 0 ya maka kita cari ke indeks 0 se kita lihat di bandingan pertama 10 dia bukan 30 ya dan lalu dia enggak punya elemen lagi selanjutnya maka kita tidak ketemu ya kan maka kita langsung stop jadi untuk mencari kita simpel sebenarnya mirip-mirip kayak Insert sih sebenarnya ya Kita masukin aja dulu elemennya ke fungsi hashing dan lalu kita tinggal cari elemennya di linklist dan lalu coba aku pengin analisa tentang di hashing chaining ini ya contoh aja nih ya misalkan aku punya jumlah elemennya adalah contoh aja ya di sini adalah n = 100 dan lalu kita tahu besaran si h tabel-nya itu adalah di sini 10 nah kalau di hashing ini kita memiliki satu istilah namanya adalah loading vekor namanya adalah loading vektor dan loading vektor ini biasanya kita tulis dengan lambang lambda atau Alfa jadi kita tulis Alfa dan loading vektor ini Kalau di hashing adalah sama dengan n Dib size atau dalam kasus ini ya dia adalah sama dengan 10 Kalau kamu perhatikan di data struktur yang lain Biasanya kita hanya perlu memakai jumlah n-nya jumlah elemen dalam mencari kompleksitas ya kan tapi di ini unik kita perlu loading vortuk menentukan kompleksitasnya jadi kita searching ya kita searching elemen kita kan tadi memakai fungsi hing ya maka kita memakai satu kompleksitas nih Big O dari 1 Tapi karena kita perlu loading vektor maka di sini 1 + Alfa maka kompleksitasnya untuk mencari elemen di hashing chaning ini adalah Big O dari 1 dambah Alfa dan mungkin aku akan memberikan juga yang lebih spesifik ya untuk mencari elemen Bagaimana kalau misalkan kita mencari elemennya itu sukses dan tidak sukses tadi kan aku kasih contoh ya kalau misalkan kita ketemu elemennya atau tidak ketemu nih kita cari average case-nya kita cari rata-ratanya Coba di sini kita Aku pengin tulis average aku tulis di atas ya average successers nih successor-nya karena kita mencari average dan successor kita harus tahu di sini kita lihat di link list-nya ya besaran si link list-nya itu adalah sebenarnya kita harus uniform distributif atau kita berasumsi ya jadi besaran ininya itu setiap indeksnya adalah si loading vektornya itu adalah si 10 kalau misalkan kita punya setiap indeksnya loading vektornya itu adalah 10 maka sebenarnya fungsi hashing ini sangat bagus jadi coba kita fokus dulu ke average successors-nya ya di sini kita lihat tadi kan kita tahu kalau misalkan kita mau searching kita harus masukin ke fungsi hashing dulu ya maka di sini T atau time ya di sini aku anggap di sini t-nya adalah Time adalah 1 ya kan dan lalu ditambah tadi kan aku bilang kita tinggal ditambah Alfa ya Tapi karena kita ingin mencari average-nya maka di sini kita bagi dua karena kan tadi kalau misalkan kita langsung ketemu kita cuma satu kali perbandingan Ya tapi kalau misalkan elemennya itu di paling terakhir dia harus pakai semua loading vektornya maka average-nya atau rata-ratanya tinggal kita bagi dua aja jadi ini adalah average successor-nya ya untuk di hashing chaining ini dan lalu kalau misalkan kita ingin mencari average untuk unsukses atau tidak sukses ya kita gampang aja nih karena kita sebenarnya kalau misalkan enggak sukses ya kita harus selalu membandingkan sampai akhir maka di sini bisa kita langsung tulis saja 1 + alfha untuk average andsuccess search-nya ya jadi kayak gitu untuk average successors dan average unsuccessors-nya ya untuk hashing chaining ini adalah analisanya dan tadi aku juga berbicara tentang loading Vector ini harus uniform distribution atau misalkan atau sebenarnya itu disebut juga kita beranggapan si loading vekor ini adalah setiap si indeksnya adalah 10 jadi nanti nih ya besaran si linklist-nya seap indeksnya itu adalah 10 tapi misalkan aku pengin masukin elemen ya contoh aja aku pengin masukin di sini elemen 5 25 terus ada 35 75 85 95 kalau kamu perhatikan ya kita memakai fungsi h-nya kan x modulo 10 ya kalau kamu perhatikan semua elemen ini akan masuk ke indeks 5 nih dia bakal masuk ke indeks 5 bayangkan kalau elemennya sangat banyak maka ide dari si loading Vector ini ya Yang mana kita harus yang mana kita harus Balance atau uniform distributive terhadap semua indeksnya ya jadi enggak sesuai sama idenya kita enggak akan punya loading vector yang sesuai seperti ini maka Siapa yang bertanggung jawab supaya si loading vektor ini itu sesuai yang bertanggung jawab adalah si programmernya yang menulis si kodingan ini dan si programmer itu harus menentukan fungsi hashing yang sesuainya supaya kita mendapatkan loading vor yang baik yang baik itu adalah kita mendapatkan uniform si alfanya itu harus n per size-nya besaran si h table maka Gimana caranya si programmer itu biar tahu menentukan fungsiing maka si programmer harus tahu data yang dia olah kayak gimana kita gak mungkin kan tahu solusi tanpa kita tahu data yang kita olah Nah jadi itulah tanggung jawabnya dari si programmer harus menentukan diodingannya ya si hashing yang sesuai supaya kita mendapatkan loading Vector yang uniform distributif kayak gitu Jadi itu analisanya untuk di searching elementen ya di hashing chaining ini dan lalu untuk menghapus sebenarnya simpel aja Dan kalau menghapus Kita sebenarnya selalu akan memakai fungsi hing ini ya karena kita kan harus mencari juga si elemen itu kita cari elemen contohnya aja di sini dua ya kita cari dan lalu kita cari di sini di Index 2 dan langsung ketemu maka di sini bisa kita langsung hapus kita hapus ya si du ini dan lalu si index 2 itu dia bakal ngpoint ke si elemen 12 Jadi sebenarnya Mirip ya kayak searching dan kompleksitasnya juga mirip Karena kita harus tinggal pakai fungsi ini dan mencari dan Lalu nanti kita tinggal hapus saja elemen yang ada di link itu jadi ini konsep dari hashing chaining ya yang harus kalian ketahui mungkin rada ribet kalau kalian lihat di sini kita harus tahu tentang loading Vector tapi sebenarnya kalau kamu coba tonton lagi video ini pelan-pelan sebenarnya hashing chaining ini sangat simpel kita cuma tinggal Insert pakai fungsi hashing dan tinggal kita taruh di linklish dan kalau searching kita tinggal searching aja ya dan lalu kita kita perhatikan loading vektornya ya loading Vector itu sebenarnya cuman yang penting kita uniform distributif aja setiap elemen-elemen ini setiap si indeks-indeks ini biar nanti panjangnya linklist itu dia Balance dalam setiap indeknya dan lalu kalau delete tinggal kita pakai fungsi ini kita cari dan lalu kita tinggal hapus saja elemennya yang ada di linklist jadi kayak gitu tentang hasing chaining SO see you in the next video thank you