Author: rasjid chan
Date: 17:11:41 04/05/04
Go up one level in this thread
On April 05, 2004 at 19:48:12, Dann Corbit wrote: ONE ENTRY PER HASH TABLE IS PROBLEM ENOUGH and sufficient to engage me for some time. I will only take note of possibilities just in case I need them later. Rasjid >On April 05, 2004 at 19:37:20, Ricardo Gibert wrote: > >>On April 05, 2004 at 19:23:48, Dann Corbit wrote: >> >>[...] >> >>> >>>Complicated idea: >>>First level hash table is large >>>Second level hash table is log(big_table_size) >>>Third level hash table is log(second_level_size) >>>Fourth level hash table is log(third_level_size) >>>Hash replacement scheme is a function that eats several parameters and decides >>>heuristically which entries are the most important. >> >>I'm not understanding your use of the log() function above. How about pluging in >>some concrete numbers to illustrate what you mean? >e.g.: >First level hash has 1048576 elements and index is 20 bits so tag=64-20=44 bits >Second level hash has 32 elements and index is 5 bits so tag=64-5=59 bits >3rd level hash has 2 elements and index is 2 bits so tag = 62 bits >4th level hash has one element, no index and 64 bit tag. > >Second level index [in case of collision] is just (hash & (32-1)) >3rd level index is just (hash & 1) >last level needs no index > >Collisions are pretty rare. I think that the above is good enough, but maybe >someone else has a better idea.
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.