Friday, 4 September 2015

Tentang Hashing

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.

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:
  1. Mengubah IPK seorang mahasiswa bernama X menjadi Y.
  2. Bertanya "berapa nilai IPK dari mahasiswa yang bernama X?"
Cara paling sederhana untuk menyelesaikan persoalan itu adalah menyimpan daftar nama dan nilai IPK dalam array, lalu melakukan linear search untuk setiap pertanyaan. Sayangnya cara ini tidak efisien.

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]".
Kedua operasi ini akan saya sebut sebagai update dan read. Kompleksitas operasi-operasi ini adalah O(K), dengan O(K) adalah kompleksitas melakukan hash pada suatu key.

    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:
    1. Untuk dua buah key yang sama, hasil hashing-nya selalu sama.
    2. Memiliki kompleksitas rendah.
    3. Meminimalkan collision (akan dijelaskan pada bagian selanjutnya).
    Pada kebanyakan kasus, kompleksitas fungsi hash dapat dianggap O(1).  Sehingga operasi update dan read bekerja dalam O(1).

    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:
    1. Dapatkan nilai hash dari "ali", yaitu 1223.
    2. Untuk setiap elemen pada linked list T[1223], cek apakah ada yang memiliki key "ali".
    3. Ternyata ada, jadi cukup ganti value pada elemen yang bersangkutan menjadi 0.
    Bagaimana jika tidak ditemukan? Artinya belum pernah ada key "ali" yang disimpan. Dengan demikian, cukup tambahkan elemen baru pada linked list T[1223] yang menyimpan key "ali" dan value 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.

    No comments :

    Post a Comment