Struktur Data - Menangani Bentrokan atau Collision

Menangani Bentrokan (Collision) pada Tabel Hash

Sudah kita bahas pada materi sebelumnya tentang Hash table yang merupakan metode atau pendekatan yang terbaik dalam menghitung indeks array dari key, meskipun demikian, akan terjadi masalah yang cukup jelas pada metode tersebut. Sebagaimana contoh yang kami sebutkan, apa yang terjadi jika terdapat dua karyawan yang kebetulan memiliki tiga digit yang sama? Ini disebut sebagai collision.

Collision artinya terdapat lebih dari satu data yang memiliki hash index yang sama, padahal mestinya cuma satu index array yang hanya dapat menyimpan satu data saja. Untuk meminimalkan collision kita bisa gunakan hash function yang dapat mencapai seluruh indeks/alamat.

Kadang kita mungkin menganggap bahwa ‘Collision’ tidak terjadi sangat sering ketika hanya sebagian kecil dari set key yang mungkin dipilih, tetapi asumsi ini salah. Sebagai contoh, pertimbangkan kumpulan orang dengan fungsi hash yang memberikan tanggal lahir mereka sebagai jumlah hari dalam setahun, misal 1 Januari adalah 1, 2 Januari adalah 2,… , 31 Desember adalah 365. Orang mungkin berpikir bahwa jika semua yang kita ingin lakukan adalah menyimpan jumlah 24 pada array dengan lokasi 365, ‘Collision’ akan tidak mungkin terjadi, namun, ternyata probabilitas ‘Collision’ lebih besar dari 50%. Hal ini sangat mengejutkan pada pandangan pertama bahwa fenomena ini telah dikenal sebagai paradoks ulang tahun von Mises(The von Mises birthday paradox)

Sangat mudah untuk memahami apa yang sedang terjadi. Misalkan kita memiliki sekelompok n orang dan ingin mengetahui seberapa besar kemungkinan terjadi diantara mereka, memiliki hari ulang tahun yang sama, dengan asumsi bahwa ulang tahun didistribusikan secara merata selama 365 hari dalam setahun. Mari kita sebut probabilitas ini p (n). Sebenarnya lebih mudah untuk terlebih dahulu menghitung probabilitas q (n) bahwa tidak ada dua dari mereka yang mempunyai ulang tahun yang sama, dan kemudian p(n) = 1 –q(n). Untuk n = 1, probabilitas ini jelas q (1) = 1

Untuk n = 2 kita mendapatkan q (2) = 364365, karena, untuk orang kedua yang ditambahkan, 364 dari 365 hari bukan ulang tahun orang pertama

Untuk n = 3 kita dapatkan, q(3) = 364.363/ 3652 = 1 – P(3) dan untuk umumnya kasus n> 1 kita miliki: q(n) = 364.363….(366-n)/365n-1 = 1 – p(n)

Mungkin mengejutkan bahwa p (22) = 0. 476 dan p (23) = 0.507, yang berarti bahwa ada lebih dari 22 orang dalam suatu kelompok, yang lebih mungkin bahwa dua dari mereka mempunyai ulang tahun yang sama daripada tidak. Perhatikan bahwa di dunia nyata, distribusi ulang tahun selama setahun tidak selalu seragam, tetapi ini hanya meningkatkan kemungkinan bahwa dua orang memiliki hari ulang tahun yang sama. Dengan kata lain, ‘Collision’ ulang tahun jauh lebih mungkin daripada yang mungkin orang pikirkan pada awalnya.

Ada beberapa cara utama untuk memperbaiki ‘Collision’

Yang pertama adalah anda bisa mengubah nilai dalam fungsi hash Anda, atau untuk mengubah fungsi hash sepenuhnya, sehingga Anda memiliki lebih dari cukup slot untuk menyimpan semua nilai potensial Anda. Anda juga dapat menyimpan fungsi hash asli tetapi mengubah struktur array Anda. Daripada menyimpan satu nilai hash di setiap slot, Anda dapat menyimpan beberapa jenis daftar yang berisi semua nilai yang di-hash di tempat itu. Daftar ini biasanya disebut buckets(keranjang) dalam konteks ini.

Daripada menyimpan satu value di setiap slot, Anda dapat menyimpan banyak value atau koleksi di setiap buckets, tetapi apakah salah satu dari pendekatan ini benar-benar membantu. Untuk yang pertama, Anda dapat mempertahankan waktu konstan O(1) mencari tetapi dengan menggunakan angka yang lebih besar dalam fungsi hash Anda, Anda akan membutuhkan lebih banyak ruang untuk menyimpan nilai-nilai Anda.

Jika Anda melakukan ini secara reaktif dan mengubah value dalam fungsi hash maka setiap kali Anda mengalami collusion, memindahkan semua data Anda ke array baru, pasti akan meningkatkan kerumitan baik dari segi ukuran dan waktu.

