Author: Uri Blass
Date: 13:00:26 09/23/01
Go up one level in this thread
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? 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.