OI-wiki
OI-wiki copied to clipboard
Add 卡掉自然溢出Hash的方法
页面英文名
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
话说这个是不是加到字符串哈希里比较好
据我所知,卡树哈希一般用与模数无关的方法,例如构造两个对哈希的贡献值相同的结点,然后两棵树分别有其中一个结点。