Collisioni di hash
Le funzioni di hash non sono perfette: a volte, dati completamente diversi possono produrre lo stesso risultato di hash. Ciò va contro la mappatura uno-a-uno tra gli input e il valore di hash. Di conseguenza, è possibile che diverse stringhe ottengano lo stesso valore di hash o che due numeri distinti producano lo stesso hash. Le collisioni di hash possono causare problemi di sicurezza e anche rallentare le prestazioni, a seconda del contesto in cui si verificano. Per esempio, una semplice funzione di hash che associa una coppia di interi a un valore di hash può mappare molte coppie (a, b) allo stesso risultato:
Ecco alcuni esempi di coppie
(a, b) che restituiscono lo stesso valore di hash:- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
Quindi, se avessimo un elenco di coppie pensato appositamente per generare lo stesso valore di hash, otterremmo molte collisioni. Di conseguenza, la ricerca di un valore o il controllo dell’esistenza di una coppia
(a, b) in una lista risulterebbe assai inefficiente, o addirittura errato (a seconda dell’implementazione).Le collisioni di hash possono essere anche sorgente di vulnerabilità di sicurezza. Le password degli utenti sono spesso memorizzate come hash per motivi di protezione (così da non rivelarle in caso di violazione del database). Se la funzione di hash non è buona e produce molte collisioni, un malintenzionato potrebbe accedere a un account senza indovinare la password corretta. Se l’hash di una password casuale coincide con l’hash della password originale, il sistema la considera come la stessa persona.
Una funzione di hash valida dovrebbe minimizzare il più possibile le collisioni. Di solito, le funzioni di hash integrate offrono buone prestazioni su input casuali. Tuttavia, se i dati in ingresso hanno una struttura particolare o il problema presenta requisiti specifici, potrebbe essere necessario implementare una funzione di hash personalizzata.
Sfida: Controllo delle collisioni
Data una funzione di hash
h che associa una coppia di interi (a, b) a un numero intero, ti viene richiesto di verificare se h è sufficientemente buona. Il programma deve controllare la presenza di collisioni e stampare Yes se non ne trova, oppure No in caso contrario. La funzione di hash è definita come:Input
La prima riga dell’input contiene un singolo intero
n (1 ≤ n ≤ 10 000), il numero di coppie.Le successive
n righe contengono coppie di interi (0 ≤ ≤ ), separate da uno spazio. È garantito che le coppie fornite siano uniche fra loro.Output
Il programma deve stampare
Yes se, per i dati forniti, la funzione h(a, b) evita le collisioni, altrimenti No.Examples
Input | Output |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB