Présentation du projet

Ce projet consiste à concevoir une liste de contacts efficace, capable de gérer un grand nombre de données. Dans un contexte réel, comme les contacts Google ou les bases de données d’entreprises, le nombre de fiches peut atteindre plusieurs milliers, voire des dizaines de milliers. Il est donc indispensable d’utiliser une structure de données performante.

Problématique

Le problème principal est le suivant : comment stocker et retrouver rapidement un contact à partir de son nom, sans devoir parcourir toute la liste à chaque recherche ? Une recherche dans une liste simple aurait une complexité en O(n), ce qui devient trop lent lorsque le nombre de contacts augmente.

Solution retenue : la table de hachage

Pour résoudre ce problème, j’ai utilisé une table de hachage codée manuellement. Le principe consiste à transformer le nom du contact en un indice grâce à une fonction de hachage. Cela permet d’accéder directement à la bonne zone de stockage, sans parcourir toute la structure.

La fonction de hachage parcourt chaque caractère du nom, transforme les caractères en valeurs numériques, puis calcule un indice. Les collisions, c’est-à-dire lorsque deux noms donnent le même indice, sont gérées à l’aide de listes chaînées.

Complexité algorithmique

Grâce à la table de hachage, les opérations principales — ajout, recherche et suppression — sont réalisées en temps constant en moyenne, c’est-à-dire en O(1). Dans le pire des cas, lorsqu’il y a beaucoup de collisions, la complexité peut atteindre O(n), mais ce cas reste rare si la table est bien dimensionnée.

Bilan et conclusion

Ce projet met en évidence l’importance du choix des structures de données. Grâce à l’utilisation d’une table de hachage dynamique, il est possible de gérer efficacement un grand nombre de contacts tout en garantissant des temps d’accès très courts. Ce type de structure est largement utilisé dans les applications professionnelles et les bases de données réelles.

FACTEUR_MAX = 0.75

taille = 10000
contacts = [[] for t in range(taille)]
nb_elements = 0

def hash_cle(clef):
    h = 0
    for c in clef:
        h += ord(c)
    return h % taille


def ajouter_contact(nom, tel):
    nb_elements = 0

    indice = hash_cle(nom)
    contacts[indice].append([nom, tel])
    nb_elements += 1
    for contact in contacts[indice]:
        if contact[0] == nom:
            contact[1] = tel
            return contacts

def rechercher_contact(nom):
    indice = hash_cle(nom)
    for contact in contacts[indice]:
        if contact[0] == nom:
            return contact[1]
    return print("le contact n'existe pas")

def supprimer_contact(nom):

    indice = hash_cle(nom)
    for i in range(len(contacts[indice])):
        if contacts[indice][i][0] == nom:
            contacts[indice].pop(i)
            nb_elements -= 1
            return contacts


print(rechercher_contact("Ethan"))
ajouter_contact("Ethan", "0102030405")
print(rechercher_contact("Ethan"))