Comment écrire un algorithme de recherche de hachage en Python ?

Comment écrire un algorithme de recherche de hachage en Python ?

L'algorithme de recherche de hachage, également connu sous le nom d'algorithme de recherche de hachage, est une méthode de recherche de données basée sur une table de hachage. Comparé aux algorithmes de recherche traditionnels tels que la recherche linéaire et la recherche binaire, l'algorithme de recherche par hachage a une efficacité de recherche plus élevée. En Python, nous pouvons utiliser un dictionnaire pour implémenter une table de hachage, puis implémenter une recherche de hachage.

L'idée de base de l'algorithme de recherche de hachage est de convertir le mot-clé à rechercher en valeur d'index via une fonction de hachage, puis de rechercher les données correspondantes dans la table de hachage en fonction de la valeur d'index. Dans une table de hachage, chaque valeur d'index correspond à un compartiment et chaque compartiment stocke un ou plusieurs mots-clés. Des conflits se produisent lorsque plusieurs mots-clés correspondent à la même valeur d'index. Afin de résoudre les conflits, une méthode courante consiste à utiliser la méthode d'adresse en chaîne pour lier des mots-clés en conflit dans une liste chaînée.

Ce qui suit est un exemple d'algorithme de recherche de hachage simple écrit en Python :

class HashTable:
    def __init__(self):
        self.size = 10
        self.table = [[] for _ in range(self.size)]  # 使用列表作为哈希表的桶
    
    def _hash_function(self, key):
        return key % self.size  # 哈希函数采用取余方式
    
    def insert(self, key, value):
        index = self._hash_function(key)
        self.table[index].append((key, value))  # 将关键字和值作为一个元组插入哈希表桶中
    
    def search(self, key):
        index = self._hash_function(key)
        for item in self.table[index]:
            if item[0] == key:
                return item[1]  # 返回关键字对应的值
        return None  # 若关键字不存在，则返回None

# 示例用法
hash_table = HashTable()
hash_table.insert(1, 'apple')
hash_table.insert(2, 'banana')
hash_table.insert(11, 'orange')

print(hash_table.search(1))  # 输出: apple
print(hash_table.search(2))  # 输出: banana
print(hash_table.search(3))  # 输出: None
print(hash_table.search(11)) # 输出: orange

Dans l'exemple ci-dessus, nous définissons une classe de table de hachageHashTable, qui contient des fonctions de hachage, des opérations d'insertion et de recherche. La fonction de hachage utilise une méthode de reste simple pour convertir le mot-clé en valeur d'index correspondante. L'opération d'insertion insère la clé et la valeur sous forme de tuple dans le compartiment correspondant à l'index. L'opération de recherche parcourt le compartiment de l'index correspondant, trouve le tuple correspondant au mot-clé et renvoie la valeur correspondante. Si le mot-clé n'existe pas, None est renvoyé.

Grâce à l'exemple ci-dessus, nous pouvons voir l'implémentation simple de l'algorithme de recherche de hachage. En pratique, des fonctions de hachage et des méthodes de résolution de conflits plus complexes peuvent être sélectionnées en fonction de besoins spécifiques et des caractéristiques des données. Dans le même temps, des opérations telles que l'expansion dynamique de la table de hachage peuvent également être effectuées pour améliorer l'efficacité de la recherche.

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!