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. 図1.PNG 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. 図2.PNG 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. 図3.PNG 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.

図4.PNG

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

Chaîne de hachage que je voulais éviter (2)
Chaîne de hachage que je voulais éviter (1)
Je voulais faire évoluer cGAN vers ACGAN
Je voulais résoudre ABC160 avec Python
Je voulais résoudre ABC159 avec Python
Je voulais résoudre ABC172 avec Python
Je voulais vraiment copier avec du sélénium
Implémentation de DQN avec TensorFlow (je voulais ...)
Je voulais résoudre NOMURA Contest 2020 avec Python
Scraping de pages i-Town: je voulais prendre la place de Wise-kun
Je voulais jouer avec la courbe de Bézier
Je voulais installer Python 3.4.3 avec Homebrew + pyenv
Je voulais juste comprendre le module Pickle de Python
Je voulais aussi vérifier les indices de type avec numpy
J'ai commencé à analyser
Je voulais utiliser la bibliothèque Python de MATLAB
J'ai essayé de déboguer.
Une histoire sur la volonté de modifier un peu le site d'administration de Django
J'ai essayé de créer automatiquement un rapport avec la chaîne de Markov
[Chaîne de Markov] J'ai essayé de charger des émotions négatives dans Python.
[Chaîne de Markov] J'ai essayé de lire les citations en Python.
Je voulais m'inquiéter du temps d'exécution et de l'utilisation de la mémoire
Je voulais supprimer plusieurs objets en s3 avec boto3
J'ai essayé d'organiser SVM.
J'ai parlé à Raspberry Pi
J'ai essayé d'implémenter PCANet
Introduction à l'optimisation non linéaire (I)
J'ai appliqué LightFM à Movielens
Je veux résoudre SUDOKU
J'ai essayé de réintroduire Linux
J'ai essayé de présenter Pylint
J'ai essayé de résumer SparseMatrix
J'ai essayé d'implémenter StarGAN (1)
Je voulais le faire comme exécuter un cas de test pour AtCoder.
Je voulais créer une présentation intelligente avec Jupyter Notebook + nb present
Je voulais convertir ma photo de visage en un style Yuyu.
Je voulais contester la classification du CIFAR-10 en utilisant l'entraîneur de Chainer
Je voulais résoudre le problème ABC164 A ~ D avec Python
Ce que j'ai fait quand je voulais rendre Python plus rapide -Édition Numba-
[Django] Je voulais tester lors du POST d'un fichier volumineux [TDD]