On Jul 6, 2009, at 9:26 AM, Isaac Deutsch wrote:
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?
Firstly, I don't understand the problem you describe: "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." Are
you referring to a node that was inserted, then overwritten, and now
you need it again?
No, I'm referring to a node that was inserted and is no longer
relevant. For example, if my tree is
A
B
C
D
E
(that is, B and D are children of the root, C is the child of B,
etc.), then I move to B, the remaining tree is:
B
C
The nodes A, D, and E are no longer relevant, because they can no
longer be reached. The challenge is to make these available for reuse
(overwriting) without traversing all of memory.
Secondly, to find a node that has to be overwritten, do you have a
criteria that always finds "the node the least probable to be used
again", or can it also return that there aren't any nodes in this
chain that should be overwritten? The first one would always limit
the search to a single chain, without looking at other chains in the
hash table, wouldn't it?
I wasn't aiming for that level of sophistication; just hoping to reuse
nodes that are no longer in the tree (dag) because they're along roads
not taken.
Peter Drake
http://www.lclark.edu/~drake/
_______________________________________________
computer-go mailing list
[email protected]
http://www.computer-go.org/mailman/listinfo/computer-go/
