Supponiamo di avere un numero di collisioni più grande del previsto nella mia tabella hash che ha 2 ^ w bucket (metà dei quali vuoti). Quindi scelgo un nuovo polinomio CRC casuale che genera valori di controllo w-bit (cioè, un valore w + 1 bit con il bit alto e il bit basso forzato a 1, e gli altri bit w-1 estratti da / dev / random), e ri-hash tutti gli elementi nella mia tabella usando il nuovo CRC come funzione di hash. La maggior parte di tali funzioni hash si avvicinano al numero previsto di collisioni previsto dal problema relativo al compleanno , non importa quali particolari corde mi ha dato Mallory da usare come chiavi per gli oggetti nel mio hash table?
In altre parole:
È lo schema per le impronte digitali di Rabin con un polinomio casuale a famiglia di funzioni hash universale ?