哈希散列表（C++⼒扣题解上）
⽬录
哈希表原理：
哈希的分类
可以把它简单地理解为数组，但其实它更像python中的字典 头⽂件：#include <unordered_set>
创建哈希集合：unordered_set<type> set;
检验检疫局英文
个⼈理解：
不如创建⼀个数组，因为创建⼀个哈希消耗的内存⽐较⼤= =，这⾥数组和哈希集合承担的作⽤其实是⼀样的= =哈希映射：
头⽂件：#include <unordered_map>
创建哈希映射： unordered_map<type, type> map;
个⼈理解：
这个就是python的字典，第⼀个type是键(key)，第⼆个type是值(value)，通过键来查询值
可以理解为：在药房，药师通过看抽屉的标签来查询抽屉的药品，标签就是键，药品就是值
所以，哈希相当于⽤空间换时间，查询哈希的值，要⽐遍历数组查询值所需的时间要短.
哈希STL函数的使⽤：
引⽤哈希集合时的应⽤：
#include <unordered_set> // 当使⽤set时引⽤的模板库
#include<iostream>
using namespace std;
int main() {
/
/ 创建⼀个哈希集合
unordered_set<int> hashset;
// 插⼊新的关键字
hashset.insert(3);
两棵树的守望hashset.insert(2);
hashset.insert(1);
马弗罐// 删除关键字
// 判断关键字是否在哈希集合中，如果在⽅法返回负数。如果在集合中返回真，否则返回假 if (unt(2) <= 0) {
cout << "关键字2不在哈希集合中" << endl;
}
// 得到哈希集合的⼤⼩
cout << "The size of hash set is: " << hashset.size() << endl;
// 遍历哈希集合，注意要以指针的形式
for (auto it = hashset.begin(); it != d(); ++it) {
cout << (*it) << " ";
}
cout << "are in the hash set." << endl;
// 清除哈希集合
hashset.clear();
// 判断哈希结合是否为空
if (pty()) {
cout << "hash set is empty now!" << endl;
}
}
引⽤哈希表的应⽤：
#include<unordered_map>
#include<iostream>
广西中医学院学报
using namespace std;
int main()
{
unordered_map<int,int>map;//创建哈希表
map[4] = 14;//直接赋值
map[5] = 15;
cout << map[4];//输出14
map.insert({ 5,15 });//参数为（键，值）
map.insert({ 5,16 });
cout << map[5]; //结果为15->⼀个下标只能对应⼀个值 //复制，重新构造⼀张新的哈希表
unordered_map<int, int> map{ {1,10},{2,12},{3,13} };
unordered_map<int, int> map1(map);
unordered_map<int, int>::iterator iter = hmap.begin();
unordered_map<int, int>::iterator iter = d();
bool isEmpty = pty();//判断是否为空
安娜卡列尼娜论文
int size = hmap.size();//哈希表的⼤⼩
erase函数
//clear()函数：清空哈希表中的元素
map.clear();
unordered_map<int, int>::iterator iter;
iter = hmap.find(2); //返回key==2的迭代器，可以通过iter->second访问该key对应的元素
if(iter != d()) cout << iter->second;
int count = unt(key);//统计哈希表键所对应的值的个数
//哈希表的遍历
for(auto iter=map.begin(); iter != d(); iter++){
cout << "key: " << iter->first << "value: " << iter->second <<endl;
}
⼩理解：
遇到不会的函数要积极动⼿查⼀查，你会发现有很多好⽤的函数
C语⾔是什么？不要联系我了，我现在只⽤C++
问：auto是啥？
答：auto是⼀种类型，像int，double，string，它能够根据后⾯是啥⾃动匹配对应的类型通过下⾯的题⽬就会加深理解了^ ^
题⽬实战
1：存在重复元素
暴⼒的⽅法很容易想到：两个for嵌套：时间复杂度是：O(N^2)
我这⾥给出的是⼩暴⼒的⽅法：时间复杂度是O(N*logN)
bool containsDuplicate(vector<int>& nums)
{
sort(nums.begin(),d());
for(int i=1;i<nums.size();i++)
if(nums[i]==nums[i-1])
return true;
retrun false;
}
哈希集合的⽅法：
思路解析：
遍历数组nums，将遍历到的元素插⼊hash集合中
如果哈希表的长度！=原数组的长度 -> 那么肯定有1个以上的重复元素插⼊到了哈希表注意这只会导致元素作为索引对应的值增加，并不会使数组长度增加
画图理解：
破茧狂龙原数组：
理解：原数组的val作为了hashset的index，原数组val的频数作为了hashset的val
bool containsDuplicate(vector<int>& nums) {
unordered_set<int>hash;
for (int a : nums)
{
hash.insert(a);
}
return hash.size() != nums.size();
}
2：只出现⼀次的数字
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议