C 中的哈希表和散列表
哈希表和散列表，是计算机科学中非常常见的数据结构。为什么呢？因为哈希表和散列表能够在常数时间内，快速的定位到某一个特定的元素。在很多应用中，这个性能上的差异是显著的。
那么，哈希表和散列表有什么不同呢？在C 中，两者的区别非常细微，大致上可以认为是同一个概念。就在本文中，我们将对哈希表和散列表进行详细的介绍。
哈希表
哈希表是一种基于哈希函数实现的数据结构。它支持常数时间的插入和查找等操作。哈希表的数据元素是根据哈希函数的结果而组织的。对于不同的键，哈希函数返回的结果是唯一的，也就是说，每个键值对应一个哈希值。
在C 中使用哈希表，要使用标准库中的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
散列表
散列表是一种根据哈希函数将键映射到位置的数据结构。它允许在常数时间内进行插入和查找等操作。散列表和哈希表的核心思想是相同的，唯一的不同是散列表还需要对冲突进行处理。
所谓冲突，是指两个不同的键值被哈希函数哈希到了同一个位置。这时，需要用到散列函数冲突解决的方法，比如开散列或者链表散列。在开散列中，开放地址法是利用其它槽，它们被称为开放槽，计算键的哈希值，以便在哈希表的其它槽中插入键，如果该槽已被占用，则尝试另外一个槽。在链表散列中，链表是在哈希表的槽中实现的。
在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
总结
哈希表和散列表是C 中非常实用的数据结构，在实际的开发中，常常用于维护关键字的集合和索引。在使用时，需要注意哈希函数的选择和冲突的处理方法。
以上是C++中的哈希表和散列表的詳細內容。更多資訊請關注PHP中文網其他相關文章！
