Author: Rémi Coulom

Date: 03:32:12 02/18/99

I just calculated the probability to have two identical values in a list of p values chosen at random among q possible values. Maybe everybody knew this already, but I was ignorant of the result and I find it is interesting. The result is, for large values of q and p < q, equivalent to exp(-(p*p)/(2*q)). It means that the probability of collision becomes high as soon as p is close to the square root of q. A consequence of this is that if you take 1,000 people, you have a very high probability that two of them have the exact same number of hair on their heads, assuming that the order of magnitude of this number is 100,000. A less funny consequence for computer chess programmers is that if you use 2^64 possible values for hash codes, you have a 1% probability of collision for 600 M values chosen at random. Of course, hash codes in a search tree are not independant and identically distributed. More experienced programmer maybe knew this since long, but I did not after 4 years of using a hash table and I thought some of you might be interested. By the way, I wonder how big were the hash codes in Deep Blue. Remi

- Re: Hash collisions and a little maths
**Vincent Diepeveen***18:06:53 02/18/99*- Re: Hash collisions and a little maths
**Rémi Coulom***03:11:22 02/24/99*- Re: Hash collisions and a little maths
**Don Dailey***21:32:00 02/24/99* - Re: Hash collisions and a little maths
**Dan Newman***14:38:53 02/24/99* - Re: Hash collisions and a little maths
**Vincent Diepeveen***05:03:23 02/24/99*- Re: Hash collisions and a little maths
**Ed Schröder***08:27:53 02/24/99*- Re: Hash collisions and a little maths
**Vincent Diepeveen***08:53:39 02/24/99*- Re: Hash collisions and a little maths
**Ed Schröder***10:06:33 02/24/99*- Re: Hash collisions and a little maths
**Don Dailey***12:24:30 02/24/99*- Re: Hash collisions and a little maths
**Vincent Diepeveen***05:21:38 02/25/99*

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths
- Re: Hash collisions and a little maths
**Andrew Dados***09:45:08 02/24/99*- Re: Hash collisions and a little maths
**Vincent Diepeveen***05:26:55 02/25/99*

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths
- Re: Hash collisions and a little maths
**Jouni Uski***04:19:43 02/18/99*- Re: Hash collisions and a little maths
**Kai Lübke***04:46:53 02/18/99*- Re: Hash collisions and a little maths
**Rémi Coulom***04:55:56 02/18/99*- Re: Hash collisions and a little maths
**Kai Lübke***04:07:30 02/19/99* - Re: Hash collisions and a little maths
**Jouni Uski***05:24:33 02/18/99*- Birthday collision... lets make an expriment
**Steffen Jakob***05:31:34 02/18/99*- Re: Birthday collision... lets make an expriment
**Enrique Irazoqui***08:26:31 02/18/99*- Re: Birthday collision... lets make an expriment
**Peter Hegger***09:12:06 02/18/99*- Re: Birthday collision... lets make an expriment
**Will Singleton***10:06:14 02/18/99*- Re: Birthday collision... lets make an expriment
**Paul Tillotson***21:29:15 02/18/99* - Re: Birthday collision... lets make an expriment
**James Robertson***12:07:44 02/18/99* - Re: Birthday collision... lets make an expriment
**Dan Homan***10:13:54 02/18/99* - Re: Birthday collision... lets make an expriment
**KarinsDad***10:13:01 02/18/99*- Re: Birthday collision... lets make an expriment
**Torstein Hall***11:59:26 02/18/99*- Re: Birthday collision... lets make an expriment
**Steffen Jakob***12:54:15 02/18/99*- Re: Birthday collision... lets make an expriment
**Oliver Y.***20:11:23 02/20/99*

- Re: Birthday collision... lets make an expriment

- Re: Birthday collision... lets make an expriment

- Re: Birthday collision... lets make an expriment

- Re: Birthday collision... lets make an expriment

- Re: Birthday collision... lets make an expriment

- Re: Birthday collision... lets make an expriment

- Re: Birthday collision... lets make an expriment
- Re: Hash collisions and a little maths
**Rémi Coulom***05:29:38 02/18/99*

- Birthday collision... lets make an expriment

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths

- Re: Hash collisions and a little maths
- Re: Hash collisions and a little maths
**Rémi Coulom***03:37:34 02/18/99*- Re: Hash collisions in chess programs?
**Inmann Werner***11:45:59 02/18/99*- Re: Hash collisions in chess programs?
**Dann Corbit***14:04:14 02/18/99*- Re: Hash collisions in chess programs?
**KarinsDad***15:09:25 02/19/99*

- Re: Hash collisions in chess programs?

- Re: Hash collisions in chess programs?

- Re: Hash collisions in chess programs?

This page took 0.1 seconds to execute

Last modified: Thu, 07 Jul 11 08:48:38 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.