Comment implémenter une table de hachage en Python

La table de hachage est une structure de données importante et largement utilisée en informatique. Il peut rapidement rechercher, insérer ou supprimer un élément spécifique dans de grandes quantités de données. Utiliser Python pour implémenter une table de hachage peut non seulement vous fournir une compréhension approfondie du mécanisme de fonctionnement interne d'une table de hachage, mais également améliorer vos capacités de programmation. Dans cet article, nous détaillerons comment implémenter une table de hachage en Python.

1. Qu'est-ce qu'une table de hachage

Une table de hachage est également appelée table de hachage, qui est une méthode de stockage clé-valeur. Il accède aux données en mappant la clé sur une position d'index de valeur. Ses opérations de base incluent l'insertion, la suppression et la recherche.

L'idée principale d'une table de hachage est d'utiliser une fonction de hachage pour mapper chaque clé à une table de taille fixe. Une fonction de hachage est une fonction qui convertit un message d'entrée de longueur arbitraire en une sortie de longueur fixe. Les fonctions de hachage courantes incluent MD5, SHA1, SHA256, etc.

2. Implémentation d'une table de hachage

Nous utilisons Python pour implémenter une table de hachage simple, y compris les opérations de base de la table de hachage, telles que l'insertion, Supprimer et rechercher, etc.

Définissez d'abord une classe Node pour représenter le nœud de la table de hachage. Chaque nœud contient une clé et une valeur.

class Node:
    def __init__(self, key, val):
        self.key = key
        self.val = val
        self.next = None

Ensuite, définissons une classe HashTable et nous utilisons la liste de Python pour implémenter la structure de données sous-jacente. Lors de l'insertion d'une paire clé-valeur, nous devons calculer la valeur de hachage en fonction de la clé et stocker la paire clé-valeur à l'emplacement correspondant dans la table de hachage.

class HashTable:
    def __init__(self):
        self.size = 100
        self.table = [None] * self.size
        
    def hash_func(self, key):
        return sum([ord(c) for c in key]) % self.size
    
    def insert(self, key, value):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            self.table[hash_value] = Node(key, value)
        else:
            cur = self.table[hash_value]
            while cur.next is not None:
                cur = cur.next
            cur.next = Node(key, value)
    
    def search(self, key):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            return None
        else:
            cur = self.table[hash_value]
            while cur is not None:
                if cur.key == key:
                    return cur.val
                else:
                    cur = cur.next
            return None
    
    def delete(self, key):
        hash_value = self.hash_func(key)
        if self.table[hash_value] is None:
            return
        elif self.table[hash_value].key == key:
            self.table[hash_value] = self.table[hash_value].next
        else:
            cur = self.table[hash_value]
            while cur.next is not None:
                if cur.next.key == key:
                    cur.next = cur.next.next
                    return
                else:
                    cur = cur.next

Dans le code ci-dessus, la méthode hash_func calcule la valeur de hachage en fonction de la clé, la méthode d'insertion insère la paire clé-valeur dans la position correspondante dans la table de hachage, la méthode de recherche trouve la valeur en fonction de la clé et de la méthode delete Supprimez la paire clé-valeur correspondante en fonction de la clé.

3. Test de la table de hachage

Ensuite, nous testons la table de hachage implémentée ci-dessus.

ht = HashTable()
ht.insert('apple', 2.5)
ht.insert('banana', 1.3)
ht.insert('orange', 0.7)

print(ht.search('apple')) # 2.5
print(ht.search('banana')) # 1.3
print(ht.search('orange')) # 0.7
print(ht.search('lemon')) # None

ht.delete('apple')
print(ht.search('apple')) # None

Dans le code ci-dessus, nous créons un objet HashTable ht et insérons trois paires clé-valeur dans ht. Ensuite, nous utilisons la méthode de recherche pour trouver des valeurs avec les clés « pomme », « banane » et « orange », et supprimons une paire clé-valeur avec la clé « pomme ». Enfin, nous recherchons la valeur avec la clé « pomme », qui devrait renvoyer Aucun.

4. Summary

Cet article présente comment implémenter une table de hachage en Python. Nous avons défini une classe Node pour représenter un nœud de la table de hachage, puis défini une classe HashTable pour représenter la table de hachage et implémenté les opérations de base de la table de hachage, telles que l'insertion, la suppression et la recherche. En implémentant une table de hachage, nous pouvons comprendre en profondeur le mécanisme de fonctionnement interne de la table de hachage et améliorer nos capacités de programmation.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!