Seuraava merkkijonojen hajautustekniikka tunnetaan nimellä "rolling hash". Muistetaan, että Javassa, kuten muissakin ohjelmointikielissä, merkkijonon kirjaimet ovat 8-bittisiä numeroita. Merkitään merkkijonon s i:ttä kirjainta vastaavaa numeroa (indeksointi alkaa nollasta) si.
Olkoon meillä merkkijono s, jonka pituus on n ja positiiviset kokonaisluvut A ja B. Merkkijonon s hajautusarvo "rolling hash" -tekniikkaa käyttäen lasketaan kaavalla
An-1s0 + An-2s1 + ... + A1sn-2 + sn-1 mod BEsimerkiksi seuraava Java-koodi laskee merkkijonon
s hajautusarvon:
long H=0;
for(int i=0; i<s.length(); i++)
H=(A*H + s.charAt(i))%B;
Mikä tästä hajautustekniikasta sitten tekee niin erikoisen? Oletetaan, että olemme laskeneet hajautusarvon merkkijonon s alkuosalle, jonka pituus on m, eli siis merkkijonolle, johon kuuluvat merkit s0...sm-1 järjestyksessä. Jos haluamme laskea hajautusarvon merkkijonolle s1...sm, niin suoraviivaisin tapa olisi vain laskea hajautusarvo kokonaan uusiksi. Tämän operaation aikavaativuus riippuu kuitenkin lineaarisesti luvusta m, ja on hitaampi kuin seuraavaksi esiteltävä tapa.
Nyt voimme laskea uuden hajautusarvon vakioajassa, kunhan meillä on tallessa merkkijonon s0...sm-1 hajautusarvo H. Nyt jos merkitään
H' = H - Am-1s0 mod B = Am-2s1 + Am-3s2 + ... + A1sm-2 + sm-1 mod Bniin saadaan merkkijonon
s1...sm hajautusarvo laskettua tämän avulla
A*H' + sm mod B = Am-1s1 + Am-2s2 + ... + A1sm-1 + sm mod BTäten uusi hajautusarvo saadaan todella laskettua vakioajassa. Tätä ideaa voi jatkaa eteenpäin, jos halutaan laskea merkkijonon
s2...sm+1 hajautusarvo, niin se saadaan vakioajassa merkkijonon s1...sm hajautusarvosta.
Luvun H' laskemisessa on syytä olla tarkkana. Seuraava tapa, joka ensisilmäyksellä vaikuttaa täysin järkevältä, on kuitenkin ongelmallinen
long H' = (H - C*s.charAt(0))%B;tässä muuttuja
C sisältää luvun Am-1 jakojäännöksen luvulla B. Ongelmaksi muodostuu se, että negatiivisen luvun jakojäännös on negatiivinen, joka aiheuttaa ongelmia. Koodin voi korjata seuraavalla tavalla
long H' = ((H - C*s.charAt(0))%B + B) % B;
Yhteentörmäysten välttämiseksi luvuilla A ja B ei kannata olla yhteisiä tekijöitä. Lisäksi jos luku B on kakkosen potenssi, on yhteentörmäysten generointi todella helppoa, kuten tässä on kerrottu (linkin takaa löytyy täysin ylimääräistä ja melko matemaattista lisämateriaalia). Käytännössä B kannattaa olla joku mahdollisimman suuri (muista varoa ylivuotoja) luku ja A "melko satunnaisesti" valittu luku välillä 1..B. Liian pieni luku muuttujassa A voi aiheuttaa yhteentörmäyksiä helpommin.
Vaikka hajautus toimisi optimaalisesti siinä mielessä, että mahdollisia hajautusarvoja saadaan suunnilleen tasaisesti ja "satunnaisesti", niin syntymäpäiväongelman nojalla erilaisia mahdollisia hajautusarvoja tulisi olla yli n2, jotta olisi epätodennäköistä, että n hajautuksessa ei tapahtuisi yhtään yhteentörmäystä. Jos lukua B ei voi enää kasvattaa ongelmitta, on toinen vaihtoehto laskea jokaiselle hajautettavalle objektille kaksi hajautusarvoa eri parametreilla. Erilaisia hajautusarvopareja on huomattavasti enemmän kuin yksittäisiä hajautusarvoja, joten yhteentörmäysten todennäköisyys vähenee.
Toinen vaihtoehto estää yhteentörmäysten vaikutus on olla luottamatta sokeasti hajautusfunktion antamaan hajautusarvoon ja tarkistaa ovatko kaksi saman hajautusarvon saanutta objektia todella samat. Täten toimivat esimerkiksi hajautustaulut.