Author: Angrim
Date: 15:03:03 09/24/01
Go up one level in this thread
On September 24, 2001 at 16:24:01, Robert Hyatt wrote: >On September 24, 2001 at 15:31:58, Antonio Dieguez wrote: > >>On September 24, 2001 at 14:33:49, Uri Blass wrote: >> >>>On September 24, 2001 at 13:53:58, Antonio Dieguez wrote: >>> >>>> >>>>>Several hash into 2 X 32 bit values. You store one value, you use the other >>>>>to generate the hash index. This is not quite as safe as a true 64 bit hash >>>>>signature where all 64 bits are used, but it is pretty good. If you have >>>>>one million entries in the table, your hash key is 52 bits long, effectively, >>>>>which is not horrible. Not as good as 64, but not horrible. >>>> >>>>hi. isn't one million of entries around 2^20, so just 44 bits are used for the >>>>key, (not 52) ? >>> >>>no >>>My understanding is that in this case every chess position is practically >>>compressed to 52 bits(52=32+20) >>>20 bits are used for the index when 32 bits are used for the position. >> >>oops yes I "just" mixed up what Hyatt said... >>but what does this mean >>>>>one million entries in the table, your hash key is 52 bits long, effectively, >>>>>which is not horrible. Not as good as 64, but not horrible. >> >>who cares if it is 52 or other? what about more hash entries, then that will >>surpass 64, funny. We can't compare just that numbers. > > > > >Who cares about the number of hash entries? We aren't scanning the entire table >to find a false match. We index to one position only. Suppose the table was >2^64 in size so you could store the entire set of possible hash signatures. >Does that increase the chances of a collision? Suppose your table has 1 >entry. you can _still_ get a collision. > >I think you are trying to consider "time" in the equation here. The farther >apart two entries are stored in time, the less chance they will falsely match >since the first has a greater chance of getting overwritten before the second >is reached. The chances of a collision with 64 bits are so remote, I wouldn't >give it a moment's thought. Because even with a _full_ 64 bit address space >for the table, the probability of a false match is one out of 2^64. Very no, the probability of a false match if you have 64 bit hash values and a full 2^64 entry hash table is 100% as soon as you search a position that you have not already searched and stored. >small. Because for any 64 bit hash signature, there is only _one_ place I >will try to find it stored in the table, regardless of how large the table >is. With that small a chance to get a false match with a full address space, >smaller tables only reduce the chances further due to overwrites. With a table of 2^64 entries, the "one place" that you probe will certainly have a match on all 64 bits. So if you search a new position it will give a false match. Angrim
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.