哈希表

哈希函数

有两个广受好评的 ull 哈希函数。

• 一种是 __builtin_bswap64：

  struct hh{
  	il size_t operator()(ull x)const{
  		constexpr static ull C=ull(4e18*acos(0))|71;
  		return __builtin_bswap64(x*C);
  	}
  };
  

• 一种是 splitmix64：

  struct hh{
  	il unsigned operator()(ull x)const{
  		x+=0x9e3779b97f4a7c15;
  		x=(x^(x>>30))*0xbf58476d1ce4e5b9;
  		x=(x^(x>>27))*0x04d049bb133111eb;
  		return x^(x>>31);
  	}
  };
  

根据喜好使用即可。

STL 哈希表

首先，unordered_map、cc_hash_table 和 gp_hash_table 的效率完全基于题目随机。

但一般情况下，gp_hash_table 的效率是最快的，但代价是其空间消耗翻倍。若要向哈希表中存储 \(10^7\) 级别的数据，需要格外注意这一点。

手写哈希表

主要由哈希函数和模数两部分构成。哈希函数从上面的两个里面任选一个就行。模数决定了哈希表的空间复杂度，一般和数据范围差不多就行，且一般是质数。

一些常用的模数：\(10^4+7\)，\(10^5+3\)，\(10^5+19\)，\(10^6+3\)，\(10^7+19\)，\(10^8+7\)。

一个简化的只需实现 [] 运算符的哈希表模板，实现了从 ull 到 ull 的映射：

struct H{
	static constexpr int M=1e7+19;
	int head[M],tot;
	struct{
		ull key,val;
		int to;
	}e[M];
	il unsigned hh(ull x){
		static constexpr ull C=ull(4e18*acos(0))|71;
		return __builtin_bswap64(x*C);
	}
	il int fnd(ull v){
		int u=hh(v)%M;
		for(int i=head[u];i;i=e[i].to) if(e[i].key==v) return i;
		e[++tot]={v,0,head[u]},head[u]=tot;
		return tot;
	}
	il ull& operator[](ull x){
		return e[fnd(x)].val;
	}
}mp;

更全的模板：

struct H{
	static constexpr int M=1e7+19;
	int head[M],tot;
	struct Data{
		ull key,val;
		int to;
	}e[M];
	il unsigned hh(ull x){
		static constexpr ull C=ull(4e18*acos(0))|71;
		return __builtin_bswap64(x*C);
	}
	il int fnd(ull v,bool typ=0){
		int u=hh(v)%M;
		for(int i=head[u];i;i=e[i].to) if(e[i].key==v) return i;
		if(typ) e[++tot]={v,0,head[u]},head[u]=tot;
		return tot;
	}
	il ull& operator[](ull x){
		return e[fnd(x,1)].val;
	}
	il bool count(ull x){
		return fnd(x);
	}
	il int size(){
		return tot;
	}
	Data* begin(){
		return e+1;
	}
	Data* end(){
		return e+tot+1;
	}
}mp;