Author: Antonio Dieguez
Date: 13:45:08 09/23/01
Go up one level in this thread
On September 23, 2001 at 16:00:26, Uri Blass wrote: >On September 23, 2001 at 14:17:18, Antonio Dieguez wrote: > >>On September 23, 2001 at 02:50:59, Uri Blass wrote: >> >>>On September 22, 2001 at 23:42:29, James Swafford wrote: >>> >>>>On September 22, 2001 at 22:17:06, Uri Blass wrote: >>>> >>>>>On September 22, 2001 at 19:08:06, Torstein Hall wrote: >>>>> >>>>>>On September 22, 2001 at 18:29:46, Andreas De Troy wrote: >>>>>> >>>> >>>>>If the hash tables are very big then the probability for hash collision can >>>>>increase and if there are enough hash collisions the result can be a bad move. >>>>> >>>>>Uri >>>> >>>>Why do you think the size of the table has any bearing on the number >>>>of collisions? The number of collisions is a function of the >>>>"uniqueness" of your key, not how many entries are in your table. >>> >>>let take an extreme case: >>>suppose there is only one entry in your hash tables and you use 64 bit numbers. >>> >>>The probability for wrong hash collision is 1/2^64 for every new node after the >>>first node. >>> >>>If you have 1000000 entries in your hash tables and the hash tables are full >>>then the probability for hash collision is 1000000/2^64 for every new node. >> >>Hi. >> >>Just one thing, not everybody use part of the key for the hash index, me not for >>example but I know a lot do. > >How do you use hash tables in this case >You have a position and you need to decide if it is in the hash tables. > >I assume that the first thing that you do is compressing the position to a 64 >bit number > >Am I right? > >In this case you need to decide if the 64 bit number is in your hash tables. >How do you do it in a fast way? I don't know how much slower it is, but I maintain another number also for the index, the bigger the hashtable the bigger it is. I'm a bit surprised by your question because it is even more natural doing this way, and the other way is the one that looks like a trick. >If you have no way to calculate the hash index from the key then I do not see >a fast way to do it. > >I understand that the hash tables is a list of 64 bit numbers >if you have 2^20 64 bits number in your list then even if your list is ordered >by increasing order you may need 20 comparisons to find if a new 64 bit number >is in the list and I do not know how to put a new number in the list in the >right place without being too slow(O(2^20) steps in this case. > >I do not know if it is possible to do the following algorithm for an array a in >less than m steps: > >a[m+1],a[m+2],....a[n] are not changed >a[0]...a[m-1] values become the previous values of a[1]...a[m] >a[m] is a new number. > >The only way that I know to do it in C is >for (i=m;i>0;i--) > a[i-1]=a[i]; >a[m]=newnumber; > >Uri
This page took 0.02 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.