字符串哈希——洛谷P3370

1.简介

本文主要介绍三种实现哈希表的方法：进制哈希，set哈希，map哈希。

2.进制哈希

#include<iostream>
#include<vector>
#define mod 1000
using namespace std;

int n,hs,ans;
vector<string> a[mod];                        //数组开多大，取决于mod取多大
string s;                                     // a[n]等价于a(n)，都是初始化vector一维大小

void f(string s)
{
	int i;
	for (i=0;i<s.size();i++)
		hs=(hs*130+s[i])/mod;                 //hs*130是为了进制转化，转化为130进制
	for (i=0;i<a[hs].size();i++)
		if (a[hs][i]==s)                      
			return;
	a[hs].push_back(s);                       //这就是为什么要用vector而不是简单的string a[mod]，目的是为了方便加入元素。并不是为了用vector可变长的特性。
	ans++;
}

int main()
{
	int i;
	cin>>n;
	while (n--)
	{
		cin>>s;
		f(s);	
	}
	cout<<ans;
	return 0;
} 

为什么vector是一维，但这里出现了二维？

实际上 [ i ] 并不是vector的二维，而是 a [ hs ] —>string的一维，string[ 1 ] 里不仅可以存一个字符，也可以是一个字符串。

3.set哈希

这里用到了set的特性：无重复元素。若集合中已有该元素，则下次再出现则不会再添加

#include<iostream>
#include<set>
using namespace std;

set<string> se;

int main()
{
    string s;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	cin>>s;
    	se.insert(p);
	}
	cout<<se.size();
    return 0;
}

4.map哈希

map实现基于键值对的hash。

重要的是键，下一次插入再碰到相同的键就不会再插入了。

至于键对应的值是多少都可以，用不到。

#include<iostream>
#include<map>
using namespace std;

map<string,int> m;

int main()
{
    string s;
    int n;
    cin>>n;
    for(int i=0;i<n;i++)
    {
    	cin>>s;
    	m[s]=1;
	}
	cout<<m.size();
    return 0;
}