Cette fois, je vais vous expliquer la méthode de hachage. C'est juste pour ma propre compréhension, donc je suis facile à expliquer où je suis satisfait de ce niveau de compréhension, et d'un autre côté, j'explique les parties qui ont pris du temps à comprendre. Veuillez noter que.

Quelle est la méthode de hachage?

La méthode de hachage est un algorithme qui peut efficacement ajouter et supprimer des éléments ainsi que la recherche. Lors de l'examen d'un certain tableau, pour ajouter un élément, il est nécessaire d'insérer après avoir effectué une recherche et de décaler tous les éléments derrière lui, de sorte que le coût de traitement est étonnamment élevé. Alors utilisons cette méthode de hachage.

La ** table de hachage ** est un tableau qui stocke les clés de sorte que la valeur de hachage soit un indice. Par exemple, considérons une table de hachage avec le reste divisé par 13 comme valeur de hachage.

Clé	5	6	14	20	29	34	37	51	69	75
valeur	M. Yamamoto	Nozaki	M. Takahashi	Suzuki	M. Hashimoto	M. Hasegawa	Ogawa	M. Sato	1er avril	Brian
Valeur de hachage(Résiduel divisé par 13)	5	6	1	7	3	8	11	12	4	10

Dans ce cas, mettez M. Yamamoto dans un [5], M. Nozaki dans un [6], M. Takahashi dans un [1], et ainsi de suite. Bien entendu, il n'est pas nécessaire de renseigner tous les éléments du tableau préparé. Par exemple, un [0] vaut None ici. De plus, chaque élément du tableau a qui apparaît ici est appelé un ** bucket **.

Méthode d'adresse ouverte

La méthode d'adresse ouverte est une méthode de re-hachage jusqu'à ce qu'il n'y ait pas de collision lorsque des conflits de valeurs de hachage se produisent. Le réhachage est effectué si nécessaire lors de l'exploration, l'ajout ou la suppression d'éléments.

Ajouter un élément

Clé	5	6	14	20	29	34	37	51	69	75
valeur	M. Yamamoto	Nozaki	M. Takahashi	Suzuki	M. Hashimoto	M. Hasegawa	Ogawa	M. Sato	1er avril	Brian
Valeur de hachage(Résiduel divisé par 13)	5	6	1	7	3	8	11	12	4	10

Tableau	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]	a[11]	a[12]
valeur	None	M. Takahashi	None	M. Hashimoto	1er avril	M. Yamamoto	Nozaki	Suzuki	M. Hasegawa	None	Brian	Ogawa	M. Sato

Si vous ajoutez (key: 18, Value: Johnny) à ce tableau, la valeur de hachage est 18% 13 = 5, donc il est déjà rempli avec Mr. Yamamoto. Alors répétez-le comme (18 + 1)% 13 = 6. Ceci est également rempli de Nozaki-kun, donc encore une fois, 7 est également rempli de Suzuki-kun, donc encore une fois ... Comme il n'y a pas d'élément avec une clé avec une valeur de hachage de 9, j'ai finalement réussi à ajouter Johnny à un [9]. Fait.

Tableau	a[0]	a[1]	a[2]	a[3]	a[4]	a[5]	a[6]	a[7]	a[8]	a[9]	a[10]	a[11]	a[12]
valeur	None	M. Takahashi	None	M. Hashimoto	1er avril	M. Yamamoto	Nozaki	Suzuki	M. Hasegawa	Johnny	Brian	Ogawa	M. Sato

Supprimer l'élément

