chanllage

 ACM 󰈭 237字

有一些有趣但是大概需要高深数学知识的计算机问题悬而未决,特此记录。

张帆猜想

哈希冲突概率

有等式$(a_1^k+a_2^k+…+a_n^k) % 2^{64}=(b_1^k+b_2^k+…+b_n^k)% 2^{64}$,

定义“冲突“为:满足上述等式的两个多重集合{an}{bn}不完全相同。

希望说明:当n为1e5的级别时,k=2时冲突概率极高,而当k>=3时冲突的概率就会降低到一个可以接受的程度。

集合{an}{bn}的元素可能可以认为是在[0, 2^64)均匀分布的,不过这一点没有仔细考究,也没有造若干数据进行检验。

chanllage
嗨! 这里是 rqdmap 的个人博客, 我正关注 GNU/Linux 桌面系统, Linux 内核 以及一切有趣的计算机技术! 希望我的内容能对你有所帮助~
如果你遇到了任何问题, 包括但不限于: 博客内容说明不清楚或错误; 样式版面混乱; 加密博客访问请求等问题, 请通过邮箱 rqdmap@gmail.com 联系我!
修改日志
  • 2024-01-05 00:01:57 合并小众分类的文章
  • 2023-09-01 18:14:49 单独划分ACM专题; 移动部分博客进入黑洞归档
  • 2023-05-29 23:05:14 博客结构与操作脚本重构
  • 2023-05-08 21:44:36 博客架构修改升级
  • 2022-11-16 01:27:34 迁移老博客文章内容