Dictionnaires et tables de hachage : le guide complet pour les développeurs débutants

Qu'est-ce qu'un dictionnaire ?

Un dictionnaire (dictionary, map, associative array) est une structure de données qui stocke des paires clé-valeur. Chaque clé unique correspond à une certaine valeur. C'est comme un dictionnaire ordinaire où un mot (clé) est associé à sa définition (valeur).

En Python, les dictionnaires ressemblent à ceci :

student = {
    "name": "Anna",
    "age": 22,
    "specialty": "Programming"
}

print(student["name"])  # Présenté par : Anna

JavaScript utilise une syntaxe similaire :

const student = {
    name: "Anna",
    age: 22,
    specialty: "Programming"
};

console.log(student.name);  // Présenté par : Anna

Opérations de base avec les dictionnaires

Ajout et modification d'éléments

# Python
grades = {}
grades["Mathematics"] = 5
grades["Physics"] = 4
grades["Mathematics"] = 5  # Modification de la valeur existante

print(grades)  # {'mathématiques' : 5, 'physique' : 4}4}

Obtention des valeurs

# Accès direct (provoque une erreur si la clé n'est pas présente)
print(grades["Mathematics"])  # 5

# Réception sécurisée avec valeur par défaut
print(grades.get("Chemistry", 0))  # 0 (pas de clé, la valeur par défaut sera renvoyée)

Suppression d'éléments

del grades["Physics"]  # Supprime la paire clé-valeur

# Ou en utilisant pop (retourne la valeur supprimée)
math_grade = grades.pop("Mathematics")

Vérification de la présence de la clé

if "Physics" in grades:
    print("Physics grade is")
else:
    print("No rating")

Qu'est-ce qu'une table de hachage ?

Une table de hachage est une façon d'implémenter un dictionnaire « sous le capot ». C'est la magie qui permet aux dictionnaires de fonctionner très rapidement.

Comment fonctionne une table de hachage ?

Lorsque vous ajoutez un élément au dictionnaire, voici ce qui se passe :

1. Hachage de la clé : la clé est convertie en un nombre (code de hachage) à l'aide d'une fonction spéciale

2. Détermination de la position : sur la base du code de hachage, l'index dans le tableau est calculé

3. Enregistrement de la valeur : la paire clé-valeur est enregistrée à cet index

# Exemple simplifié d'une fonction de hachage
def simple_hash(key, table_size):
    return sum(ord(char) for char in key) % table_size

# Pour la clé « cat » et la taille de la table 10
hash_value = simple_hash("cat", 10)  # Renvoie un nombre de 0 à 9

Conflits

Parfois, des clés différentes peuvent donner le même hachage. C'est ce qu'on appelle une collision. Il existe plusieurs façons de les résoudre :

Méthode de la chaîne : si deux paires ont le même hachage, elles sont stockées sous forme de liste avec un index.

Adressage ouvert : si la cellule est occupée, la prochaine cellule libre est recherchée.

Complexité des opérations

L'un des principaux avantages des dictionnaires est la vitesse de travail :

• Ajout d'un élément : O (1) en moyenne

• Recherche d'élément : O(1) en moyenne

• Suppression d'un élément : O (1) en moyenne

Cela signifie que le temps d'exécution de l'opération ne dépend pas du nombre d'éléments dans le dictionnaire. À titre de comparaison, la recherche dans une liste prend O(n) temps — vous devez vérifier chaque élément.

Exemples pratiques d'utilisation

Calcul de la fréquence des éléments

text = "hello world"
letter_count = {}

for letter in text:
    if letter in letter_count:
        letter_count[letter] += 1
    else:
        letter_count[letter] = 1

print(letter_count)
# {'h': 1, 'e': 1, 'l': 3, 'o': 2, ' ': 1, 'w': 1, 'r': 1, 'd': 1}

Une façon plus élégante d'utiliser get() :

text = "hello world"
letter_count = {}

for letter in text:
    letter_count[letter] = letter_count.get(letter, 0) + 1

Groupement des données

students = [
    {"name": "Anna", "group": "A"},
    {"name": "Ivan", "group": "B"},
    {"name": "Maria", "group": "A"},
]

groups = {}
for student in students:
    group_name = student["group"]
    if group_name not in groups:
        groups[group_name] = []
    groups[group_name].append(student["name"])

print(groups)
# {'A': ['Anna', 'Maria'], 'B': ['Ivan']}

Mise en cache des résultats

def fibonacci(n, cache={}):
    if n in cache:
        return cache[n]
    
    if n <= 1:
        return n
    
    result = fibonacci(n-1, cache) + fibonacci(n-2, cache)
    cache[n] = result
    return result

print(fibonacci(100))  # Calcul très rapide grâce à la mise en cache

Quand utiliser les dictionnaires ?

Les dictionnaires sont parfaits pour :

• Stockage des paramètres et des configurations

• Calcul de la fréquence des éléments

• Recherche rapide par identifiant unique

• Groupements et agrégations de données

• Mise en cache des calculs

• Représentations des graphes (liste d'adjacence)

Caractéristiques importantes

Les clés doivent être immuables : en Python, les clés peuvent être des chaînes, des nombres, des tuples, mais pas des listes ou d'autres dictionnaires.

# Correct
valid_dict = {
    "name": "value",
    42: "value",
    (1, 2): "value"
}

# Erreur ! Les listes sont modifiables# invalid_dict = {[1, 2] : "value"}

Ordre des éléments : en Python 3.7+, les dictionnaires conservent l'ordre d'ajout des éléments, mais cela ne vaut la peine que si l'ordre est vraiment important.

Productivité : les dictionnaires consomment plus de mémoire que les listes, mais compensent cela par la vitesse d'accès.

Conclusion

Les dictionnaires et les tables de hachage sont des structures de données fondamentales que tout développeur doit comprendre. Ils vous permettent d'organiser efficacement les données et de résoudre de nombreuses tâches pratiques. Comprendre comment ils fonctionnent vous aidera à écrire un code plus rapide et plus efficace.

Commencez à utiliser des dictionnaires dans vos projets et vous apprécierez rapidement leur puissance et leur commodité. Entraînez-vous sur des tâches simples, en les compliquant progressivement, et bientôt le travail avec les dictionnaires deviendra naturel pour vous.

La théorie, c'est bien, mais la vraie compréhension vient de la pratique. Dans l'application Code Des centaines de tâches de programmation de complexité variable vous attendent, y compris des exercices sur le travail avec les dictionnaires, les tables de hachage et d'autres structures de données. Résolvez les problèmes à votre rythme et suivez vos progrès !

Nous avons aussi une communauté vivante dans Telegram! Ici, des développeurs expérimentés aident les débutants, partagent des ressources utiles, discutent de tâches intéressantes et communiquent simplement sur des sujets de programmation. L'ambiance est conviviale et solidaire, chaque question est importante et personne ne sera laissé sans réponse. Rejoignez-nous ! 👋