软件企业公司网站模板,php手机网站如何制作,网页游戏平台十大排名,wordpress站点费用哈希表存储结构#xff08;开放寻址法#xff0c;拉链法#xff09;字符串哈希方式#xff08;添加、查找h(x)#xff09;
常见从0~10^9映射到0~10^5就要对10^5取mod#xff08;取模一般要质数最好#xff09;但是可能会有冲突
1.拉链法#xff1a;O(1)#xff0c;每…哈希表存储结构开放寻址法拉链法字符串哈希方式添加、查找h(x)
常见从0~10^9映射到0~10^5就要对10^5取mod取模一般要质数最好但是可能会有冲突
1.拉链法O(1)每个节点拉一条链增加数
#includeiostream
#includecstring
using namespace std;
const int N100003;
int h[N],e[N],ne[N],idx;
void insert(int x){int k(x%NN)%N;e[idx]x;ne[idx]h[k];h[k]idx;
}
bool find(int x){int k(x%NN)%N;for(int ih[k];i!-1;ine[i]){if(e[i]x)return true;}return false;
}
int main(){int n;cinn;memset(h,-1,sizeof(h));while(n--){char op[2];int x;cinopx;if(op[0]I)insert(x);else {if(find(x))coutYesendl;else coutNoendl;}}return 0;
}
2.开放寻址法开放寻厕法
#includeiostream
#includecstring
using namespace std;
const int N200003,null0x3f3f3f3f;
int h[N];
int find(int x ){int k (x%NN)%N;while(h[k]!nullh[k]!x){k;if(kN)k0;}return k;
}
int main(){int n;cinn;memset(h,0x3f,sizeof(h));while(n--){char op[2];int x;cinopx;int kfind(x);if(op[0]I)h[k]x;else {if(k)coutYesendl;else coutNoendl;}}return 0;
}
字符串前缀哈希方式映射成从1开始取p131 13331 2^64三个
#includeiostream
using namespace std;
typedef unsigned long long ull;
const int N100010,P131;//进制
int n,m;
char str[N];
ull h[N],p[N];//h[i]表示前i个数的哈希值,p用于存储p的多少次方
ull get(int l,int r){return h[r]-h[l-1]*p[r-l1];
}
int main(){cinnmstr1;p[0]1;for(int i1;in;i){p[i]p[i-1]*P;h[i]h[i-1]*Pstr[i];}while(m--){int l1,r1,l2,r2;cinl1r1l2r2;if(get(l1,r1)get(l2,r2))coutYesendl;else coutNoendl;}return 0;
}
