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 – 232 = -1220935217

Technorati : , , ,
Del.icio.us : , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s