OI-wiki icon indicating copy to clipboard operation
OI-wiki copied to clipboard

Add 卡掉自然溢出Hash的方法

Open Great-designer opened this issue 1 year ago • 2 comments

页面英文名

https://oi-wiki.org/graph/tree-hash/

我希望能添加的内容是

加到《树哈希》,另设自然溢出Hash一节即可

我了解到的相关参考资料有

自然溢出Hash使用的模数是2^32或者2^64,模该模数的群结构最高阶为2^30或者2^62

借助这样的特性可以卡掉自然溢出Hash

随手在网上可以搜到一些不太官方的文章:

  • https://www.bbsmax.com/A/l1dyp37b5e/
  • https://blog.csdn.net/wzq_QwQ/article/details/46757551
  • https://blog.csdn.net/weixin_45750972/article/details/107457997

Great-designer avatar Mar 21 '23 06:03 Great-designer

话说这个是不是加到字符串哈希里比较好

jifbt avatar Apr 06 '23 07:04 jifbt

据我所知,卡树哈希一般用与模数无关的方法,例如构造两个对哈希的贡献值相同的结点,然后两棵树分别有其中一个结点。

jifbt avatar Apr 06 '23 07:04 jifbt