Between moves, I find the nodes that can be recycled and put them on a free list. If the free list is empty I do a very short search, then give up.
David > -----Original Message----- > From: [email protected] [mailto:computer-go- > [email protected]] On Behalf Of Peter Drake > Sent: Sunday, July 05, 2009 9:42 PM > To: computer-go > Subject: Re: [computer-go] Hash tables > > On Jul 5, 2009, at 9:05 PM, David Fotland wrote: > > > The hash table contains a linked list of nodes with the same hash > > index. > > Okay, I've almost got it. > > If you're hashing by chaining, you presumably go to the appropriate > slot in the table, then traverse the (short) linked list of nodes > hanging from that slot. If the node you want isn't present, though, > you have to find another node you can overwrite, presumably from > another chain in the hash table. How do you find such a node without a > lengthy search? > > > I actually have fewer total nodes than you do. The commercial version > > allocates 30K nodes per CPU core. The version in the world > > championship had > > much more, but the commercial version can't be that greedy for memory. > > That's reassuring. > > Peter Drake > http://www.lclark.edu/~drake/ > > _______________________________________________ > computer-go mailing list > [email protected] > http://www.computer-go.org/mailman/listinfo/computer-go/ _______________________________________________ computer-go mailing list [email protected] http://www.computer-go.org/mailman/listinfo/computer-go/
