Chaîne de hachage que je voulais éviter (1)
Bonsoir (* ´ω ｀) Le titre a une voix de mon cœur (rires) Je pense que c'était difficile pour les gens qui étudiaient pour la première fois, y compris moi-même. Rendez-le aussi facile à comprendre que possible et passons à l'action.
J'ai préparé à la hâte un arrangement approprié.
À partir de maintenant, nous stockerons les données appropriées dans le tableau suivant.
Normalement, les données sont stockées dans l'ordre à partir du pointeur 0 (= x [0]), mais changeons le goût cette fois.
La chaîne Hash à contester cette fois
** Une seule donnée peut être stockée à une seule adresse,
N'est-il pas possible d'en emballer plus? !! ** (Est-ce un peu rugueux ...)
Si vous regardez les matériaux d'experts, vous verrez souvent les chiffres suivants.
Si c'est x [0], il semble que les données sont liées et connectées par un total de trois chaînes.
Quand je l'ai vu pour la première fois, j'ai trouvé que c'était très agréable, c'est incroyable de pouvoir faire ça !!
Mais comment l'écrivez-vous? (; ´ ･ ω ･)
Commençons par la définition de base de Hash. Comment décidez-vous du pointeur de destination de stockage? Oui, c'est ça.
** "Entier spécifié par l'utilisateur"% de la longueur du tableau **
Par exemple, si vous entrez ** 14 **, la longueur du tableau préparé cette fois est 7, donc 0 apparaîtra. OK, alors que voulez-vous stocker dans x [0]?
Pour le moment, mettons également ** 1 **. Non, arrêtez !! x [0] Non seulement 1 est stocké, ** 14 ** est également stocké ensemble!
Les questions viendront à mort, mais continuons.
Comme le titre l'indique, c'est une chaîne, alors saisissons l'adresse de la destination de la connexion !!
Si clé = 14, valeur = 1, np (pointeur suivant) = aucun, la figure ci-dessous sera obtenue.
Alors, que se passe-t-il si key = 21 dans l'entrée suivante?
21%7 = 0
Aussi ** 0 ** ('Д')
Que devrais-je faire. .. ..
Si vous avez un problème, essayez de l'écrire pour le moment et cela changera votre humeur.
test.py
class Node:
def __init__(self,key,value,next):
self.key = key #Tout entier saisi par l'utilisateur
self.value = value #Valeur que vous souhaitez stocker
self.np = np # next pointer
Défini comme Node, il a trois arguments. Préparons un tableau pour stocker ce nœud.
test.py
class ChainedHash:
def __init__(self,capacity):
self.capacity = capacity #Puisqu'il s'agit de la longueur du tableau, nous remplacerons 7 plus tard.
self.table = [None]*self.capacity #Nommez le tableau qui stocke la table Nodes
Par exemple, attribuez key = 14, value = 1, np = None à Node selon le cas, Attribuez-le ensuite à la table [0] et imprimez-le. Ensuite, j'ai été surpris de voir ce qui suit.
test.py
[<__main__.Node object at 0x00000282E2DA9D60>, None, None, None, None, None, None]
Quel est le problème avec l'affectation de Node à la table [0]? Quand je l'ai vu pour la première fois, j'ai failli tomber (rires) Mais maintenant que j'y pense, je pense que c'est aussi l'un des moyens de constituer la chaîne.
Par exemple, que pensez-vous lorsque vous voyez cette description?
test.py
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
Ajoutez la clé, la valeur et self.table [Vhash] au nœud préparé au début. Remplacez et attribuez à temp. clé et valeur sont les valeurs que vous êtes sur le point d'entrer. Mais self.table [Vhash], qu'est-ce que c'est? Oui, c'est la valeur stockée à l'origine dans la table [0]. Bien sûr, la valeur de la table [0] qui a été stockée à l'origine a clé, valeur, self.table [Vhash]. Il est stocké (la valeur initiale de la table [0] est None). Qu'est-ce que ça veut dire. .. J'ai fait une image pour compléter la mauvaise explication.
La première chose que j'ai écrite est A parce que les données (clé, valeur, np) sont longues. Après cela, j'ai écrit des données dans x [0] comme B, mais regardez le np de B dans la figure. Les données de A elles-mêmes sont-elles intégrées? ?? Par conséquent, lorsque vous saisissez enfin le contenu de la valeur B stockée dans la table [0], vous pouvez également voir la valeur suivante de A. Si vous continuez le processus d'incorporation de données dans les données de cette manière, ne voyez-vous pas beaucoup de données connectées? Au cas où, veuillez revoir la description avec l'explication ci-dessus à l'esprit.
test.py
# ↓ Data A = self.table[0]
temp = Node(key,value,self.table[Vhash])
#self.table[0]Clé nouvellement préparée+ value +Données A dans un package et attribuées
self.table[Vhash] = temp
#À partir du tableau ci-dessus[0]La valeur de est mise à jour de A à B
Droite? (Lol) Une seule donnée est écrite sur une seule adresse, Parce que les données sont intégrées dans les données, comme une chaîne On dirait qu'ils sont connectés. C'est intéressant (≧ ▽ ≦)
Avec cette image, la suivante est plus facile. Avant d'intégrer des données À l'origine, la table [0] a besoin d'une description pour vérifier s'il y a des données en double, non? Ce sera peut-être comme ça.
test.py
def add(self,key,value):
Vhash = key % self.capacity #Calculer quel pointeur spécifier dans le tableau
p = self.table[Vhash] #Si c'est 0, table[0]Remplacez la valeur de en p
#Où p est la clé,value,Contient np
while p is not None:
#p.key extrait uniquement la clé en p
#p.Si la clé est équivalente à la clé que vous avez saisie cette fois
#Il ne peut pas être utilisé car il est dupliqué, il renvoie donc False.
if p.key == key:
return False
#Appelez np à l'intérieur de p,
#Clé de données intégrée, value,Réaffectez np à p.
p = p.np
#Revenez à tout au début et continuez jusqu'à ce que
#Vérifiez les clés en double.
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
Eh bien, je suis enfin là. Je vais résumer l'image dans son ensemble.
test.py
class Node:
def __init__(self,key,value,np):
self.key = key
self.value = value
self.np = np
class ChainedHash:
def __init__(self,capacity):
self.capacity = capacity
self.table = [None]*self.capacity
def add(self,key,value):
Vhash = key % self.capacity
p = self.table[Vhash]
while p is not None:
if p.key == key:
return False
p = p.np
temp = Node(key,value,self.table[Vhash])
self.table[Vhash] = temp
def dump(self):
for i in range(self.capacity):
p = self.table[i]
print(i,end="")
while p is not None:
print(f"=>{p.key}({p.value})",end="")
p = p.np
print()
test = ChainedHash(7)
while True:
num = int(input("select 1.add, 2.dump "))
if num == 1:
key = int(input("key: "))
val = int(input("val: "))
test.add(key,val)
elif num == 2:
test.dump()
else:
break
Résultat d'exécution.py
select 1.add, 2.dump 1# 1.Sélectionnez ajouter
key: 7
val: 1
select 1.add, 2.dump 1 # 1.Sélectionnez ajouter
key: 14
val: 2
select 1.add, 2.dump 2# 2.Sélectionnez le vidage
0=>14(2)=>7(1) #Achèvement de la chaîne('Д')!!
1
2
3
4
5
6
Eh bien, je suis désolé pour la longue explication. La suite continue à cela (2) ...
Recommended Posts