Saya akan menjelaskan sebuah teknik yang bernama hashing. Hashing merupakan teknik yang sering digunakan dalam pemrograman pada umumnya. Untuk pemrograman kompetitif, hashing dapat membantu menyelesaikan persoalan secara tidak terduga.
Diberikan sejumlah nama orang dan nilai IPK mereka. Selanjutnya, terdapat banyak operasi berupa:
Cara yang lebih baik adalah dengan struktur data Binary Search Tree (BST). Dengan BST, kompleksitas untuk setiap operasi adalah O(log N) (tentunya ada dikalikan dengan konstanta untuk membandingkan string, tetapi tidak saya tulis). Memang cukup cepat, tetapi cara ini bukan yang terbaik.
Lalu bagaimana?
Seandainya yang diberikan bukan nama, tetapi nomor mahasiswa yang kisarannya antara 000000 sampai 999999, apakah cara lebih baik yang bisa dilakukan?
Jawabannya adalah cukup dengan membuat direct addressing table. Artinya, buat array yang bisa menampung 0 sampai 999999, misalnya bernama T. Untuk operasi mengubah IPK seseorang dengan ID X menjadi Y, cukup ubah T[X] = Y. Mencari IPK seseorang dengan ID X juga mudah, cukup kembalikan T[X]. Jadi setiap operasi bisa dilakukan dalam O(1).
Sayang sekali yang kita miliki bukan nomor ID, melainkan nama. Untungnya, kita memiliki teknik yang bernama hashing.
Artinya:
Kita berhasil mengubah string "abca" menjadi sebuah angka, yaitu 7. Hal ini juga akan dilakukan untuk setiap nama mahasiswa dalam setiap operasi; sebelumnya di-hash terlebih dahulu. Dengan demikian, direct addressing table dapat kembali digunakan! Kini kompleksitas untuk setiap operasi adalah O(K), dengan K adalah kompleksitas menghitung nilai hash melalui fungsi hashing. Untuk contoh di atas, K = panjang string. Jika panjang setiap string cukup kecil, setiap operasi bisa dianggap O(1).
Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi:
Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan key, dan IPK merupakan value.
Perhatikan bahwa key tidak harus berupa string. Tipe data apapun dapat didukung, asalkan didefinisikan fungsi hash-nya. Kalau untuk value, tentu saja datanya bisa bertipe apapun.
Operasi minimal yang perlu didukung oleh hash table adalah:
Beberapa string sangat mungkin memiliki nilai hash yang sama! Sebagai contoh, "abca", "aabc", dan "baca" sama-sama memiliki nilai hash 7. Akibatnya, hash table akan bingung membedakan mahasiswa bernama "aabc", "abca", dan "baca"!
Closed hashing
Contoh teknik yang digunakan adalah linear/quadratic probing. Saya tidak menjelaskan bagian ini karena menurut saya kurang cocok digunakan saat kompetisi. Kalian yang tertarik bisa mengunjungi artikel ini.
Open hashing
Idenya sederhana. Kita dapat mengganti array pada direct addressing table menjadi "array of linked list". Misalnya "array of linked list" ini bernama T. Setiap elemen pada linked list T[i] menyimpan sejumlah pasangan key dan value untuk memiliki nilai hash key berupa i.
Ketika kita hendak menyimpan suatu nilai ke T[i] dan terjadi collision (sudah ada isinya), kita cukup tambahkan elemen baru pada T[i]. Bentuknya akan menjadi seperti rantai. Berikut ilustrasinya:
Pada ilustrasi tersebut, angka-angka di kiri merupakan i.
Diketahui pula bahwa "madani", "ali", dan "omar" memiliki nilai hash yang sama, yaitu 1223. Untuk kasus seperti ini, mereka akan membentuk rantai pada T[i].
Dengan struktur ini, operasi update perlu didahului dengan sedikit linear search. Sebagai contoh, misalkan untuk key "ali" hendak diganti value-nya menjadi 0:
Operasi read dapat dilakukan dengan hal serupa. Cukup hash, lalu cari pada linked list yang bersangkutan.
Pada kondisi ideal, panjang rata-rata dari suatu linked list jauh lebih kecil dari N, dengan N adalah banyaknya entri yang disimpan pada hash table.
Cara ketiga, anggap saja tidak ada collision
Anda harus menyiapkan fungsi hash yang bagus. Contoh yang sering digunakan untuk hash pada string adalah menganggap string sebagai bilangan basis 26, kemudian lakukan modulo dengan bilangan prima yang besar (misalnya 109+7).
Cara ini tidak disarankan pada dunia nyata. Namun pada kompetisi, saya hampir selalu menggunakan asumsi tidak ada collision.
Cara yang dapat digunakan adalah membuat array T berukuran P, dengan P adalah bilangan prima yang mendekati ukuran array sewajarnya (misalnya jutaan). Kemudian modulo nilai hash dengan P, baru dimasukkan ke T.
Mengapa harus bilangan prima? Hal ini dapat memperkecil peluang terjadinya collision. Ada banyak penjelasan di balik argumen ini, misalnya di sini.
Kini terdapat unordered_map pada C++, yang bekerja sangat cepat. Kegunaannya mirip seperti map, tetapi operasi insert bekerja dalam O(1). Memang sebenarnya implementasi unordered_map pada C++ adalah hash table :)
Saya pernah beberapa kali berhasil accepted dengan menggunakan hashing. Salah satunya yang berkesan adalah soal yang meminta kita memeriksa apakah dua tree yang diberikan isomorphic (memiliki struktur sama).
Permasalahan
Dalam sebuah universitas, terdapat banyak mahasiswa. Setiap mahasiswa memiliki nilai IPK dan bisa berubah sewaktu-waktu.Diberikan sejumlah nama orang dan nilai IPK mereka. Selanjutnya, terdapat banyak operasi berupa:
- Mengubah IPK seorang mahasiswa bernama X menjadi Y.
- Bertanya "berapa nilai IPK dari mahasiswa yang bernama X?"
Cara yang lebih baik adalah dengan struktur data Binary Search Tree (BST). Dengan BST, kompleksitas untuk setiap operasi adalah O(log N) (tentunya ada dikalikan dengan konstanta untuk membandingkan string, tetapi tidak saya tulis). Memang cukup cepat, tetapi cara ini bukan yang terbaik.
Lalu bagaimana?
Seandainya yang diberikan bukan nama, tetapi nomor mahasiswa yang kisarannya antara 000000 sampai 999999, apakah cara lebih baik yang bisa dilakukan?
Jawabannya adalah cukup dengan membuat direct addressing table. Artinya, buat array yang bisa menampung 0 sampai 999999, misalnya bernama T. Untuk operasi mengubah IPK seseorang dengan ID X menjadi Y, cukup ubah T[X] = Y. Mencari IPK seseorang dengan ID X juga mudah, cukup kembalikan T[X]. Jadi setiap operasi bisa dilakukan dalam O(1).
Sayang sekali yang kita miliki bukan nomor ID, melainkan nama. Untungnya, kita memiliki teknik yang bernama hashing.
Ide Dasar
Ide utama dari hashing adalah mengubah suatu string menjadi suatu bilangan dengan suatu fungsi. Misalkan kita memiliki string "abca", dan fungsi f yang memetakan string ke bilangan bulat berikut:f(S) = ( (banyaknya 'a')*1 + (banyaknya 'b')*2 + (banyaknya 'c')*3 + ... + (banyaknya 'z')*26 ) mod 1000000
Artinya:
f("abca") = (2*1 + 1*2 + 1*3 + 0*4 + 0*5 + ... + 0*26) mod 1000000
= 7
Kita berhasil mengubah string "abca" menjadi sebuah angka, yaitu 7. Hal ini juga akan dilakukan untuk setiap nama mahasiswa dalam setiap operasi; sebelumnya di-hash terlebih dahulu. Dengan demikian, direct addressing table dapat kembali digunakan! Kini kompleksitas untuk setiap operasi adalah O(K), dengan K adalah kompleksitas menghitung nilai hash melalui fungsi hashing. Untuk contoh di atas, K = panjang string. Jika panjang setiap string cukup kecil, setiap operasi bisa dianggap O(1).
Hashing
Dapat diartikan sebagai aktivitas untuk mengubah suatu objek menjadi serangkaian angka/karakter/sejenisnya. Pada contoh sebelumnya, kita melakukan hash pada string menjadi bilangan.Anda mungkin menyadari bahwa tabel T pada contoh sebelumnya bekerja seperti array. Kita seakan-akan dapat melakukan operasi:
T["gozali"] = 3;
printf("%d\n", T["gozali"]);Pada ilmu komputer, tabel seperti ini disebut sebagai hash table. Struktur data ini erat kaitannya dengan konsep "key value". Key adalah hal yang menjadi indeks, dan value adalah nilai yang berasosiasi dengannya. Pada contoh permasalahan sebelumnya, nama mahasiswa merupakan key, dan IPK merupakan value.
Perhatikan bahwa key tidak harus berupa string. Tipe data apapun dapat didukung, asalkan didefinisikan fungsi hash-nya. Kalau untuk value, tentu saja datanya bisa bertipe apapun.
Operasi minimal yang perlu didukung oleh hash table adalah:
- Diberikan key X dan value Y, catat bahwa value dari X adalah Y. Operasi ini dapat dianggap "T[X] = Y".
- Diberikan key X, cari value-nya. Operasi ini dapat dianggap seperti mengakses "T[X]".
Fungsi Hashing
Pada bagian sebelumnya, saya memberi contoh fungsi hashing sederhana. Sebenarnya fungsi hashing itu bebas, terserah Anda ingin mendefinisikannya seperti apa. Namun, diharapkan fungsi hashing memiliki kriteria sebagai berikut:- Untuk dua buah key yang sama, hasil hashing-nya selalu sama.
- Memiliki kompleksitas rendah.
- Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).
Collision
Kembali pada contoh fungsi hash yang saya berikan. Apakah Anda menyadari hal yang buruk dari fungsi ini?Beberapa string sangat mungkin memiliki nilai hash yang sama! Sebagai contoh, "abca", "aabc", dan "baca" sama-sama memiliki nilai hash 7. Akibatnya, hash table akan bingung membedakan mahasiswa bernama "aabc", "abca", dan "baca"!
Penanganan Collision
Collision dapat ditangani. Beberapa cara yang saya ketahui:Closed hashing
Contoh teknik yang digunakan adalah linear/quadratic probing. Saya tidak menjelaskan bagian ini karena menurut saya kurang cocok digunakan saat kompetisi. Kalian yang tertarik bisa mengunjungi artikel ini.
Open hashing
Idenya sederhana. Kita dapat mengganti array pada direct addressing table menjadi "array of linked list". Misalnya "array of linked list" ini bernama T. Setiap elemen pada linked list T[i] menyimpan sejumlah pasangan key dan value untuk memiliki nilai hash key berupa i.
Ketika kita hendak menyimpan suatu nilai ke T[i] dan terjadi collision (sudah ada isinya), kita cukup tambahkan elemen baru pada T[i]. Bentuknya akan menjadi seperti rantai. Berikut ilustrasinya:
Pada ilustrasi tersebut, angka-angka di kiri merupakan i.
Diketahui pula bahwa "madani", "ali", dan "omar" memiliki nilai hash yang sama, yaitu 1223. Untuk kasus seperti ini, mereka akan membentuk rantai pada T[i].
Dengan struktur ini, operasi update perlu didahului dengan sedikit linear search. Sebagai contoh, misalkan untuk key "ali" hendak diganti value-nya menjadi 0:
- Dapatkan nilai hash dari "ali", yaitu 1223.
- Untuk setiap elemen pada linked list T[1223], cek apakah ada yang memiliki key "ali".
- Ternyata ada, jadi cukup ganti value pada elemen yang bersangkutan menjadi 0.
Operasi read dapat dilakukan dengan hal serupa. Cukup hash, lalu cari pada linked list yang bersangkutan.
Pada kondisi ideal, panjang rata-rata dari suatu linked list jauh lebih kecil dari N, dengan N adalah banyaknya entri yang disimpan pada hash table.
Cara ketiga, anggap saja tidak ada collision
Anda harus menyiapkan fungsi hash yang bagus. Contoh yang sering digunakan untuk hash pada string adalah menganggap string sebagai bilangan basis 26, kemudian lakukan modulo dengan bilangan prima yang besar (misalnya 109+7).
Cara ini tidak disarankan pada dunia nyata. Namun pada kompetisi, saya hampir selalu menggunakan asumsi tidak ada collision.
Ukuran Array T
Dari tadi saya menjelaskan cara melakukan hash. Namun, bisa saja nilai hash yang didapatkan sangat besar, misalnya ratusan juta. Bagaimana mungkin kita menyiapkan array T dengan ukuran sampai ratusan juta?Cara yang dapat digunakan adalah membuat array T berukuran P, dengan P adalah bilangan prima yang mendekati ukuran array sewajarnya (misalnya jutaan). Kemudian modulo nilai hash dengan P, baru dimasukkan ke T.
Mengapa harus bilangan prima? Hal ini dapat memperkecil peluang terjadinya collision. Ada banyak penjelasan di balik argumen ini, misalnya di sini.
Hash pada Praktiknya
Jika membutuhkan hash, saya tidak membuat array T seperti yang saya jelaskan. Saya melakukan hash supaya key menjadi bilangan, lalu menyimpannya pada map C++. Memang kompleksitasnya sudah tidak O(1) per update atau read, tetapi setidaknya operasi insert pada map menjadi sesederhana membandingkan bilangan (ketimbang membandingkan string!)Kini terdapat unordered_map pada C++, yang bekerja sangat cepat. Kegunaannya mirip seperti map, tetapi operasi insert bekerja dalam O(1). Memang sebenarnya implementasi unordered_map pada C++ adalah hash table :)
Saya pernah beberapa kali berhasil accepted dengan menggunakan hashing. Salah satunya yang berkesan adalah soal yang meminta kita memeriksa apakah dua tree yang diberikan isomorphic (memiliki struktur sama).
Penutup
Tulisan ini sebenarnya adalah pengantar untuk tulisan utama saya tentang hashing, yaitu seni-seni pada hashing.
good explaination
BalasHapusthanks for sharing :)
mantappp banget kak ini artikel lebih debes dari scele!!!
BalasHapusAku mumet
BalasHapus