Author: Dann Corbit
Date: 16:48:12 04/05/04
Go up one level in this thread
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.