Hashing
Quando si lavora con collezioni di elementi, come una lista di stringhe o una lista di tuple, ricercare un elemento o rispondere a domande del tipo “L’elemento X è presente nella nostra collezione?” può diventare molto dispendioso dal punto di vista computazionale. Confrontare numeri, invece, è estremamente veloce, e i nostri computer sono progettati per effettuare confronti numerici in modo molto efficiente (a differenza di stringhe o tuple). Per questo, se riusciamo a mappare i dati in un valore numerico, alcune operazioni (come trovarne l’occorrenza o verificarne la presenza) risultano più rapide.
La tecnica di mappare dati di dimensioni arbitrarie a dati di dimensione fissa si chiama hashing. Il numero risultante (hash) funge da identificatore univoco per i dati originali. Di solito, disponiamo di una funzione
hash in grado di mappare i dati iniziali a un valore di dimensione fissa (per esempio, un numero).In Python, ad esempio, esiste la funzione integrata
hash, che può mappare qualsiasi oggetto immutabile a un numero, in genere compreso nell’intervallo . È importante notare che può essere applicata solo a oggetti immutabili. Cercare di calcolare l’hash di una lista o di un dizionario (che sono mutabili e possono essere modificati aggiungendo o rimuovendo elementi) genererebbe infatti un errore:print(hash(123)) # 123
print(hash('Anna')) # 2573300035916889866
print(hash('Bob')) # -2781086332262035333
print(hash((2, 'Simon'))) # -6551767300073204554
print(hash([1, 2])) # TypeError: unhashable type: 'list'Challenge: Hash a pair of integers
Realizziamo ora una funzione di hash personalizzata
h. Riceverà una coppia di interi e dovrà restituirne l’hash. La funzione h è definita come:In questo modo, il valore hash sarà sempre compreso nell’intervallo [0; 5077).
Input
L’unica riga di input contiene due numeri
a e b ( ≤ a, b ≤ ).Output
Il programma deve stampare l’hash della coppia (a, b).
Esempi
Input | Output |
4 5 | 2916 |
23452 5432 | 3751 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB