本文主要是介绍CPP中的hash [more cpp-7],希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
写在前面
hash 在英文中是弄乱的含义。在编程中,hash是一种数据技术,它把任意类型的数据通过算法,生成一串数字(hash code),实现hash的函数称为哈希函数,又称散列函数,杂凑函数。在CPP中hashcode是一个size_t类型的数字。
你可能会问?把数据弄乱有什么用?为什么我们要把数据映射到一串数字上?这又什么意义吗?我们先看看hash的性质
一般hash性质
唯一性(唯一映射)
- 理想情况下,不同的输入应该映射到不同的哈希值,这样可以确保哈希值具有唯一性。(唯一且不重复)不过,由于输入空间的大小通常远大于哈希值的输出空间,实际上可能会发生哈希冲突(即不同输入映射到相同的哈希值)。
固定长度
- 不论输入数据的长度是多少,哈希值的长度是固定的。比如,SHA-256 哈希函数总是生成 256 位的哈希值。
不可逆性(One-Way Property)
- 不可逆性: 哈希函数是单向的,即从哈希值不能反推出原始输入。这是因为哈希函数将原始数据压缩成固定长度的哈希值,可能会丢失信息。由于信息丢失,哈希值不能唯一地表示原始数据。
碰撞(Collision)
- 碰撞: 哈希函数的输出范围是有限的,因此不同的输入数据可能会生成相同的哈希值。这种现象称为碰撞。尽管哈希函数设计时尽量减少碰撞的发生,但理论上总是存在碰撞的可能性。
std::hash
CPP为内建类型提供了hash的计算方法(当然还有类型本身)
const std::type_info& inttype = typeid(int);
cout << inttype.name() << endl;
cout << inttype.hash_code() << endl;const std::type_info& floattype = typeid(float);
cout << floattype.name() << endl;
cout << floattype.hash_code() << endl;std::hash<int> intHash;
std::hash<std::string> stringHash;
std::cout << "Hash of 42: " << intHash(42) << std::endl;
std::cout << "Hash of 42: " << intHash(52) << std::endl;
std::cout << "Hash of 'hello': " << stringHash("hello") << std::endl;
哈希表
在一些常见的任务中,我们其实有意无意的就在使用hash表
- 给定一个数组arr,我们要统计其中每个数字出现的次数(数字大于0小于1000),那我们可以命出一个int table[1000]数组,先把每个元素置零,再历遍arr, table[arr[j]]++.这里其实就是一个1->1的hash
- 它在给定的范围内唯一且不重复,没有碰撞现象,这就是一个简单的hash表
- 给定一个字符串string,里面只有小写字母,我们统计26个英文字母出现的次数,那我们可以命出一个int alphanum[26],置零每个元素,历遍string ,alphanum[string[j]]++,这里其实是’a’->0的hash
- 下一个场景,你开了一家小卖部,有1000种 商品,你记不清每种商品的价格,把它记在一个本子上,以
商品名-价格 的形式,那如果是直接检索,买任意一种商品最糟糕要对比1000次名字。我们如果做一个hash
商品名对上唯一的数字,那按照数字来找不是快多了?
std::hash map
哈希表是一种用于存储和查找数据的数据结构,通过哈希函数将键映射到表中的位置,从而在平均情况下实现常数时间的插入、删除和查找操作。在 C++ 中,哈希表的实现主要通过标准库提供的 unordered_map
和 unordered_set
类来实现。
unordered_map
和 unordered_set
这两个容器都基于哈希表实现。unordered_map
用于存储键值对,而 unordered_set
用于存储唯一的键。
1. unordered_map
unordered_map
是一个哈希表实现的关联容器,它将键映射到值。其主要特性包括:
- 插入操作:在平均情况下,插入时间复杂度为 O(1)。
- 查找操作:在平均情况下,查找时间复杂度为 O(1)。
- 删除操作:在平均情况下,删除时间复杂度为 O(1)。
示例代码
#include <iostream>
#include <unordered_map>using namespace std;int main() {// 创建一个 unordered_mapunordered_map<string, int> umap;// 插入键值对umap["apple"] = 3;umap["banana"] = 2;umap["orange"] = 1;// 查找元素if (umap.find("banana") != umap.end()) {cout << "Banana count: " << umap["banana"] << endl;}// 遍历 unordered_mapfor (const auto& pair : umap) {cout << pair.first << ": " << pair.second << endl;}// 删除元素umap.erase("apple");// 查找删除后的元素if (umap.find("apple") == umap.end()) {cout << "Apple not found" << endl;}return 0;
}
2. unordered_set
unordered_set
是一个哈希表实现的集合容器,用于存储唯一的元素。它的主要特性包括:
- 插入操作:在平均情况下,插入时间复杂度为 O(1)。
- 查找操作:在平均情况下,查找时间复杂度为 O(1)。
- 删除操作:在平均情况下,删除时间复杂度为 O(1)。
示例代码
#include <iostream>
#include <unordered_set>using namespace std;int main() {// 创建一个 unordered_setunordered_set<string> uset;// 插入元素uset.insert("apple");uset.insert("banana");uset.insert("orange");// 查找元素if (uset.find("banana") != uset.end()) {cout << "Banana is in the set" << endl;}// 遍历 unordered_setfor (const auto& element : uset) {cout << element << endl;}// 删除元素uset.erase("apple");// 查找删除后的元素if (uset.find("apple") == uset.end()) {cout << "Apple not found" << endl;}return 0;
}
主要功能和操作
- 构造函数:
unordered_map
和unordered_set
提供了多种构造函数,包括默认构造函数、带初始桶数的构造函数等。 - 哈希函数:
unordered_map
和unordered_set
默认使用std::hash
作为哈希函数,用户也可以提供自定义哈希函数。 - 键的比较:默认使用
std::equal_to
进行键的比较,也可以提供自定义比较函数。
这篇关于CPP中的hash [more cpp-7]的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!