Fungsi hash pada String

Didalam kelas String, kode hash dari string s dengan panjang n dapat dihitung sebagai berikut :

atau jika di implementasikan didalam code,

int h = 0;
for (int i=0; i < n; i++){
h = 31 * h + s.charAt(i);
}
Sebagai contoh kode hash pada string “hello” menggunakan nilai Unicode pada karakter

h	e	l	l	o
104	101	108	108	111

kemudian hitung seperti dibawah ini

Didalam operasi aritmatika umum menggunakan 32-bit aritmatika modular yang mengabaikan overflow. Sebegai contoh

Integer.MAX_VALUE + 1 = Integer.MIN_VALUE

dimana

Integer.MAX_VALUE = 2147483647

Integer.MIN_VALUE = -2147483648

Sebagai catatan, karena menggunakan aritmatika modular maka kode hash mungkin menghasilkan nilai negatif atau bahkna nol. Hal ini bisa menghasilkan nilai positif karena hello merupakan string yang pendek. Sebagai contoh, kode hash untuk helloa, yang merupakan 31 kali kode hash dari hello ditambah dengan 97, maka hasilnya bukan 3074032079. Karena bilangan tersebut melampaui batas bilangan bulat 32-bit, sehingga 3074032079 – 2³² = -1220935217

Technorati : fungsi, fungsi hash, hash, string
Del.icio.us : fungsi, fungsi hash, hash, string