hash ​

Hash算法的本质：
	将信息映射到一个d维向量上（哈希值），通过判定向量的相等，从而判定信息的相等
	最为常见的，d=1，此时哈希值就是一个数

数值映射hash：
	在理想概率均匀的情况下，可以认为冲突概率是1/p
	法一：模质数
		核心思想：
			将特别大的整数（需要用高精度存储的）映射成小整数
		常见应用：
			判断大整数是否相等
			可以方便的处理+,-,*,/等计算式的结果
			是绝大多数hash的基础
	法二：xorshift
		核心思想：
			将任意正常大小的整数映射成较大整数（通常是ull）
		标准实现：
			ull shift(ull x){
				x=x*rnd1+rnd2;
				x^=x<<13;
				x^=x>>17;
				x^=x<<5;
				return x;
　　}
	法三：多项式函数映射
		核心思想：
			将任意正常大小的整数映射成较大整数（通常是ull）
		运用：一般可以和xorshift、自然溢出一起使用，效率都比较高，且冲突概率非常小
　　法四：赋rand值
		核心思想：
			将小整数映射成较大整数（通常是ull）
集合映射hash：
	法一：xor hash
		核心思想：
			将集合里的数用数值映射hash以后再xor起来
		常见运用：
			处理涉及到出现次数奇偶性的问题
			处理差分更方便：树上路径，或是序列的子段
	法二：加法hash
		核心思想：
			将集合里的数用数值映射hash以后再加起来
		常见运用：
			处理涉及到出现次数是倍数的问题
			同样可以处理差分，略麻烦一些
字符串hash/多项式hash：
	核心思想：
		将其看作一个P进制数，进行数值映射
		注意，必须保证数的每一位值是正整数
		注意，应保证P大于每一位上取的数值
		注意，如果是考虑子串的话，一定要用自然溢出或双模
	冲突概率：
		两个长为n的串冲突概率：n/p
		x个长为n的串不冲突概率：(1-n/p)^(x*(x-1)/2)
树hash：
	树hash都是针对有根树的hash
	一个点的hash值等于1+子结点hash值组成的集合hash
	可以利用换根实现无根树hash
矩阵hash：
	利用向量乘矩阵加速的性质，随机一个向量即可
例题：
P2312：大整数映射
P1224：比较难想，尤其是k=3的情况
P8819

Hash算法的本质：
	将信息映射到一个d维向量上（哈希值），通过判定向量的相等，从而判定信息的相等
	最为常见的，d=1，此时哈希值就是一个数

数值映射hash：
	在理想概率均匀的情况下，可以认为冲突概率是1/p
	法一：模质数
		核心思想：
			将特别大的整数（需要用高精度存储的）映射成小整数
		常见应用：
			判断大整数是否相等
			可以方便的处理+,-,*,/等计算式的结果
			是绝大多数hash的基础
	法二：xorshift
		核心思想：
			将任意正常大小的整数映射成较大整数（通常是ull）
		标准实现：
			ull shift(ull x){
				x=x*rnd1+rnd2;
				x^=x<<13;
				x^=x>>17;
				x^=x<<5;
				return x;
　　}
	法三：多项式函数映射
		核心思想：
			将任意正常大小的整数映射成较大整数（通常是ull）
		运用：一般可以和xorshift、自然溢出一起使用，效率都比较高，且冲突概率非常小
　　法四：赋rand值
		核心思想：
			将小整数映射成较大整数（通常是ull）
集合映射hash：
	法一：xor hash
		核心思想：
			将集合里的数用数值映射hash以后再xor起来
		常见运用：
			处理涉及到出现次数奇偶性的问题
			处理差分更方便：树上路径，或是序列的子段
	法二：加法hash
		核心思想：
			将集合里的数用数值映射hash以后再加起来
		常见运用：
			处理涉及到出现次数是倍数的问题
			同样可以处理差分，略麻烦一些
字符串hash/多项式hash：
	核心思想：
		将其看作一个P进制数，进行数值映射
		注意，必须保证数的每一位值是正整数
		注意，应保证P大于每一位上取的数值
		注意，如果是考虑子串的话，一定要用自然溢出或双模
	冲突概率：
		两个长为n的串冲突概率：n/p
		x个长为n的串不冲突概率：(1-n/p)^(x*(x-1)/2)
树hash：
	树hash都是针对有根树的hash
	一个点的hash值等于1+子结点hash值组成的集合hash
	可以利用换根实现无根树hash
矩阵hash：
	利用向量乘矩阵加速的性质，随机一个向量即可
例题：
P2312：大整数映射
P1224：比较难想，尤其是k=3的情况
P8819