哈希表

哈希函数

有两个广受好评的 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;