Module: Hashing

Oltre alle sequenze, puoi anche hash set. Cioè, insiemi di oggetti senza ordine su di essi. Viene calcolato secondo la seguente formula:
hash(A) = \(\sum_{a \in A} p^{ord(a)}\)   <- contare tutto modulo
dove ord è una funzione che assegna ad un oggetto dell'insieme il suo numero ordinale assoluto tra tutti i possibili oggetti (per esempio, se gli oggetti sono numeri naturali, allora ord(x) = x, e se lettere latine minuscole, allora ord(& #39;a' ;) = 1, ord('b') = 2 ecc.)

Cioè, per ogni oggetto associamo un valore pari alla base alla potenza del numero di questo oggetto e sommiamo tutti questi valori per ottenere un hash dell'intero insieme. Come risulta chiaro dalla formula, l'hash viene facilmente ricalcolato se un elemento viene aggiunto o rimosso dall'insieme (basta aggiungere o sottrarre il valore richiesto). Stessa logica,  se non vengono aggiunti o rimossi singoli elementi, ma altri insiemi (basta aggiungere/sottrarre il loro hash).

Come puoi già capire, i singoli elementi sono considerati come insiemi di dimensione 1, per i quali possiamo calcolare l'hash. E i set più grandi sono semplicemente un'unione di tali set singoli, dove combinando i set, aggiungiamo i loro hash.

In effetti, questo è sempre lo stesso hash polinomiale, ma prima del coefficiente in p^m , avevamo il valore dell'elemento della sequenza sotto il numero n - m - 1 (dove n è la lunghezza della sequenza), e ora questo è il numero di elementi nell'insieme il cui numero ordinale assoluto è uguale a m.

In tale hashing, si deve prendere una base sufficientemente grande (maggiore della dimensione massima dell'insieme), o usare il doppio hashing per evitare situazioni in cui un insieme di p oggetti con numero ordinale assoluto m ha lo stesso hash di un insieme con un oggetto con numero ordinale assoluto m. numero ordinale m+1.