We can get efficient algorithms both for finding and for inserting fish into the set if we use a hash table.  This representation has performance better than binary search or a binary search tree, O(1), for finding a fish and similar performance for inserting and deleting fish.  Thus we get good performance even if the fish population is dynamic, and there is no dependence on a bounded grid.  However, for the AllFish function we need to get all the fish in order, and this requires a sort.  Consequently, this aspect of the hash table implementation is slower that using a sorted vector or a binary search tree.  Since AllFish is called only once for each step of the simulation (not counting display), the overall performance is still very good.

We need to define a hash function to map the key for the table, a Position, to an index into the table.  Since the fish are randomly distributed throughout the environment, we can do this simply as follows.

We can define our hash function for a position, pos, by the formula

hash value  =  (pos.Row() + pos.Col()) % tableSize

Each entry in the hash table will be a linked list of fish, each of which mapped to the same index in the table under the hash function.  If the size of the table is about the same as the number of fish, then the average length of these linked lists will be 1 and most will have three or fewer fish.  For example, if we have the same set of fish as given above stored in a hash table of size 5 using the hash function given above, then the table would look like this:

The functions in the Environment class that previously accessed the apmatrix of fish will access this set instead.  The calls in the environment should be exactly the same as for the binary search tree implementation, so that the only changes that need to be made to the environment are changes in the include lines and a change to the hash table constructor to supply a size parameter.

1. We need to use the version of Position for which operator < and operator !=  have been overloaded, as for the BST implementation.
2. We construct a Directory (i.e. Lookup Table or Map) class that stores items with a key.  We can do this as a template class with two placeholders for types, one for the items to be stored (ItemType) and the other for the keys (KeyType). KeyType must have operator <  defined for it.  In our case KeyType will be Position.  The interface for this class should be exactly the same as for the BST version.
• The lookup table will be implemented with hash table  The constructor will have to take a parameter for the table size.  This is the only difference in the interface from the BST version.
• We need a private data member myTable, an apvector of pointers to dummy header nodes.
• The constructor for Directory should take a parameter to set the table size.
• We need to define the following functions, each with a helper function to do the recursion.
• Insert. Insert takes an item and key and adds the item to the hash with the key.  If the key is already in the tree, then the item with that key should be overwritten by the new item.
• Remove. Remove takes a key and removes the item stored with that key, if any, from the hash table.
• Lookup. Lookup takes a key parameter and a reference parameter item.  If the key is found in the tree, item is set to be the item stored with key and Lookup returns true, otherwise Lookup returns false.
• InorderList. InorderList should return an apvector containing all the items in the hash table in order by key. Use the quicksort for efficency. Hint: just move pointers\when you sort, rather than whole fish.
• We need to define a destructor that deallocates all memory from the linked lists.
3. The directoryhash.h file contains the class declaration for a hash table implemented directory.  The directoryhash.cpp file contains a partial implementation of Directory.  This is a templated hash table that was developed for other purposes and has simply been adopted here.  However, as a standard hash table, it does not have the inorder traversal.  The one function that needs to be added is the function InorderList that will return all the items in the hash table in order according to the key with which they were stored.  This assumes that an ordering is defined for the key type.  The specification for InorderList has been added to the directoryhash1.h file and the header is in the directoryhash0.cpp file, needing the code to be filled in.
• Hint:  sort the listnode pointers, using the key field for the sort, then copy into an apvector of the items.
4. After the directory based on a hash table is done, we need to replace the apmatrix myWorld with a Directory in the fish Environment class, just as for the BST implementation.
• Environment will also need private data members myNumRows and myNumCols if a bounded grid is used.
5. The following Environment functions need to be changed to use the Directory for accessing fish instead of the apmatrix.  These changes are identical to the changes made for the BST implementation, except that the constructor for the hash table must take a parameter for the size of the table.
• the constructor
• AddFish
• removeFish
• IsEmpty
• Update
• AllFish
• The functions NumRows and NumCols need to be modified to use myNumRows and myNumCols.