Computer Chess Club Archives

Search

Terms

Messages

Subject: Interesting numbers about hashing - 32 bits are clearly not enough

Author: J. Wesley Cleveland

Date: 12:21:17 12/06/01

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.

Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 14:53:24 12/06/01
Re: Interesting numbers about hashing - 32 bits are clearly not enough Slater Wold 14:02:42 12/06/01
- Re: Interesting numbers about hashing - 32 bits are clearly not enough Robert Hyatt 15:15:27 12/06/01
  - Re: Interesting numbers about hashing - 32 bits are clearly not enough Russell Reagan 14:37:56 12/07/01
  - Re: Interesting numbers about hashing - 32 bits are clearly not enough Slater Wold 05:13:14 12/07/01
  - Re: Interesting numbers about hashing - 32 bits are clearly not enough Steffen Jakob 00:57:00 12/07/01
  - Re: Interesting numbers about hashing - 32 bits are clearly not enough Eugene Nalimov 21:26:05 12/06/01
  - Re: Interesting numbers about hashing - 32 bits are clearly not enough Miguel A. Ballicora 19:51:48 12/06/01
    - Re: Interesting numbers about hashing - 32 bits are clearly not enough Robert Hyatt 20:08:43 12/06/01
      - Re: Interesting numbers about hashing - 32 bits are clearly not enough James T. Walker 20:49:14 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Robert Hyatt 21:09:35 12/07/01
      - Re: Interesting numbers about hashing - 32 bits are clearly not enough Miguel A. Ballicora 21:20:18 12/06/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Miguel A. Ballicora 21:22:19 12/06/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Uri Blass 22:46:57 12/06/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Uri Blass 06:00:27 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Miguel A. Ballicora 07:44:43 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Dieter Buerssner 08:38:17 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Miguel A. Ballicora 09:20:56 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 07:51:16 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 06:17:01 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Uri Blass 06:25:57 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Uri Blass 06:39:45 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Uri Blass 06:44:41 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 08:03:45 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 08:12:22 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Heiner Marxen 12:37:50 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Uri Blass 08:20:57 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 08:54:06 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Sune Fischer 08:16:51 12/07/01
        
        Re: Interesting numbers about hashing - 32 bits are clearly not enough Robert Hyatt 22:07:56 12/06/01
  - Re: Interesting numbers about hashing - 32 bits are clearly not enough J. Wesley Cleveland 18:30:46 12/06/01
- Re: Interesting numbers about hashing - 32 bits are clearly not enough Miguel A. Ballicora 15:13:55 12/06/01
Re: Interesting numbers about hashing - 32 bits are clearly not enough martin fierz 13:22:58 12/06/01
Re: Interesting numbers about hashing - 32 bits are clearly not enough Tom Kerrigan 12:42:36 12/06/01

This page took 0.01 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.