Java Source Code Pada Metode Rolling Hash

Hashing adalah suatu cara untuk mentransformasi sebuah string menjadi suatu nilai yang unik dengan panjang tertentu (fixed-length) yang berfungsi sebagai penanda string tersebut. Fungsi untuk menghasilkan nilai ini disebut fungsi hash, sedangkan nilai yang dihasilkan disebut nilai hash.

Contoh sederhana hashing adalah:

Firdaus, Hari
Munir, Rinaldi
Rabin, Michael
Karp, Richard

Menjadi

7864 = Firdaus, Hari
9802 = Munir, Rinaldi
1990 = Rabin, Michael
8822 = Karp, Richard

Contoh di atas adalah penggunaan hashing dalam pencarian pada database. Apabila tidak di-hash, pencarian akan dilakukan karakter-per-karakter pada nama-nama yang panjangnya bervariasi dan ada 26 kemungkinan pada setiap karakter. Namun pencarian akan menjadi lebih efisien setelah di-hash karena kemungkinan setiap angka berbeda. Nilai hash pada umumnya digambarkan sebagai fingerprint yaitu string pendek yang terdiri atas huruf dan angka yang terlihat acak (data biner yang ditulis dalam heksadesimal).

Rolling hash merupakan fungsi yang digunakan untuk menghasilkan nilai hash dari rangkaian gram dalam algoritma winnowing. Fungsi hash H(c1...ck) didefinisikan sebagai berikut:

 

Rumus Rolling hash

Keterangan:
c : nilai ascii karakter
b : basis (bilangan prima)
k : banyak karakter

Keuntungan dari rolling hash adalah untuk nilai hash berikutnya H(c2...ck+1) dapat dilakukan dengan cara:

Rumus Penghitungan nilah hash berikutnya dengan rolling hash

Dengan begitu tidak perlu melakukan iterasi dari indeks pertama sampai terakhir untuk menghitung nilai hash untuk gram ke-2 sampai terakhir. Hal ini tentu dapat menghemat biaya komputasi saat menghitung nilai hash dari sebuah gram

Berikut flowchart rolling hash:

Berdasarkan rumus rolling hash di atas, berikut source code java untuk fungsi pada metode rolling hash:

public class HashGram {
    public Long rollingHash(String sub) {
        long hash_value = 0;
        int ascii;
        int prev_hash = 0;
        int basis = 3;
        int c_awal = 0;
        int length = sub.length() - 1;
        System.out.println("k = "+sub.length());
        System.out.println("b = "+basis);
        if (prev_hash == 0) {
            for (int i = 0; i <= length; i++) {
                ascii = sub.charAt(i);
                hash_value += (long) (ascii * Math.pow(basis, length - i));
                System.out.println("c ke-"+(i+1)+" adalah huruf '"+sub.charAt(i)+"' bernilai ASCII = "+ascii);
            }
        } else {
            hash_value = prev_hash - (long) (c_awal * Math.pow(basis, length));
            hash_value *= basis;
            hash_value += sub.charAt(length);
        }
        c_awal = sub.charAt(0);
        prev_hash = (int) hash_value;
        System.out.println("Nilai hash pada kata = '"+sub+"' = "+hash_value);
        return hash_value;
    }

    public static void main(String[] args) {
        HashGram hg = new HashGram();
        String text = "dhafiqsagara";
        hg.rollingHash(text);
    }
}

Berikut hasilnya: