2020-team-0x06-Hashing

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

[/wiki/2020-team0x06 返回]

== Hashing ==


=== Schwartz-Zippel lemma ===

 * 若hash值由(多元)n次函数在模mod下确定，则hash碰撞的概率为n/mod
 * mod最好为质数

=== Sequence ===

 * 序列ai的hash函数为\sigma ai * r^i^，其中r为mod内随机整数
 * 环hash可由环的最小表示确定

=== (multi)Set ===

 * 设集合内任意元素为x，则集合的hash函数为\prod (x + r)

=== Tree ===

 * 对每个高度i随机一个权值ri，对于以x为根且高度为i的子树，其hash函数为其儿子hash值集合在ri下的hash，即\prod (son + ri)
 * 无根树可以重心为根

=== Graph ===

 * 设h(v, d)为节点v的d级hash，则h(v,d)为h(son,d-1)的有序序列的hash，整个图的hash为h(v,maxd)的有序序列的hash，h(v,0)=1
 * '''未经证明'''

=== Reference ===

[http://rng-58.blogspot.com/2017/02/hashing-and-probability-of-collision.html rng_58’s blog]

[/wiki/2020-team0x06 返回]

Hashing

Schwartz-Zippel lemma

  • 若hash值由(多元)n次函数在模mod下确定，则hash碰撞的概率为n/mod
  • mod最好为质数

Sequence

  • 序列ai的hash函数为\sigma ai * ri，其中r为mod内随机整数
  • 环hash可由环的最小表示确定

(multi)Set

  • 设集合内任意元素为x，则集合的hash函数为\prod (x + r)

Tree

  • 对每个高度i随机一个权值ri，对于以x为根且高度为i的子树，其hash函数为其儿子hash值集合在ri下的hash，即\prod (son + ri)
  • 无根树可以重心为根

Graph

  • 设h(v, d)为节点v的d级hash，则h(v,d)为h(son,d-1)的有序序列的hash，整个图的hash为h(v,maxd)的有序序列的hash，h(v,0)=1
  • 未经证明

Reference

rng_58’s blog