Dengan pendekatan bucket, Anda masih perlu melakukan iterasi melalui beberapa koleksi, meskipun yang lebih pendek, setiap kali Anda mencari sesuatu. Fungsi hash memiliki waktu pencarian konstan dalam kasus rata-rata, tetapi karena sistem bucket, Anda bisa menyimpan setiap value dalam satu bucket dan kemudian hanya mengulang melalui list. Dalam kasus yang lebih buruk, ini akan berubah menjadi O (m). Ketika dilakukan dengan baik, hashing sangat cepat dan dapat menghemat banyak waktu, namun memang menimbulkan masalah yang sangat nyata. Tidak ada satu cara sempurna untuk mendesain fungsi hash. Anda perlu mempertimbangkan semua hal ini dan membangun sistem yang paling masuk akal untuk data dan keterbatasan Anda.

Seringkali, Anda harus memilih antara membuat fungsi hash yang menyebarkan value dengan baik tetapi menggunakan banyak ruang dan satu yang menggunakan lebih sedikit bucket tetapi mungkin harus melakukan beberapa searching di dalam setiap bucket. Idealnya, Anda akan memiliki satu hingga tiga elemen yang disimpan di setiap bucket. Jadi Anda dapat mendesain fungsi hash dengan mempertimbangkan hal itu.

Anda juga dapat melakukan dengan menggunakan fungsi hash kedua di dalam bucket besar untuk memisahkan elemen-elemen tersebut bahkan lebih. Itu akan bekerja sangat baik jika Anda tahu Anda akan memiliki data yang tersebar dengan baik tetapi akhirnya memiliki beberapa ember yang sangat besar.

box1

Semisal anda mempunyai tabel hash seperti ini:

box1

Disini kita memesan array dua dimensi dari awal. Kita dapat pikirkan setiap kolom sebagai bucket di mana kita membuang semua elemen yang memberikan hasil tertentu ketika fungsi hash disediakan, sehingga kolom kelima berisi semua kunci yang fungsi hash evaluasinya menjadi 4. Kemudian kita dapat menempatkan HKG ke dalam slot “di bawah” PHL, dan GLA dalam satu di bawah ORY, dan terus mengisi tabel dalam urutan yang diberikan hingga kami mencapai:

box1

Kelemahan dari pendekatan ini adalah bahwa kita harus memesan lebih banyak ruang daripada akhirnya akan diperlukan, karena harus memperhitungkan kemungkinan jumlah maksimal collusion. Bahkan saat table masih cukup kosong secara keseluruhan, collusion akan menjadi semakin mungkin. Selain itu, ketika mencari key tertentu, perlu untuk mencari seluruh kolom yang terkait dengan posisi yang diharapkan, setidaknya sampai slot kosong tercapai. Jika ada order pada kunci, mereka dapat disimpan dalam urutan menaik, yang berarti kita dapat menggunakan pencarian biner yang lebih efisien daripada pencarian linier, tetapi order akan memiliki overhead sendiri. Kerumitan rata-rata mencari item tertentu tergantung pada berapa banyak entri dalam array yang sudah diisi

Metode Chaining:. Daripada memesan seluruh sub-array (kolom di atas) untuk key yang bertabrakan, seseorang dapat membuat linked list untuk set entri yang terkait dengan setiap kunci. Chaining ini merupakan metode yang digunakan untuk mengatasi kemungkinan adanya collusion pada alamat – alamat yang sama, jika kita melihat pada sebuah alamat lengkap dan menyimpan rekaman yang mempunyai alamat yang sama, maka kita akan melihat adanya sebuah senarai berantai tunggal berkepala dengan kepalanya adalah alamat hash. Hasilnya untuk contoh di atas dapat digambarkan seperti ini:

box1

Pada chaining, kita menempatkan semua elemen hash ke slot yang sama ke dalam linked list yang sama, Pendekatan ini tidak menyisakan ruang yang tidak akan diambil, tetapi memiliki kelemahan bahwa untuk menemukan barang tertentu, list harus dilalui. Namun, menambahkan langkah hashing masih mempercepat pengambilan kembali.

Running time terburuk untuk penyisipan adalah O (1). Prosedur penyisipan cepat sebagian karena mengasumsikan bahwa elemen x yang disisipkan belum ada di dalamnya tabel; jika perlu, kita dapat memeriksa asumsi ini (dengan biaya tambahan) dengan mencari untuk elemen yang kuncinya adalah x.key sebelum kita masukkan. Untuk pencarian, running time terburuk sebanding dengan panjang list, kita dapat menghapus elemen dalam waktu O (1) jika daftar tersebut ditautkan secara ganda,

Operasi dictionary pada tabel hash T mudah diterapkan ketika collusion diselesaikan dengan chaining:

CHAINED-HASH-INSERT(T,x)
1 insert x di bagian atas daftar T [h(x.key)]
CHAINED-HASH-SEARCH(T,k)
1 search untuk elemen dengan key k pada daftar T [h.(k)]
CHAINED-HASH-DELETE(T,x)
1 delete x daftar T [h(x.key)]