首页 > 其他分享 >哈希表

哈希表

时间:2024-10-31 18:00:15浏览次数:5  
标签:hash int pos cc 哈希 table include

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<random>
#include<time.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<unordered_map>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
const int MAXN=1e5+10;
int pos[MAXN],cnt;mt19937 R;
struct node{int x,y,w;};vector <node> e;
inline bool cmp(node x,node y)
	{return x.w<y.w;}
"ValueType" <ll,int> H;
inline ll F(int x,int y)
	{return ((1ll*x)<<32)|y;}
signed main()
{
	int n=100000,m=100000,q=250;
	for(int i=1;i<=n;++i) pos[i]=i;
	for(int i=1,x,y,w;i<=m;++i)//插入 m 个数
	{
		w=R()%123456789+1;
		x=R()%n+1,y=R()%n+1;
		if(x>y) swap(x,y);ll pos=F(x,y);
		if(!H[pos]) H[pos]=w;
		else H[pos]=min(H[pos],w);
	}
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
	for(auto now:H)//遍历一遍
	{
		ll pos=now.first;int w=now.second;
		int x=pos>>32,y=pos^((1ll*x)<<32);
		e.push_back({x,y,w});
	}
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
// 	sort(e.begin(),e.end(),cmp);
	for(int i=0;i<e.size();++i)//修改为编号
		H[F(e[i].x,e[i].y)]=i;
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
	for(int o=1,k=400;o<=q;++o)//查询一些东西
	{
		shuffle(pos+1,pos+1+n,R);
		for(int i=0;i<k;++i) for(int j=i+1;j<k;++j)
		{
			int x=pos[i],y=pos[j];
			if(x>y) swap(x,y);ll POS=F(x,y);
			if(H.find(POS)!=H.end()) ++cnt;
		}
	}
	cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';return 0;
}

你写出了这样的代码,大概是想找出 \(q=250\) 个点集大小为 \(k=400\) 的导出子图。

其中你需要实现一个 pairint 的映射,于是你将 pair 压成了 long long

尽管不一定很卡常,但是你精益求精的使 "ValueType" = gp_hash_table,打开了 O2

然后你发现输出是:

0.727675
0.729566
1.07756

甚至查询都跑不出来。

你不以为意,大概只是正好这样的数据能卡掉 gp_hash_table,但是没关系,因为你还有 cc_hash_table 可以替换。

你幸高采烈的将 cc_hash_table 替换上,你发现输出是:

0.008778
0.01072
0.011504
0.350058

不错,很快,你提交后吃了一发罚时,它说你 TLE 了。

你更加疑惑了,但是你认为可能常数藏在一些看不见的地方,于是开始卡常。

但是当然你想到用 unordered_map 来试一试,你发现输出是:

0.010581
0.012657
0.013935
0.600974

明显比 cc_hash_table 慢啊,于是你继续卡常。

但是两个多小时后你卡不动了,你突然想到了什么,对 cc_hash_table 打开了 ubsan:

0.023092
0.02854
0.031228
/usr/include/c++/9/ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp:530:15: runtime error: member access within null pointer of type 'struct entry'
0.915729

所以或许是 cc_hash_table 有 bug?我不知道啊。

但是对于 gp_hash_table

#include<stdio.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
#include<unordered_map>
#define ll long long
using namespace std;
using namespace __gnu_pbds;
gp_hash_table <ll,int> H;
signed main()
{
	int n=500000,cnt=0;
	for(int i=1,x,y;i<=n;++i)
	{
		x=rand()%n+1,y=rand()%n+1;
		// if(x>y) swap(x,y);
		H[(1ll*x)<<32|y]=i;
	}
}

这个跑 \(0.15s\),而把注释删了跑 \(9.9s\)。大概是因为过于不均匀?

标签:hash,int,pos,cc,哈希,table,include
From: https://www.cnblogs.com/int-R/p/18518522/hash

相关文章

  • 用哈希表封装myunordered_map和myunordered_set
    在学习这个之前,已经学习过,myunordered_map和myunordered_set的基本用法和哈希表怎么用哈希思想模拟实现;因此为了更深入的了解myunordered_map和myunordered_set与哈希表的内容,我们来自己用哈希表模拟实现myunordered_map和myunordered_set;这种模拟实现和之前模拟实现map与set......
  • 两数之和到哈希表
    两数之和给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。你可以假设每种输入只会对应一个答案,并且你不能使用两次相同的元素。你可以按任意顺序返回答案。示例1:输入:nums=[2,7,11,......
  • 必学算法——哈希算法
    目录前言一、什么是哈希算法二、哈希算法的原理三、哈希算法的特点四、哈希算法的应用场景五、经典例题1.字符统计代码题解[2.字符串统计](https://www.lanqiao.cn/problems/1206/learning/?page=1&first_category_id=1&name=%E5%AD%97%E7%AC%A6%E4%B8%B2%E7%BB%9F%E8%......
  • 0x02 Leetcode Hot100 哈希
    前置知识掌握每种语言的基本数据类型及其时间复杂度。Python:list、tuple、set、dictC++:STL中的vector、set、mapJava:集合类中的List、Set、Map为什么是哈希?在不同语言中,对于字典(dict)类的数据都会先将其键(key)进行哈希(Hash)运算,这个Hash值决定了键值对在内存中的存储位置,因此......
  • 【论文分享】HashGAT-VCA:一种结合哈希函数和图注意力网络的矢量元胞自动机模型,用于城
    本文考虑地块内部异质性,提出一个结合哈希函数和图注意力网络(GAT)的矢量元胞自动机(VCA)方法,用于研究城市土地利用变化;并将该模型应用于模拟深圳市2009年至2012年的城市土地利用变化,结果表明,HashGAT-VCA模型的模拟准确性显著优于其他VCA模型。【论文题目】HashGAT-VCA:Avecto......
  • 2.哈希函数
    哈希函数目标:极快且稳定特点:确定性/幂等性:对于相同的输入,哈希算法应始终产生相同的输出。这样才能确保哈希表是可靠的。效率高:计算哈希值的过程应该足够快,哈希表的实用性越高。均匀分布:哈希算法应使得键值对均匀分布在哈希表中。分布越均匀,哈希冲突的概率就越低......
  • 散列表:哈希表的装载因子对散列冲突有什么影响?
    散列表:哈希表的装载因子对散列冲突有什么影响?哈希表的装载因子对散列冲突有着重要的影响。一、装载因子的定义装载因子是哈希表中已存储的元素个数与哈希表大小的比值。例如,如果一个哈希表中有10个元素,哈希表的大小为20,那么装载因子就是10/20=0.5。二、对散列冲突......
  • P3370 【模板】字符串哈希
    【模板】字符串哈希题目描述如题,给定NNN个字符串(第iii个字符......
  • 7、哈希表
    7、哈希表哈希表最主要的作用就是把一个比较庞大的空间或者值域映射到比较小的值域(0-n)就是将-10^9~10^9映射到0~10^5一、存储结构映射的方法可以是h(x)=xmod10^5但是这样映射会出现一个问题可能会有重复的数字出现所以就引出了两个方法开放寻址法和......
  • 「哈希表」是什么,有哪些常用的解决冲突的方法
    哈希表(HashTable),也被称为散列表,是一种数据结构,用于实现关联数组(AssociativeArray)或映射(Map)这样的抽象数据类型。常用的解决哈希表冲突的方法:1.链地址法(SeparateChAIning);2.开放寻址法(OpenAddressing);3.线性探查(LinearProbing)等。一、哈希表是什么哈希表(HashTable),也被称......