Dieses Mal werde ich die Hash-Methode erklären. Es ist nur für mein eigenes Verständnis, also bin ich einfach zufrieden mit dem Teil, den ich mit dieser Ebene des Verstehens zufrieden bin, und andererseits erkläre ich den Teil, dessen Verständnis lange gedauert hat. Bitte beachte, dass.

Was ist die Hash-Methode?

Die Hash-Methode ist ein Algorithmus, mit dem Elemente effizient hinzugefügt und gelöscht sowie gesucht werden können. Wenn Sie ein bestimmtes Array in Betracht ziehen, müssen Sie zum Hinzufügen eines Elements nach einer Suche einfügen und alle dahinter liegenden Elemente verschieben, damit die Verarbeitungskosten unerwartet hoch sind. Verwenden wir also diese Hash-Methode.

Die ** Hash-Tabelle ** ist ein Array, in dem Schlüssel gespeichert werden, sodass der Hash-Wert ein Index ist. Betrachten Sie beispielsweise eine Hash-Tabelle, deren Rest durch 13 als Hash-Wert geteilt wird.

Schlüssel	5	6	14	20	29	34	37	51	69	75
Wert	Herr Yamamoto	Nozaki	Herr Takahashi	Suzuki	Herr Hashimoto	Herr Hasegawa	Ogawa	Herr Sato	1. April	Brian
Hashwert(Rest geteilt durch 13)	5	6	1	7	3	8	11	12	4	10

In diesem Fall setzen Sie Herrn Yamamoto in eine [5], Herrn Nozaki in eine [6], Herrn Takahashi in eine [1] und so weiter. Natürlich müssen nicht alle Elemente des vorbereiteten Arrays ausgefüllt werden. Zum Beispiel ist eine [0] hier Keine. Außerdem wird jedes Element des Arrays a, das hier angezeigt wird, als ** Bucket ** bezeichnet.

Adressmethode öffnen

Die Open-Address-Methode ist eine Methode zum erneuten Hashing, bis keine Kollision mehr auftritt, wenn Hash-Wertekonflikte auftreten. Das Aufwärmen erfolgt bei Bedarf, wenn Elemente untersucht, hinzugefügt oder gelöscht werden.

Element hinzufügen

Schlüssel	5	6	14	20	29	34	37	51	69	75
Wert	Herr Yamamoto	Nozaki	Herr Takahashi	Suzuki	Herr Hashimoto	Herr Hasegawa	Ogawa	Herr Sato	1. April	Brian
Hashwert(Rest geteilt durch 13)	5	6	1	7	3	8	11	12	4	10

Array	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]
Wert	None	Herr Takahashi	None	Herr Hashimoto	1. April	Herr Yamamoto	Nozaki	Suzuki	Herr Hasegawa	None	Brian	Ogawa	Herr Sato

Wenn Sie diesem Array "(Schlüssel: 18, Wert: Johnny)" hinzufügen, lautet der Hash-Wert "18% 13 = 5", sodass er bereits mit Mr. Yamamoto gefüllt ist. Erwärme es also als "(18 + 1)% 13 = 6". Dies ist auch mit Nozaki-Kun gefüllt, also wieder 7 ist auch mit Suzuki-Kun gefüllt, also wieder ... Da es kein Element mit einem Schlüssel mit einem Hash-Wert von 9 gibt, ist es mir endlich gelungen, Johnny zu einem [9] hinzuzufügen. Hat.

Array	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]
Wert	None	Herr Takahashi	None	Herr Hashimoto	1. April	Herr Yamamoto	Nozaki	Suzuki	Herr Hasegawa	Johnny	Brian	Ogawa	Herr Sato

Element löschen

Wie löscht man nun ein Element? Angenommen, Sie löschen Yamamoto aus diesem Array. Wenn ich es einfach löschen würde, würde die Suche nach Johnny es hier in "a [9]" als Ergebnis der Wiederholung finden, aber der ursprüngliche Hash-Wert war "5". Daher wird der Wert des Hashwerts 5 nicht gefunden und die Suche schlägt fehl. Wenn a [5] von Anfang an leer ist, ist es in Ordnung, die Suche nicht zu bestehen. Nach dem Löschen wird der Wert, den Sie später suchen möchten, möglicherweise durch erneutes Aufbereiten ausgefüllt. richtig. Um diesen Bereich zu beurteilen, kann jeder Bucket des Arrays drei Zustände haben: "LEER, BESETZT und GELÖSCHT". Auf diese Weise befindet sich bei der Suche nach dem Wert von Schlüssel 18 "a [5]" im Status "GELÖSCHT", sodass Sie die Suche erneut aufbereiten und fortsetzen können.

