C++中的哈希表和散列表

C++中的哈希表和散列表

哈希表和散列表，是计算机科学中非常常见的数据结构。为什么呢？因为哈希表和散列表能够在常数时间内，快速的定位到某一个特定的元素。在很多应用中，这个性能上的差异是显著的。

那么，哈希表和散列表有什么不同呢？在C++中，两者的区别非常细微，大致上可以认为是同一个概念。就在本文中，我们将对哈希表和散列表进行详细的介绍。

哈希表

哈希表是一种基于哈希函数实现的数据结构。它支持常数时间的插入和查找等操作。哈希表的数据元素是根据哈希函数的结果而组织的。对于不同的键，哈希函数返回的结果是唯一的，也就是说，每个键值对应一个哈希值。

在C++中使用哈希表，要使用标准库中的unordered_map类。在包含头文件<unordered_map>之后，我们可以定义一个unordered_map对象，然后使用其成员函数对其进行操作。例如：

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

在上述示例中，我们使用了一个unordered_map<std::string, int>对象grades来实现学生成绩查询的功能。通过grades["John"]这样的方式，我们可以很容易地找到John的成绩，输出结果为90。

散列表

散列表是一种根据哈希函数将键映射到位置的数据结构。它允许在常数时间内进行插入和查找等操作。散列表和哈希表的核心思想是相同的，唯一的不同是散列表还需要对冲突进行处理。

所谓冲突，是指两个不同的键值被哈希函数哈希到了同一个位置。这时，需要用到散列函数冲突解决的方法，比如开散列或者链表散列。在开散列中，开放地址法是利用其它槽，它们被称为开放槽，计算键的哈希值，以便在哈希表的其它槽中插入键，如果该槽已被占用，则尝试另外一个槽。在链表散列中，链表是在哈希表的槽中实现的。

在C++中使用散列表，需要使用标准库中的unordered_map或unordered_set类。在使用这两个类时，我们还需要提供一个哈希函数，默认是一个std::hash类模板，它能够将任何可哈希类型的变量映射到一个唯一的整数值。例如：

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

在上述示例中，我们使用了一个unordered_set<Person, PersonHash>对象来维护一组人的信息，其中，Person是一个结构体类型，包含姓名和年龄两个字段。需要注意的是，我们还提供了一个自定义的哈希函数PersonHash，由于Person类型不是一个可哈希类型，我们需要为它提供一个哈希函数。

总结

哈希表和散列表是C++中非常实用的数据结构，在实际的开发中，常常用于维护关键字的集合和索引。在使用时，需要注意哈希函数的选择和冲突的处理方法。