有一些有趣但是大概需要高深数学知识的计算机问题悬而未决,特此记录。
张帆猜想
哈希冲突概率
有等式$(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)均匀分布的,不过这一点没有仔细考究,也没有造若干数据进行检验。