Tableaux et tables de hachage

word_counts = {
  "hello": 42,
  "world": 37,
  "AI": 156
}

Besoin du compteur pour "AI" ? La hash map utilise une hash function pour convertir la clé en index en coulisses. Résultat : un temps de recherche moyen en O(1) - comme les tableaux, mais avec des noms au lieu de numéros.

Utilisations en IA

• Correspondance de vocabulaire : transformer des mots comme « brilliant » en token ID 8921 pour un modèle de langage.
• Comptage de fréquences : combien de fois chaque mot apparaît-il dans un jeu de données ? Une hash map répond en un seul passage.
• Mise en cache : si une prédiction a déjà été calculée pour une entrée X, on la stocke pour ne jamais la recalculer.

Complexité temporelle en bref

| Opération | Tableau | Hash Map | |-----------|---------|----------| | Accès par index | O(1) ⚡ | N/A | | Accès par clé | O(n) 🐢 | O(1) ⚡ | | Insertion en fin | O(1) ⚡ | O(1) ⚡ | | Insertion au milieu | O(n) 🐢 | N/A | | Recherche d'une valeur | O(n) 🐢 | O(1) ⚡ |

Retenez : O(1) signifie « instantané, quelle que soit la taille » et O(n) signifie « plus les données sont volumineuses, plus c'est lent ».

Patron classique : comptage de fréquences

L'un des patrons les plus utiles en entretien comme en IA est le comptage d'occurrences :

counts = {}
for each word in text:
    if word in counts:
        counts[word] = counts[word] + 1
    else:
        counts[word] = 1

Un seul passage dans le texte donne la fréquence de chaque mot. Les modèles de langage utilisent exactement cette approche (à grande échelle) pour comprendre quels mots comptent le plus.

Patron classique : le problème Two-Sum

Étant donné un tableau de nombres et une cible, trouvez deux nombres dont la somme égale la cible. L'approche naïve vérifie toutes les paires - O(n²). L'approche astucieuse utilise une hash map :

seen = {}
for each number in array:
    complement = target - number
    if complement in seen:
        return [seen[complement], current_index]
    seen[number] = current_index

Un seul passage, en O(n). La hash map mémorise ce qu'on a déjà vu.

Quand choisir quoi

• Utilisez un tableau quand l'ordre compte, quand vous accédez par position ou quand vous traitez tout séquentiellement (comme les pixels d'une image).
• Utilisez une hash map quand vous avez besoin de recherches rapides par clé, de comptage d'occurrences ou de vérifier rapidement l'existence d'un élément.

Points clés à retenir

• Les tableaux offrent un accès en O(1) par index et sont la colonne vertébrale de l'IA numérique (images, embeddings, tenseurs).
• Les hash maps offrent un accès en O(1) par clé et sont indispensables pour les recherches, le comptage et la mise en cache.
• Choisir la bonne structure peut transformer un algorithme O(n²) en O(n) - une différence capitale quand on traite des millions de données.
• En pratique, la plupart des pipelines d'IA utilisent les deux : tableaux pour le calcul numérique, hash maps pour les métadonnées.