手写HashMap
优势 :代替Unordered_map,某些题会卡unmap。
缺点:需要手写,代码量比调用库函数大。
哈希模数表
https://planetmath.org/goodhashtableprimes
算法流程
基于链式前向星。
插入结点(ins) 就遍历图,如果找到就直接value++,否则新建一个结点。
查找(find) 也是遍历图,如果找到直接返回value,否则返回0。
代码
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int N=1e5+5,mod=98317;
struct HashMap{
//hash prime table
//[24593,49157,98317](1e5)
//[196613,393241,786433](1e6)
//[1572869,3145739,6291469](1e7)
//[12582917 25165843 50331653] (6e7)
//mod<N
struct node{
int k,v,nt;
}e[N];
int h[N],cnt;
void ins(int x){
int u=x%mod;
for(int i=h[u];i;i=e[i].nt)
if(e[i].k==x) {e[i].v++;return;}
e[++cnt]={x,1,h[u]},h[u]=cnt;
}
int find(int x){
int u=x%mod;
for(int i=h[u];i;i=e[i].nt)
if(e[i].k==x) return e[i].v;
return 0;
}
}mp;
int main(){
int n;
//input
//10
//1 1 1 2 2 3 4 5 10 9
//output
//3 2 1 1 1 0 0 0 1 1
scanf("%d",&n);
for(int i=1;i<=n;i++){
int x;scanf("%d",&x);
mp.ins(x);
}
for(int i=1;i<=10;i++) printf("%d ",mp.find(i));
return 0;
}