blocks|key|1597228|text|这是一个generalization+of+the+Birthday+problem。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1597229|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Birthday_problem#Generalizations^0|4|12|0|0^^$0|@$1|2|3|4|5|6|7|L|8|@]|9|@$A|M|B|N|1|O]]|C|$]]|$1|D|3|-4|5|6|7|P|8|@]|9|@]|C|$]]]|E|$F|$5|G|H|I|C|$J|K]]]]

This is a <a href="http://en.wikipedia.org/wiki/Birthday_problem#Generalizations" rel="noreferrer">generalization of the Birthday problem</a>.

blocks|key|1382247|text|对我来说，这听起来很像Birthday+Paradox。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|1382248|您应该能够将可能的生日集(365)替换为可能的散列(50000)，并运行与它们在那里提供的相同的计算。|1382249|如果您针对您的值修改了本文中提供的python脚本：|1382250|+def+bp(n,+d):
++++v+=+1.0
++++for+i+in+range(n):

+++++++++v+=+v+*+(1+-+float(i)/d)
++++return+1+-+v

+print+bp(2,+50000)|code-block|syntax|javascript|1382251|你最终会得到两个数字0.00002的碰撞几率。大约265个样本，你有大约50%25的机会发生碰撞。|1382252|entityMap|0|LINK|mutability|MUTABLE|url|http://en.wikipedia.org/wiki/Birthday_paradox^0|B|G|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|W|8|@]|9|@$A|X|B|Y|1|Z]]|C|$]]|$1|D|3|E|5|6|7|10|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|11|8|@]|9|@]|C|$]]|$1|H|3|I|5|J|7|12|8|@]|9|@]|C|$K|L]]|$1|M|3|N|5|6|7|13|8|@]|9|@]|C|$]]|$1|O|3|-4|5|6|7|14|8|@]|9|@]|C|$]]]|P|$Q|$5|R|S|T|C|$U|V]]]]

That sounds a lot like the <a href="http://en.wikipedia.org/wiki/Birthday_paradox" rel="noreferrer">Birthday Paradox</a> to me.

You should be able to just substitute the set of possible birthdays (365) with the possible hashes (50000) and run the same calculations they present there.

If you modify the python script presented in the article for your values:

<pre><code> def bp(n, d):
 v = 1.0
 for i in range(n):

 v = v * (1 - float(i)/d)
 return 1 - v

 print bp(2, 50000)
</code></pre>

You end up with the odds of collision on two numbers of 0.00002. Around 265 samples, you have around a 50% chance of having a collision.

blocks|key|1597360|text|首先计算没有碰撞的概率：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1597361|hashes_picked+=+100
single_collision_odds+=+50000

#+safe_combinations+is+number+of+ways+to+pick+hashes+that+don't+overlap
safe_combinations+=+factorial(single_collision_odds)+/+factorial(single_collision_odds+-+hashes_picked)

#+all_combinations+is+total+number+of+ways+to+pick+hashes
all_combinations+=+single_collision_odds+**+hashes_picked+++

collision_chance+=+(all_combinations+-+safe_combinations)+/+all_combinations|code-block|syntax|javascript|1597362|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

First calculate the probability that there is not a collision:

<pre><code>hashes_picked = 100
single_collision_odds = 50000

# safe_combinations is number of ways to pick hashes that don't overlap
safe_combinations = factorial(single_collision_odds) / factorial(single_collision_odds - hashes_picked)

# all_combinations is total number of ways to pick hashes
all_combinations = single_collision_odds ** hashes_picked 

collision_chance = (all_combinations - safe_combinations) / all_combinations
</code></pre>

blocks|key|1597423|text|在JS中|type|unstyled|depth|inlineStyleRanges|entityRanges|data|1597424|function+calculate(n,k)
{

++++var+result+=1;
++++for+(var+i=0;+i<k;+i%2B%2B){
++++++++result=result*n/(n-i)
++++}
++++result=(1-1/result)*100;
++++return+result;
}|code-block|syntax|javascript|1597425|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

and in JS 

<pre><code>function calculate(n,k)
{

 var result =1;
 for (var i=0; i&lt;k; i++){
 result=result*n/(n-i)
 }
 result=(1-1/result)*100;
 return result;
}
</code></pre>

Say I have a hash algorithm, and it's nice and smooth (The odds of any one hash value coming up are the same as any other value).

Now say that I know that the odds of picking 2 hashes and there being a collision are (For arguments sake) 50000:1.

Now say I pick 100 hashes. How do I calculate the odds of a collision within that set of 100 values, given the odds of a collision in a set of 2?

What is the general solution to this, so that I can come up with a number of hash attempts after which the odds fall below some acceptable threshold? E.g. I can say things like "A batch of 49999 hash value creations has a high chance of collision".

How to calculate the odds of a collision in hash algorithms?

翻译质量差，导致语言生硬或混乱。

没有提供实际的解决方法或示例。

解答不清晰，无法理解或解决问题。

页面排版不美观，阅读体验差。

文章

问答

视频

教程

学习中心

腾讯云实验室

直播

竞赛

腾讯云代码分析专区

腾讯iOA零信任安全管理系统专区

腾讯云架构师技术同盟交流圈

腾讯云数据库专区

腾讯云智能顾问专区

腾讯云原生专区

腾讯混元专区

腾讯云TCE专区

腾讯云Lighthouse专区

腾讯云HAI专区

腾讯云Edgeone专区

腾讯云存储专区

腾讯云智能专区

腾讯轻联专区 

腾讯云开发专区

TAPD专区

腾讯轻量云游戏服专区

腾讯云最具价值专家

腾讯云架构师技术同盟

腾讯云创作之星

腾讯云开发者先锋

腾讯云代码助手

云原生构建

TAPD 敏捷项目管理

Cloud Studio

SDK中心

API中心

命令行工具

涵盖代码开发、场景应用、自动测试全流程，助你从零构建专属AI助手

一站式MCP教程库，解锁AI应用新玩法

聚焦“写作效率、视觉美观与运行性能”三方面进行全面升级，为您提供更高效、稳定的创作环境

社区富文本&Markdown编辑器全新改版上线，欢迎大家体验!

诚挚邀请您参与本次调研，分享您的真实使用感受与建议。您的反馈至关重要，感谢您的支持与参与！

社区新版编辑器体验调研

假设我有一个哈希算法，它很好很平滑(出现任何一个哈希值的概率与任何其他值相同)。现在假设我知道选择2个散列和发生冲突的几率是(为了争论) 50000:1。现在假设我选择了100个哈希值。在给定2个值的碰撞几率的情况下，如何计算这100个值中的碰撞几率？这个问题的一般解决方案是什么，这样我就可以提出一些散列尝试，在这些尝...

问如何在哈希算法中计算冲突的概率？
EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在哈希算法中计算冲突的概率？EN

社区

活动

圈层

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

问如何在哈希算法中计算冲突的概率？
EN