Klasse 1

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

Definiert den Status des Buckets. In C-Sprache

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

Es ist das gleiche wie

Klasse 2

class Bucket:
    #Eimer, aus denen der Hash besteht

    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

Diese Klasse erstellt eine Instanz des Buckets. Eine Bucket-Instanz ist im Grunde ein einzelnes Element des Arrays, das wir zuvor gesehen haben. Jedes dieser Elemente hat drei Attribute: Schlüssel, Wert und Status.

Klasse 3

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

    def hash_value(self, key: Any) -> int:
        """Suchen Sie den Hashwert aus dem Schlüssel"""
        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:
        """Erwärmen Sie den Hash-Wert erneut und geben Sie ihn zurück"""
        return (self.hash_value(key) + 1) % self.capacity

    def search_node(self, key: Any) -> Any:
        """Suchen Sie nach Eimern, deren Schlüssel der Schlüssel ist"""
        hash = self.hash_value(key)
        p = self.table[hash] #Der Hash-Eimer geht in p.
        for i in range(self.capacity): #Schleife für die Anzahl der Buckets im Array
            if p.stat == Status.EMPTY: #Wenn der Eimer leer ist, bedeutet dies, dass von Anfang an nichts darin war. Brechen Sie also ab und geben Sie None zurück
                break
            elif p.stat == Status.OCCUPIED and p.key == key: #Wenn Sie einen Eimer mit dem Schlüssel finden, den Sie suchen möchten, geben Sie diesen Eimer zurück
                return p
            hash = self.rehash_value(hash)
            p = self.table[hash]
        return None 

    def search(self, key: Any) -> Any:
        """Suchen Sie mit dem Schlüssel nach dem Element und geben Sie den Wert zurück"""
        p = self.search_node(key)
        if p is not None:
            return p.value
        else:
            return None
    
    def add(self, key: Any, value: Any) -> bool:
        """Fügen Sie ein Element hinzu, dessen Schlüssel der Schlüssel und dessen Wert der Wert ist"""
        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:
        """Element mit Schlüsselschlüssel löschen"""
        p = self.search_node(key)
        if p is None:
            return False
        p.set_status(Status.DELETED)
        return True
    
    def dump(self) -> None:
        """Dump Hash-Tabelle"""
        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('---Nicht registriert---')
            elif self.table[i].stat == Status.DELETED:
                print('---gelöscht---')

Früher habe ich gesagt, dass der Versuch, den Wert von key: 18 zu finden, nachdem ein [5] gelöscht wurde, fehlschlagen würde, aber lassen Sie uns sehen, wie dies vermieden wird.

    def search_node(self, key: Any) -> Any:
        """Suchen Sie nach Eimern, deren Schlüssel der Schlüssel ist"""
        hash = self.hash_value(key)
        p = self.table[hash] #Der Hash-Eimer geht in p.
        for i in range(self.capacity): #Schleife für die Anzahl der Buckets im Array
            if p.stat == Status.EMPTY: #Wenn der Eimer leer ist, bedeutet dies, dass von Anfang an nichts darin war. Brechen Sie also ab und geben Sie None zurück
                break
            elif p.stat == Status.OCCUPIED and p.key == key: #Wenn Sie einen Eimer mit dem Schlüssel finden, den Sie suchen möchten, geben Sie diesen Eimer zurück
                return p
            hash = self.rehash_value(hash)
            p = self.table[hash]
        return None

Bei der Suche wird "search_node (key)" von "search (key)" aufgerufen. Dies ist eine Methode, um den Bucket mit dem Schlüssel zurückzugeben. Wenn Sie "search ()" als Schlüssel mit 18 angeben, beginnt die Suche nach "a [5]". Da dies ein Zustand von DELETE ist, werden wir "if" und "elif" erneut aufwärmen und "a [(18 + 1)% 13]" als Ziel festlegen. Sie können dies wiederholen und Johnny schließlich in "a [9]" finden.

Schließlich

Sehen wir uns ein Beispiel für die Verwendung der obigen Klasse an.


from enum import Enum
Menu = Enum('Menu', ['hinzufügen', 'Löschen', 'Suche', 'Dump', 'Ende'])

