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

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

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

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

哈希表

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

立即学习“C++免费学习笔记（深入）”；

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

#include 
#include 
#include 

int main()
{
    std::unordered_map grades;

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

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

    return 0;
}

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

散列表

动感购物系统 2005V-C

无错试用版，保留了所以商城的基本功能，商品数量限制80件2005V-C更新：更新所有订单功能及一些相应的错误，在线支付加上邮费功能支持在线支付八家银行等接口和可以选择商品图文排列功能，可以后台自由设置，银行接口列表如下：动感在线支付支付宝 网银在线 NPS支付 西部支付 1st-pay在线支付平台 首信易支付 易付通 中国在线支付 环讯IPS支付 不使用在线支付默认管理员帐号：admin密码：ad

下载

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

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

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

#include 
#include 
#include 

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()(p.name);
        std::size_t h2 = std::hash()(p.age);
        return h1 ^ (h2 << 1);
    }
};

int main()
{
    std::unordered_set 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类型不是一个可哈希类型，我们需要为它提供一个哈希函数。

总结

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