Author: Stan Eisenstat
Subject: Re: [Cs223] Hwk5 Clarification 2
Date: Friday, 03 Apr 2020, 21:09:54

    > Message Posted By: Unknown
    >
    > In your last note, you stated that "The hash function applied to POSITION
    > specifies in which chain to store the triple." Just to clarify again, does
    > this mean that each chain in our hash table represents a potential "path"
    > to go from the initial position to the final goal.

No.

The hash table is a search table that is used to keep
track of which tray positions have been reached so that
they are not considered again if they are reached by
another sequence of moves.  Any other type of search
table could have been used instead (although an array or
linked list containing all of the positions would be too
slow to be practical).

The KEY in each (KEY,ATTR) pair stored in the table is
the POSITION; the ATTR is the pair (REACHED-FROM,NSTEPS).

As we discussed in class, the hash table is an array of
"chains", where each chain is a search table (normally
a linked list as in Aspnes' notes, but here a sorted
array).   The hash function applied to the KEY (i.e.,
to POSITION) specifies WHICH search table to look in
when searching and to add to when inserting.

If you still do not understand what is going on, please
read Aspnes' notes on hashing, listen to the first two
recorded lectures, and then contact me directly or see
one of the staff during office hours.  Thanks.

--Stan-