def select_menu() -> Menu:
    """Menüauswahl"""
    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.hinzufügen:
        key = int(input('Schlüssel: '))
        val = input('Wert: ')
        if not hash.add(key, val):
            print('Additionsfehler')
            
    elif menu == Menu.Löschen:
        key = int(input('Schlüssel: '))
        if not hash.remove(key):
            print('Fehler löschen')
            
    elif menu == Menu.Suche:
        key = int(input('Schlüssel: '))
        t = hash.search(key)
        if t is not None:
            print(f'Der Wert mit diesem Schlüssel ist{t}ist.')
        else:
            print('Es gibt keine zutreffenden Daten.')
    elif menu == Menu.Dump:
        hash.dump()
    else:
        break

Eingabe und Ausgabe unten

(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 5
Wert:Herr Yamamoto
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 6
Wert:Nozaki
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 14
Wert:Herr Takahashi
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 20
Wert:Suzuki
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 29
Wert:Herr Hashimoto
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 34
Wert:Herr Hasegawa
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 37
Wert:Ogawa
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 51
Wert:Herr Sato
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 69
Wert:1. April
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 75
Wert:Brian
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 4
 0 ---Nicht registriert---
 1 14 (Herr Takahashi)
 2 ---Nicht registriert---
 3 29 (Herr Hashimoto)
 4 69 (1. April)
 5 5 (Herr Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (Herr Hasegawa)
 9 ---Nicht registriert---
10 75 (Brian)
11 37 (Ogawa)
12 51 (Herr Sato)
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 5
Wert:Johnny
Additionsfehler!
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 4
 0 ---Nicht registriert---
 1 14 (Herr Takahashi)
 2 ---Nicht registriert---
 3 29 (Herr Hashimoto)
 4 69 (1. April)
 5 5 (Herr Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (Herr Hasegawa)
 9 ---Nicht registriert---
10 75 (Brian)
11 37 (Ogawa)
12 51 (Herr Sato)
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 5

Das ... Als ich versuchte, Johnny zu Mr. Yamamoto hinzuzufügen, schlug die Hinzufügung fehl. Selbst wenn in der Open-Address-Methode "a [5]" gefüllt ist, sollte es erneut aufbereitet und irgendwie gefüllt werden, es sei denn, alle Elemente sind voll ...

Das Problem scheint in add () zu liegen

if self.search(key) is not None:

Das ist der Teil.

if self.search(key) == value:

Ich werde es umschreiben und es erneut versuchen.

(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 5
Wert:Herr Yamamoto
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 6
Wert:Nozaki
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 14
Wert:Herr Takahashi
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 20
Wert:Suzuki
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 29
Wert:Herr Hashimoto
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 34
Wert:Herr Hasegawa
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 37
Wert:Ogawa
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 51
Wert:Herr Sato
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 69
Wert:1. April
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 75
Wert:Brian
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 4
 0 ---Nicht registriert---
 1 14 (Herr Takahashi)
 2 ---Nicht registriert---
 3 29 (Herr Hashimoto)
 4 69 (1. April)
 5 5 (Herr Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (Herr Hasegawa)
 9 ---Nicht registriert---
10 75 (Brian)
11 37 (Ogawa)
12 51 (Herr Sato)
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 1
Schlüssel: 18
Wert:Johnny
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 4
 0 ---Nicht registriert---
 1 14 (Herr Takahashi)
 2 ---Nicht registriert---
 3 29 (Herr Hashimoto)
 4 69 (1. April)
 5 5 (Herr Yamamoto)
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (Herr Hasegawa)
 9 18 (Johnny)
10 75 (Brian)
11 37 (Ogawa)
12 51 (Herr Sato)
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 2
Schlüssel: 5
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 4
 0 ---Nicht registriert---
 1 14 (Herr Takahashi)
 2 ---Nicht registriert---
 3 29 (Herr Hashimoto)
 4 69 (1. April)
 5 ---gelöscht---
 6 6 (Nozaki)
 7 20 (Suzuki)
 8 34 (Herr Hasegawa)
 9 18 (Johnny)
10 75 (Brian)
11 37 (Ogawa)
12 51 (Herr Sato)
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 3
Schlüssel: 18
Der Wert mit diesem Schlüssel ist Johnny.
(1)hinzufügen(2)Löschen(3)Suche(4)Dump(5)Ende: 5

Johnny wurde sicher hinzugefügt, und es gelang mir, nach Johnny zu suchen, nachdem Mr. Yamamoto gelöscht wurde.

[Nachschlagewerke](https://www.amazon.co.jp/ Algorithmen und Datenstrukturen, die mit neuem und klarem Python gelernt wurden - Neue und klare Serie - 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] Hash-Methode (Open-Address-Methode) in Python