Author: martin fierz
Date: 13:22:58 12/06/01
Go up one level in this thread
On December 06, 2001 at 15:21:17, J. Wesley Cleveland wrote: >This problem is like the problem "How many people does it take before >it is probable that two have the same birthday ?". The answer, which >many people find suprising is 23. To calculate this, calculate the >probability p, that two people have different birthdays = 364/365. >Then calculate how many pairs of people n, you need before this is less >than 1/2, p^n <.5. Then find the number of people g, which taken two at >a time is >= n, g = n*(n-1)/2. > >The same method tells you how many different positions you can have >before it is likely that two will have the same hash key. > >32 bits 77163 >48 bits 1.97536627683E+7 >64 bits 5.05693754118E+9 > > >Thanks to Cliff Leitch for providing a high precision freeware calculator. aloha, two notes on this: - if you don't need high precision, then you can calculate the number as sqrt(n), that is for 32 bits it's just 2^16 (65'000), for 64 2^32 (4'000'000'000). like this you can do it in your head without high precision freeware calculators :-) - these numbers do not tell the whole story. you are essentially asking "if my hashtable is infinitely large, how big is the chance of a hash collison?", because you assume that the first instance of the same position is still in the hashtable - which it may not be in reality because it has been overwritten. this means that for a normal-sized hashtable (1 million entries?) the collison probability is smaller than what you calculate. cheers martin
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.