Seni Hashing

Setelah mempelajari hashing, Anda mungkin perlu tahu tentang teknik-teknik khusus hashing. Teknik ini saya dapatkan melalui pengalaman, dan telah berkali-kali "menyelamatkan" peringkat tim pada kompetisi. Semoga berguna juga untuk Anda :)

Oh ya, selain rolling hash, nama-nama yang tercantum merupakan nama ciptaan saya. 

---

Rolling Hash

Teknik ini sangat umum digunakan. Saya mempelajarinya dari tutorial Topcoder.

Ceritanya adalah diberikan sebuah string S.
Bagaimana kita mendapatkan nilai hash dari semua substring S yang memiliki panjang k?
Fungsi hash yang digunakan pada rolling hash adalah menganggap string sebagai bilangan basis 26. Lebih umum lagi, basis ini sebenarnya boleh berapa saja. Misalkan basis yang dipilih adalah B.

Anggap S = "ayamxzc" dan k=4. Jika h[i] menyatakan nilai hash untuk S[i..i+k-1], maka bisa digambarkan nilai h[0] sampai h[3] sebagai berikut:

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?