Tables de hachage et tables de hachage en C++

Tables de hachage et tables de hachage en C++

Les tables de hachage et les tables de hachage sont des structures de données très courantes en informatique. Pourquoi? Parce que les tables de hachage et les tables de hachage peuvent localiser rapidement un élément spécifique en temps constant. Dans de nombreuses applications, cette différence de performances est significative.

Alors, quelle est la différence entre une table de hachage et une table de hachage ? En C++, la différence entre les deux est très subtile et ils peuvent généralement être considérés comme le même concept. Juste dans cet article, nous présenterons en détail les tables de hachage et les tables de hachage.

Table de hachage

La table de hachage est une structure de données basée sur la fonction de hachage. Il prend en charge les opérations d'insertion et de recherche en temps constant. Les éléments de données d'une table de hachage sont organisés en fonction des résultats de la fonction de hachage. Pour différentes clés, le résultat renvoyé par la fonction de hachage est unique, c'est-à-dire que chaque valeur de clé correspond à une valeur de hachage.

Pour utiliser une table de hachage en C++, utilisez la classe unordered_map dans la bibliothèque standard. Après avoir inclus le fichier d'en-tête , nous pouvons définir un objet unordered_map puis opérer dessus à l'aide de ses fonctions membres. Par exemple :

#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;
}

Dans l'exemple ci-dessus, nous avons utilisé un objet notes unordered_map pour implémenter la fonction de requête de notes des étudiants. Grâce aux notes["John"], nous pouvons facilement trouver les notes de John et le résultat en sortie est 90.

Table de hachage

Une table de hachage est une structure de données qui mappe les clés aux emplacements en fonction d'une fonction de hachage. Il permet d'effectuer des opérations telles que des insertions et des recherches en temps constant. Les idées de base des tables de hachage et des tables de hachage sont les mêmes, la seule différence est que les tables de hachage doivent également gérer les conflits.

Le soi-disant conflit signifie que deux valeurs clés différentes sont hachées à la même position par la fonction de hachage. À l'heure actuelle, vous devez utiliser des méthodes de résolution de conflits avec des fonctions de hachage, telles que le hachage ouvert ou le hachage de liste chaînée. En hachage ouvert, la méthode d'adresse ouverte consiste à utiliser d'autres slots, ils sont appelés slots ouverts, calculer la valeur de hachage de la clé afin d'insérer la clé dans d'autres slots de la table de hachage, si le slot est déjà occupé, essayer un autre Une fente. Dans le hachage de liste chaînée, la liste chaînée est implémentée dans les emplacements de la table de hachage.

Pour utiliser les tables de hachage en C++, vous devez utiliser la classe unordered_map ou unordered_set dans la bibliothèque standard. Lors de l'utilisation de ces deux classes, nous devons également fournir une fonction de hachage. La valeur par défaut est un modèle de classe std::hash, qui peut mapper n'importe quelle variable de type hachable à une valeur entière unique. Par exemple :

#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;
}

Dans l'exemple ci-dessus, nous utilisons un objet unordered_set pour gérer un groupe d'informations sur les personnes, où Person est un type de structure contenant deux champs : nom et âge. Il convient de noter que nous fournissons également une fonction de hachage personnalisée PersonHash. Étant donné que le type Person n'est pas un type hachable, nous devons lui fournir une fonction de hachage.

Résumé

Les tables de hachage et les tables de hachage sont des structures de données très pratiques en C++. Dans le développement réel, elles sont souvent utilisées pour gérer des ensembles et des index de mots-clés. Lorsque vous l'utilisez, vous devez faire attention au choix de la fonction de hachage et à la manière de gérer les conflits.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!