rolling hash

Un rolling hash (chiamato anche hash ricorsivo o rolling checksum) è una funzione di hash che processa l'input tramite una finestra scorrevole sull'input stesso. Alcune funzioni hash permettono il calcolo molto rapido, aggiornando il risultato in base al valore dell'hash nella finestra precedente e in base ai valori aggiunto e rimosso dalla finestra all'iterazione corrente, in maniera analoga al calcolo di una media mobile. Tutte le funzioni di rolling hash hanno complessità computazionale lineare nel numero di elementi, ma la complessità rispetto alla lunghezza k della finestra può variare a seconda dell'algoritmo. Ad esempio la funzione rolling hash di Rabin-Karp richiede la moltiplicazione di due interi di bit, con complessità , mentre l'hash di n-gram con polinomi ciclici può essere calcolato in tempo lineare. Un rolling hash può essere al più una funzione due-a-due indipendente o una funzione , ma non può essere k-a-k indipendente.