Maintenant, comment supprimer un élément? Par exemple, supposons que vous supprimiez Yamamoto de ce tableau. Si je le supprimais simplement, la recherche de Johnny le trouverait ici dans ʻa [9] suite au rehash, mais la valeur de hachage d'origine était 5. Par conséquent, la valeur de la valeur de hachage 5 ne sera pas trouvée et la recherche échouera. Si ʻa [5] est vide depuis le début, il est normal d'échouer la recherche, mais une fois qu'elle a été supprimée, peut-être que la valeur que vous voulez rechercher plus tard est remplie par rehachage. droite. Par conséquent, afin de porter un jugement sur cette zone, chaque compartiment du tableau peut avoir trois états «EMPTY, OCCUPIED et DELETED». De cette façon, lors de la recherche de la valeur de la clé 18, ʻa [5] est dans l'état DELETED`, donc vous pouvez recommencer et continuer la recherche.

Classe 1

class Status(Enum):
    OCCUPIED = 0
    EMPTY = 1
    DELETED = 2

Définit l'état du compartiment. En langage C

#define OCCUPIED 0
#define EMPTY 1
#define DELETED 2

C'est la même chose que

Classe 2

class Bucket:
    #Les seaux qui composent le hachage

    def __init__(self, key: Any = None, value: Any = None, stat: Status = Status.EMPTY) -> None:
        self.key = key
        self.value = value
        self.stat = stat
    def set(self, key: Any, value: Any, stat: Status) -> None:
        self.key = key
        self.value = value
        self.stat = stat
    def set_status(self, stat: Status) -> None:
        self.stat = stat

Cette classe crée une instance du bucket. Une instance de bucket est essentiellement un élément individuel du tableau que nous avons vu précédemment. Chacun de ces éléments a trois attributs: clé, valeur et état.

Classe 3

class OpenHash:
    
    def __init__(self, capacity: int) -> None:
        """Initialisation"""
        self.capacity = capacity
        self.table = [Bucket()] * self.capacity

    def hash_value(self, key: Any) -> int:
        """Trouver la valeur de hachage à partir de la clé"""
        if isinstance(key, int):
            return key % self.capacity
        return (int(hashlib.md5(str(key).encode()).hexdigest(), 16) % self.capacity)

    def rehash_value(self, key: Any) -> int:
        """Rehash et renvoyer la valeur de hachage"""
        return (self.hash_value(key) + 1) % self.capacity

    def search_node(self, key: Any) -> Any:
        """Rechercher des buckets dont la clé est la clé"""
        hash = self.hash_value(key)
        p = self.table[hash] #Le seau de hachage va dans p.
        for i in range(self.capacity): #Boucle pour le nombre de compartiments dans le tableau
            if p.stat == Status.EMPTY: #Si le seau est vide, cela signifie que rien ne s'y trouvait depuis le début, alors cassez et retournez Aucun
                break
            elif p.stat == Status.OCCUPIED and p.key == key: #Si vous trouvez un bucket avec la clé que vous voulez trouver, renvoyez ce bucket
                return p
            hash = self.rehash_value(hash)
            p = self.table[hash]
        return None 

    def search(self, key: Any) -> Any:
        """Recherchez l'élément avec la clé clé et renvoyez la valeur"""
        p = self.search_node(key)
        if p is not None:
            return p.value
        else:
            return None
    
    def add(self, key: Any, value: Any) -> bool:
        """Ajouter un élément dont la clé est la clé et dont la valeur est la valeur"""
        if self.search(key) is not None:
            return False
        hash = self.hash_value(key)
        p = self.table[hash]
        for i in range(self.capacity):
            if p.stat == Status.EMPTY or p.stat == Status.DELETED:
                self.table[hash] = Bucket(key, value, Status.OCCUPIED)
                return True
            hash = self.rehash_value(hash)
            p = self.table[hash]
        return False

    def remove(self, key: Any) -> int:
        """Supprimer l'élément avec la clé"""
        p = self.search_node(key)
        if p is None:
            return False
        p.set_status(Status.DELETED)
        return True
    
    def dump(self) -> None:
        """Vider la table de hachage"""
        for i in range(self.capacity):
            print(f'{i:2} ', end = '')
            if self.table[i].stat == Status.OCCUPIED:
                print(f'{self.table[i].key} ({self.table[i].value})')
            elif self.table[i].stat == Status.EMPTY:
                print('---Non enregistré---')
            elif self.table[i].stat == Status.DELETED:
                print('---supprimé---')

J'ai mentionné plus tôt qu'essayer de trouver la valeur de key: 18 après la suppression d'un [5] échouera, mais voyons comment cela est évité.

    def search_node(self, key: Any) -> Any:
        """Rechercher des buckets dont la clé est la clé"""
        hash = self.hash_value(key)
        p = self.table[hash] #Le seau de hachage va dans p.
        for i in range(self.capacity): #Boucle pour le nombre de compartiments dans le tableau
            if p.stat == Status.EMPTY: #Si le seau est vide, cela signifie que rien ne s'y trouvait depuis le début, alors cassez et retournez Aucun
                break
            elif p.stat == Status.OCCUPIED and p.key == key: #Si vous trouvez un bucket avec la clé que vous voulez trouver, renvoyez ce bucket
                return p
            hash = self.rehash_value(hash)
            p = self.table[hash]
        return None

Lors de la recherche, search_node (key) est appelé à partir de search (key), qui est une méthode pour renvoyer le bucket avec la clé. Si vous donnez 18 à search () comme clé, la recherche commencera pour ʻa [5] . Puisqu'il s'agit d'un état DELETE, nous allons re-hacher via ʻif et ʻelifet cibler ʻa [(18 + 1)% 13]. En répétant ceci, vous pouvez éventuellement trouver Johnny dans ʻa [9] `.

finalement

Voyons en fait un exemple d'utilisation de la classe ci-dessus.


from enum import Enum
Menu = Enum('Menu', ['ajouter à', 'Effacer', 'chercher', 'déverser', 'Fin'])

def select_menu() -> Menu:
    """Sélection de menu"""
    s = [f'({m.value}){m.name}'for m in Menu]
    while True:
        print(*s, sep=' ', end='')
        n = int(input(' : '))
        if 1 <= n <= len(Menu):
            return Menu(n)
        
hash = OpenHash(13)

