Hashing
Lorsqu’on travaille avec des collections d’éléments, comme une liste de chaînes de caractères ou une liste de tuples, il devient très coûteux en termes de calcul de rechercher des éléments dans la collection ou de répondre à des questions du type « L’élément X est-il présent dans notre collection ? ». En revanche, la comparaison de nombres est très rapide, et nos ordinateurs sont spécialement conçus pour comparer des nombres de manière efficace (contrairement aux chaînes de caractères ou aux tuples). Ainsi, si nous pouvons associer les données à une valeur numérique, des opérations comme la recherche d’un élément ou la vérification de sa présence dans la collection deviennent plus rapides.
La technique qui consiste à associer des données de taille arbitraire à des données de taille fixe est appelée « hashing ». Le nombre obtenu (le hash) sert d’identifiant unique pour les données d’origine. En général, nous disposons d’une fonction
hash qui peut mapper les données initiales vers des données de taille fixe (typiquement un nombre).Par exemple, Python possède une fonction intégrée
hash qui peut associer tout objet immuable à un nombre, généralement compris dans l’intervalle . Notez qu’elle ne fonctionne que sur des objets immuables. Ainsi, tenter de hasher une liste ou un dictionnaire (qui sont des objets mutables et peuvent être modifiés en y ajoutant ou en retirant des éléments) déclenchera une erreur :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
Implémentons une fonction de hachage personnalisée
h. Elle recevra une paire d’entiers et devra renvoyer la valeur de hachage. La fonction h est définie comme suit :De cette manière, la valeur de hachage se trouvera toujours dans l’intervalle [0; 5077).
Input
L’unique ligne de l’entrée contient deux nombres
a et b ( ≤ a, b ≤ ).Output
Le programme doit afficher le hash de la paire (a, b).
Examples
Entrée | Sortie |
4 5 | 2916 |
23452 5432 | 3751 |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB