Heim Backend-Entwicklung C++ Hash-Tabellen und Hash-Tabellen in C++

Hash-Tabellen und Hash-Tabellen in C++

Aug 21, 2023 pm 09:58 PM
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 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;
}
Nach dem Login kopieren

Im obigen Beispiel haben wir ein unordered_map-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;
}
Nach dem Login kopieren

Im obigen Beispiel verwenden wir ein unordered_set-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!

Erklärung dieser Website
Der Inhalt dieses Artikels wird freiwillig von Internetnutzern beigesteuert und das Urheberrecht liegt beim ursprünglichen Autor. Diese Website übernimmt keine entsprechende rechtliche Verantwortung. Wenn Sie Inhalte finden, bei denen der Verdacht eines Plagiats oder einer Rechtsverletzung besteht, wenden Sie sich bitte an admin@php.cn

Heiße KI -Werkzeuge

Undresser.AI Undress

Undresser.AI Undress

KI-gestützte App zum Erstellen realistischer Aktfotos

AI Clothes Remover

AI Clothes Remover

Online-KI-Tool zum Entfernen von Kleidung aus Fotos.

Undress AI Tool

Undress AI Tool

Ausziehbilder kostenlos

Clothoff.io

Clothoff.io

KI-Kleiderentferner

AI Hentai Generator

AI Hentai Generator

Erstellen Sie kostenlos Ai Hentai.

Heißer Artikel

R.E.P.O. Energiekristalle erklärten und was sie tun (gelber Kristall)
2 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Repo: Wie man Teamkollegen wiederbelebt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌
Hello Kitty Island Abenteuer: Wie man riesige Samen bekommt
4 Wochen vor By 尊渡假赌尊渡假赌尊渡假赌

Heiße Werkzeuge

Notepad++7.3.1

Notepad++7.3.1

Einfach zu bedienender und kostenloser Code-Editor

SublimeText3 chinesische Version

SublimeText3 chinesische Version

Chinesische Version, sehr einfach zu bedienen

Senden Sie Studio 13.0.1

Senden Sie Studio 13.0.1

Leistungsstarke integrierte PHP-Entwicklungsumgebung

Dreamweaver CS6

Dreamweaver CS6

Visuelle Webentwicklungstools

SublimeText3 Mac-Version

SublimeText3 Mac-Version

Codebearbeitungssoftware auf Gottesniveau (SublimeText3)

Parallelitätssicheres Design von Datenstrukturen in der C++-Parallelprogrammierung? Parallelitätssicheres Design von Datenstrukturen in der C++-Parallelprogrammierung? Jun 05, 2024 am 11:00 AM

Bei der gleichzeitigen C++-Programmierung ist der parallelitätssichere Entwurf von Datenstrukturen von entscheidender Bedeutung: Kritischer Abschnitt: Verwenden Sie eine Mutex-Sperre, um einen Codeblock zu erstellen, der nur die gleichzeitige Ausführung eines Threads zulässt. Lese-/Schreibsperre: Ermöglicht das gleichzeitige Lesen mehrerer Threads, das gleichzeitige Schreiben jedoch nur einem Thread. Sperrenfreie Datenstrukturen: Verwenden Sie atomare Operationen, um Parallelitätssicherheit ohne Sperren zu erreichen. Praktischer Fall: Thread-sichere Warteschlange: Verwenden Sie kritische Abschnitte, um Warteschlangenvorgänge zu schützen und Thread-Sicherheit zu erreichen.

Das C++-Objektlayout ist auf den Speicher abgestimmt, um die Effizienz der Speichernutzung zu optimieren Das C++-Objektlayout ist auf den Speicher abgestimmt, um die Effizienz der Speichernutzung zu optimieren Jun 05, 2024 pm 01:02 PM

C++-Objektlayout und Speicherausrichtung optimieren die Effizienz der Speichernutzung: Objektlayout: Datenelemente werden in der Reihenfolge der Deklaration gespeichert, wodurch die Speicherplatznutzung optimiert wird. Speicherausrichtung: Daten werden im Speicher ausgerichtet, um die Zugriffsgeschwindigkeit zu verbessern. Das Schlüsselwort alignas gibt eine benutzerdefinierte Ausrichtung an, z. B. eine 64-Byte-ausgerichtete CacheLine-Struktur, um die Effizienz des Cache-Zeilenzugriffs zu verbessern.

Wie implementiert man einen benutzerdefinierten Komparator in C++ STL? Wie implementiert man einen benutzerdefinierten Komparator in C++ STL? Jun 05, 2024 am 11:50 AM

Die Implementierung eines benutzerdefinierten Komparators kann durch die Erstellung einer Klasse erreicht werden, die „operator()“ überlädt, zwei Parameter akzeptiert und das Ergebnis des Vergleichs anzeigt. Beispielsweise sortiert die StringLengthComparator-Klasse Zeichenfolgen, indem sie ihre Längen vergleicht: Erstellen Sie eine Klasse, überladen Sie „operator()“ und geben Sie einen booleschen Wert zurück, der das Vergleichsergebnis angibt. Verwendung benutzerdefinierter Komparatoren zum Sortieren in Containeralgorithmen. Mit benutzerdefinierten Komparatoren können wir Daten anhand benutzerdefinierter Kriterien sortieren oder vergleichen, selbst wenn wir benutzerdefinierte Vergleichskriterien verwenden müssen.

Wie implementiert man das Strategy Design Pattern in C++? Wie implementiert man das Strategy Design Pattern in C++? Jun 06, 2024 pm 04:16 PM

Die Schritte zum Implementieren des Strategiemusters in C++ lauten wie folgt: Definieren Sie die Strategieschnittstelle und deklarieren Sie die Methoden, die ausgeführt werden müssen. Erstellen Sie spezifische Strategieklassen, implementieren Sie jeweils die Schnittstelle und stellen Sie verschiedene Algorithmen bereit. Verwenden Sie eine Kontextklasse, um einen Verweis auf eine konkrete Strategieklasse zu speichern und Operationen darüber auszuführen.

Ähnlichkeiten und Unterschiede zwischen Golang und C++ Ähnlichkeiten und Unterschiede zwischen Golang und C++ Jun 05, 2024 pm 06:12 PM

Golang und C++ sind Garbage-Collected- bzw. manuelle Speicherverwaltungs-Programmiersprachen mit unterschiedlicher Syntax und Typsystemen. Golang implementiert die gleichzeitige Programmierung über Goroutine und C++ implementiert sie über Threads. Die Golang-Speicherverwaltung ist einfach und C++ bietet eine höhere Leistung. In der Praxis ist Golang-Code prägnanter und C++ bietet offensichtliche Leistungsvorteile.

Was sind die zugrunde liegenden Implementierungsprinzipien von C++-Smartpointern? Was sind die zugrunde liegenden Implementierungsprinzipien von C++-Smartpointern? Jun 05, 2024 pm 01:17 PM

Intelligente C++-Zeiger implementieren eine automatische Speicherverwaltung durch Zeigerzählung, Destruktoren und virtuelle Funktionstabellen. Der Zeigerzähler verfolgt die Anzahl der Referenzen, und wenn die Anzahl der Referenzen auf 0 sinkt, gibt der Destruktor den ursprünglichen Zeiger frei. Virtuelle Funktionstabellen ermöglichen Polymorphismus und ermöglichen die Implementierung spezifischer Verhaltensweisen für verschiedene Arten von Smart Pointern.

Wie kopiere ich einen C++-STL-Container? Wie kopiere ich einen C++-STL-Container? Jun 05, 2024 am 11:51 AM

Es gibt drei Möglichkeiten, einen C++-STL-Container zu kopieren: Verwenden Sie den Kopierkonstruktor, um den Inhalt des Containers in einen neuen Container zu kopieren. Verwenden Sie den Zuweisungsoperator, um den Inhalt des Containers in den Zielcontainer zu kopieren. Verwenden Sie den Algorithmus std::copy, um die Elemente im Container zu kopieren.

Wie implementiert man eine verschachtelte Ausnahmebehandlung in C++? Wie implementiert man eine verschachtelte Ausnahmebehandlung in C++? Jun 05, 2024 pm 09:15 PM

Die Behandlung verschachtelter Ausnahmen wird in C++ durch verschachtelte Try-Catch-Blöcke implementiert, sodass neue Ausnahmen innerhalb des Ausnahmehandlers ausgelöst werden können. Die verschachtelten Try-Catch-Schritte lauten wie folgt: 1. Der äußere Try-Catch-Block behandelt alle Ausnahmen, einschließlich der vom inneren Ausnahmehandler ausgelösten. 2. Der innere Try-Catch-Block behandelt bestimmte Arten von Ausnahmen, und wenn eine Ausnahme außerhalb des Gültigkeitsbereichs auftritt, wird die Kontrolle an den externen Ausnahmehandler übergeben.

See all articles