
Mise en œuvre d'une table de hachage bidirectionnelle efficace
Une table de hachage ou une structure de données de dictionnaire offre une indexation et une récupération efficaces des valeurs par clés. Cependant, il est parfois souhaitable d'indexer également par valeurs. Une table de hachage bidirectionnelle permet une indexation basée sur des clés et des valeurs.
Implémentation personnalisée à l'aide d'une classe bidirectionnelle
L'implémentation Python dict fournit un mappage unidirectionnel à partir des clés aux valeurs. Pour créer une table de hachage bidirectionnelle, nous pouvons créer notre propre classe qui hérite de la classe dict :
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | <code class = "python" > class bidict(dict):
def __init__(self, *args, **kwargs):
super(bidict, self).__init__(*args, **kwargs)
self.inverse = {}
for key, value in self.items():
self.inverse.setdefault(value, []).append(key)
def __setitem__(self, key, value):
if key in self:
self.inverse[self[key]].remove(key)
super(bidict, self).__setitem__(key, value)
self.inverse.setdefault(value, []).append(key)
def __delitem__(self, key):
self.inverse.setdefault(self[key], []).remove(key)
if self[key] in self.inverse and not self.inverse[self[key]]:
del self.inverse[self[key]]
super(bidict, self).__delitem__(key)</code>
|
Copier après la connexion
Principales caractéristiques :
- L'attribut inverse maintient un mappage des valeurs vers une liste de clés.
- Lorsqu'une paire clé-valeur est ajoutée, le mappage inverse est mis à jour automatiquement.
- Lorsqu'une clé est supprimée, le mappage inverse est également mis à jour pour supprimer la clé.
- La nature bidirectionnelle permet à la fois l'accès d[key] et d[value].
- Elle permet à plusieurs clés d'avoir la même valeur.
Exemple d'utilisation :
1 2 3 4 5 6 7 8 | <code class = "python" >bd = bidict({ 'a' : 1, 'b' : 2})
print (bd) # { 'a' : 1, 'b' : 2}
print (bd.inverse) # {1: [ 'a' ], 2: [ 'b' ]}
bd[ 'c' ] = 1 # Two keys have the same value
print (bd) # { 'a' : 1, 'c' : 1, 'b' : 2}
print (bd.inverse) # {1: [ 'a' , 'c' ], 2: [ 'b' ]}</code>
|
Copier après la connexion
Avantages :
Cette implémentation combine l'efficacité de la structure de données dict de Python avec la flexibilité de accès bidirectionnel. C'est un outil puissant pour diverses applications où une indexation basée sur les valeurs est nécessaire.
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!