Hash表(散列表)

1. 复杂度O（k*n）k为较大的常数
2. 用处：在不适用动态内存的情况下，充分利用静态内存（不需要把数组开的贼大）
3. 判重（和map功能相似）
4. 避免hash冲突：链地址法
5. 代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<queue>
#include<stack>
#include<map>
#include<algorithm>
#define N 100000
#define mo 10007
using namespace std;
const int base=31;
int n,ht,z,ans;
struct node{
	string s="";
	int son=-1;
}a[N];
int hash(string st){
	int sum=0;
	for(int i=0; i<st.length(); i++) sum=(sum*base+(int)st[i])%mo;
	return sum;
}
int main(){
	cin>>n; z=mo-1;
	for(int i=1; i<=n; i++){
		int flag=0;
		string st;
		cin>>st;
		ht=hash(st);
		if(a[ht].s == "") a[ht].s=st,ans++;
		else{
			z++;
			while(a[ht].son != -1){
				if(a[ht].s == st) flag=1;
				ht=a[ht].son;
			}
			if(a[ht].s == st) flag=1;
			if(flag) continue;
			a[ht].son=z;
			a[z].s=st;
			ans++;
		}
	}
	cout<<ans;
	return 0;
}