Hash-Tabellen und Hash-Tabellen in C++

Hash-Tabellen und Hash-Tabellen in C++

Hash-Tabellen und Hash-Tabellen sind in der Informatik sehr verbreitete Datenstrukturen. Warum? Weil Hash-Tabellen und Hash-Tabellen ein bestimmtes Element in konstanter Zeit schnell finden können. In vielen Anwendungen ist dieser Leistungsunterschied erheblich.

Was ist also der Unterschied zwischen einer Hash-Tabelle und einer Hash-Tabelle? In C++ ist der Unterschied zwischen den beiden sehr subtil und sie können im Allgemeinen als dasselbe Konzept betrachtet werden. In diesem Artikel werden wir Hash-Tabellen und Hash-Tabellen im Detail vorstellen.

Hash-Tabelle

Hash-Tabelle ist eine Datenstruktur, die auf einer Hash-Funktion basiert. Es unterstützt zeitkonstante Einfüge- und Suchvorgänge. Die Datenelemente einer Hash-Tabelle werden entsprechend den Ergebnissen der Hash-Funktion organisiert. Für verschiedene Schlüssel ist das von der Hash-Funktion zurückgegebene Ergebnis eindeutig, d. h. jeder Schlüsselwert entspricht einem Hash-Wert.

Um eine Hash-Tabelle in C++ zu verwenden, verwenden Sie die Klasse unordered_map in der Standardbibliothek. Nachdem wir die Header-Datei ff4294d2f1027f38dcfc6e591d43822a eingefügt haben, können wir ein unordered_map-Objekt definieren und es dann mithilfe seiner Mitgliedsfunktionen bearbeiten. Zum Beispiel:

#include <unordered_map>
#include <string>
#include <iostream>

int main()
{
    std::unordered_map<std::string, int> grades;

    // 添加键值对
    grades["John"] = 90;
    grades["Sara"] = 85;
    grades["Bob"] = 95;

    // 查找键对应的值
    std::cout << "John's grade is " << grades["John"] << std::endl;

    return 0;
}

Im obigen Beispiel haben wir ein unordered_map2afa4d3f8bd3b313b9a5d1f92444599b-Objekt „grades“ verwendet, um die Funktion der Schülernotenabfrage zu implementieren. Über grades["John"] können wir Johns Noten leicht finden und das Ausgabeergebnis ist 90.

Hash-Tabelle

Eine Hash-Tabelle ist eine Datenstruktur, die Schlüssel Orten basierend auf einer Hash-Funktion zuordnet. Es ermöglicht die Ausführung von Vorgängen wie Einfügungen und Suchen in konstanter Zeit. Die Kernideen von Hash-Tabellen und Hash-Tabellen sind dieselben. Der einzige Unterschied besteht darin, dass Hash-Tabellen auch Konflikte verarbeiten müssen.

Der sogenannte Konflikt bedeutet, dass zwei verschiedene Schlüsselwerte durch die Hash-Funktion an dieselbe Position gehasht werden. Zu diesem Zeitpunkt müssen Sie Methoden zur Lösung von Hash-Funktionskonflikten verwenden, z. B. offenes Hashing oder verknüpftes Listen-Hashing. Beim offenen Hashing besteht die offene Adressmethode darin, andere Steckplätze zu verwenden. Sie werden als offene Steckplätze bezeichnet. Berechnen Sie den Hash-Wert des Schlüssels, um den Schlüssel in andere Steckplätze der Hash-Tabelle einzufügen. Wenn der Steckplatz bereits belegt ist, versuchen Sie es mit einem anderen Ein Steckplatz. Beim Hashing verknüpfter Listen wird die verknüpfte Liste in den Slots der Hash-Tabelle implementiert.

Um Hash-Tabellen in C++ zu verwenden, müssen Sie die Klasse unordered_map oder unordered_set in der Standardbibliothek verwenden. Wenn wir diese beiden Klassen verwenden, müssen wir auch eine Hash-Funktion bereitstellen. Die Standardeinstellung ist eine std::hash-Klassenvorlage, die jede hashbare Typvariable einem eindeutigen Ganzzahlwert zuordnen kann. Zum Beispiel:

#include <unordered_set>
#include <string>
#include <iostream>

struct Person
{
    std::string name;
    int age;
};

bool operator==(const Person& lhs, const Person& rhs)
{
    return lhs.name == rhs.name && lhs.age == rhs.age;
}

// 哈希函数
struct PersonHash
{
    std::size_t operator()(const Person& p) const
    {
        std::size_t h1 = std::hash<std::string>()(p.name);
        std::size_t h2 = std::hash<int>()(p.age);
        return h1 ^ (h2 << 1);
    }
};

int main()
{
    std::unordered_set<Person, PersonHash> people = {
        {"John", 30},
        {"Sara", 25},
        {"Bob", 45},
    };

    // 添加元素
    people.insert({"Mary", 38});

    // 查找元素
    Person p = {"John", 30};
    if (people.find(p) != people.end()) {
        std::cout << p.name << " is found" << std::endl;
    }

    return 0;
}

Im obigen Beispiel verwenden wir ein unordered_set6491ed04da39b6704fdfad2eeebcd351-Objekt, um die Informationen einer Gruppe zu verwalten, wobei Person ein Strukturtyp ist, der zwei Felder enthält: Name und Alter. Es ist zu beachten, dass wir auch eine benutzerdefinierte Hash-Funktion PersonHash bereitstellen. Da der Typ Person kein Hash-Typ ist, müssen wir eine Hash-Funktion dafür bereitstellen.

Zusammenfassung

Hash-Tabellen und Hash-Tabellen sind sehr praktische Datenstrukturen in C++. In der tatsächlichen Entwicklung werden sie häufig zum Verwalten von Schlüsselwortsätzen und -indizes verwendet. Bei der Verwendung müssen Sie auf die Wahl der Hash-Funktion und den Umgang mit Konflikten achten.

Das obige ist der detaillierte Inhalt vonHash-Tabellen und Hash-Tabellen in C++. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!