while True:
    menu = select_menu()
    
    if menu == Menu.ajouter à:
        key = int(input('Clé: '))
        val = input('valeur: ')
        if not hash.add(key, val):
            print('Échec de l'addition')
            
    elif menu == Menu.Effacer:
        key = int(input('Clé: '))
        if not hash.remove(key):
            print('Supprimer l'échec')
            
    elif menu == Menu.chercher:
        key = int(input('Clé: '))
        t = hash.search(key)
        if t is not None:
            print(f'La valeur avec cette clé est{t}est.')
        else:
            print('Il n'y a pas de données applicables.')
    elif menu == Menu.déverser:
        hash.dump()
    else:
        break

Entrée et sortie ci-dessous

(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 5
valeur:M. Yamamoto
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 6
valeur:Nozaki
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 14
valeur:M. Takahashi
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 20
valeur:Suzuki
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 29
valeur:M. Hashimoto
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 34
valeur:M. Hasegawa
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 37
valeur:Ogawa
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 51
valeur:M. Sato
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 69
valeur:1er avril
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 75
valeur:Brian
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 4
 0 ---Non enregistré---
 1 14 (M. Takahashi)
 2 ---Non enregistré---
 3 29 (M. Hashimoto)
 4 69 (1er avril)
 5 5 (M. Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (M. Hasegawa)
 9 ---Non enregistré---
10 75 (Brian)
11 37 (Ogawa)
12 51 (M. Sato)
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 5
valeur:Johnny
Échec de l'addition!
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 4
 0 ---Non enregistré---
 1 14 (M. Takahashi)
 2 ---Non enregistré---
 3 29 (M. Hashimoto)
 4 69 (1er avril)
 5 5 (M. Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (M. Hasegawa)
 9 ---Non enregistré---
10 75 (Brian)
11 37 (Ogawa)
12 51 (M. Sato)
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 5

Cela ... Quand j'ai essayé d'ajouter Johnny à M. Yamamoto, l'ajout a échoué. Dans la méthode d'adresse ouverte, même si ʻa [5] `est rempli, il devrait être reformulé et d'une manière ou d'une autre rempli à moins que tous les éléments ne soient pleins ...

Le problème semble être dans ʻadd () `

if self.search(key) is not None:

Voilà la partie.

if self.search(key) == value:

Je vais le réécrire et réessayer.

(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 5
valeur:M. Yamamoto
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 6
valeur:Nozaki
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 14
valeur:M. Takahashi
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 20
valeur:Suzuki
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 29
valeur:M. Hashimoto
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 34
valeur:M. Hasegawa
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 37
valeur:Ogawa
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 51
valeur:M. Sato
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 69
valeur:1er avril
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 75
valeur:Brian
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 4
 0 ---Non enregistré---
 1 14 (M. Takahashi)
 2 ---Non enregistré---
 3 29 (M. Hashimoto)
 4 69 (1er avril)
 5 5 (M. Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (M. Hasegawa)
 9 ---Non enregistré---
10 75 (Brian)
11 37 (Ogawa)
12 51 (M. Sato)
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 1
Clé: 18
valeur:Johnny
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 4
 0 ---Non enregistré---
 1 14 (M. Takahashi)
 2 ---Non enregistré---
 3 29 (M. Hashimoto)
 4 69 (1er avril)
 5 5 (M. Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (M. Hasegawa)
 9 18 (Johnny)
10 75 (Brian)
11 37 (Ogawa)
12 51 (M. Sato)
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 2
Clé: 5
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 4
 0 ---Non enregistré---
 1 14 (M. Takahashi)
 2 ---Non enregistré---
 3 29 (M. Hashimoto)
 4 69 (1er avril)
 5 ---supprimé---
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (M. Hasegawa)
 9 18 (Johnny)
10 75 (Brian)
11 37 (Ogawa)
12 51 (M. Sato)
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 3
Clé: 18
La valeur avec cette clé est Johnny.
(1)ajouter à(2)Effacer(3)chercher(4)déverser(5)Fin: 5

Johnny a été ajouté en toute sécurité et j'ai réussi à rechercher Johnny après la suppression de M. Yamamoto.

[Livres de référence](https://www.amazon.co.jp/ Algorithmes et structures de données appris avec Python nouveau et clair-Nouvelle série claire-Nobuhiro Shibata / dp / 4815603197 / ref = pd_sbs_14_t_1 / 355-2283754-9134449 ? _encoding = UTF8 & pd_rd_i = 4815603197 & pd_rd_r = fdf0f7d2-76c5-4384-94b0-860a83839a41 & pd_rd_w = ELFk0 & pd_rd_wg = 8xj9G & pf_rd_p = ca22fd73-0f1e-4b39-9917-c84a20b3f3a8 & pf_rd_r = 3F77WDCW3H4HF22R94GE & psc = 1 & refRID = 3F77WDCW3H4HF22R94GE)

[GO] Méthode Hash (méthode d'adresse ouverte) en Python