Hash tables and hash tables in C++

Hash tables and hash tables in C

Hash tables and hash tables are very common data structures in computer science. why? Because hash tables and hash tables can quickly locate a specific element in constant time. In many applications, this difference in performance is significant.

So, what is the difference between a hash table and a hash table? In C, the difference between the two is very subtle, and they can generally be considered the same concept. Just in this article, we will introduce hash tables and hash tables in detail.

Hash table

The hash table is a data structure based on the hash function. It supports constant-time insertion and search operations. The data elements of a hash table are organized according to the results of the hash function. For different keys, the result returned by the hash function is unique, that is, each key value corresponds to a hash value.

To use a hash table in C, use the unordered_map class in the standard library. After including the header file , we can define an unordered_map object and then operate on it using its member functions. For example:

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

In the above example, we used an unordered_map object grades to implement the function of student grade query. Through grades["John"], we can easily find John's grades, and the output result is 90.

Hash table

A hash table is a data structure that maps keys to locations based on a hash function. It allows operations such as insertions and searches to be performed in constant time. The core ideas of hash tables and hash tables are the same, the only difference is that hash tables also need to handle conflicts.

The so-called conflict means that two different key values ​​are hashed to the same position by the hash function. At this time, you need to use hash function conflict resolution methods, such as open hashing or linked list hashing. In open hashing, the open address method is to use other slots, they are called open slots, calculate the hash value of the key to insert the key in other slots of the hash table, if the slot is already occupied, try another A slot. In linked list hashing, the linked list is implemented in the slots of the hash table.

To use hash tables in C, you need to use the unordered_map or unordered_set class in the standard library. When using these two classes, we also need to provide a hash function. The default is a std::hash class template, which can map any hashable type variable to a unique integer value. For example:

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

In the above example, we use an unordered_set object to maintain a group of people's information, where Person is a structure type containing two fields: name and age. It should be noted that we also provide a custom hash function PersonHash. Since the Person type is not a hashable type, we need to provide a hash function for it.

Summary

Hash tables and hash tables are very practical data structures in C. In actual development, they are often used to maintain sets and indexes of keywords. When using it, you need to pay attention to the choice of hash function and how to deal with conflicts.

The above is the detailed content of Hash tables and hash tables in C++. For more information, please follow other related articles on the PHP Chinese website!