Add to the Project #6 program, so that as your program builds the binary search tree, it also stores the name information in a hash table.  Use the HashtableOpen class and KWHashMap interface that are provided by the authors of the text book.  The key for the hashing must use an object that has both name and sex instance variables; the value to be stored in the table must be an object that contains all four elements associated with a baby name.  You will need to create a hashCode method for the key; you may be able to use the same equals and compareTo methods that you used for Project #6.

You are required to make two changes in the HashtableOpen class.  First, you must change the find method so that it does quadratic probing, rather than linear probing.  Second, you must change the value of START_CAPACITY so that it is appropriate for quadratic probing and so that it is large enough to prevent rehashing from being needed.  (To find an appropriate prime number of START_CAPACITY, I recommend looking up "prime numbers" on Google.)  To avoid rehashing, either set the LOAD_THRESHOLD so that rehash is never called, eliminate the call in the add method or set the START_CAPACITY so that the load factor is not an issue.  You should set the START_CAPACITY so that the load factor will be between 0.7 and 0.9.

Then, modify the reporting and testing portion of the program so that it reports the number of nodes examined during the building of the bst and the number of hash table entries checked during the building of the hash table.  The testing of the bst and hash table can be done together.  That is, as the program reads a name and sex from the lookFor.txt file, it can look up the entry in the bst and the hash table and display both results, showing the origin and meaning.  (Naturally, the results should be identical.)
 

Hand in a printout of your well-documented program, and a printout of the displays for both data files (captured from the screen).  You must create a folder named p7 under the folder named after you on the P: drive for COSC 310.  Copy into p7 all .java files that you created for this project.  The easiest way to capture the displays is to do a copy and paste from the output window in Eclipse to a NotePad file.  Do not put the displays in the p7 folder; do not do a print screen to capture an exact image of the screen - it will not show all of the log.
 

Following are the answers I get when finding the entries in lookFor.txt  using both the BST and the hash table.

Mae (girl)
Tree: Unknown  From the name Mary      Hash: Unknown  From the name Mary
Rosalind (girl)
Tree: Unknown  Unknown                 Hash: Unknown  Unknown
Desiree (girl)
Tree: Unknown  Desired                 Hash: Unknown  Desired
Avel (boy)
Tree: Greek  Breath                    Hash: Greek  Breath
Lamar (boy)
Tree: Old-German  Well-known land      Hash: Old-German  Well-known land
Shaine (boy)
Tree: Irish  God is gracious           Hash: Irish  God is gracious
Christiana (girl)
Tree: British  Christian, Annointed    Hash: British  Christian, Annointed
Esme (girl)
Tree: British  Gracious Protector      Hash: British  Gracious Protector
Santeago (boy)
Tree: Latin  Saint James               Hash: Latin  Saint James
Damita (girl)
Tree: Spanish  Baby Princess           Hash: Spanish  Baby Princess
Noël (boy)
Tree: Latin   Day of birth             Hash: Latin   Day of birth
Redford (boy)
Tree: Unknown  Unknown                 Hash: Unknown  Unknown
Afton (girl)
Tree: Celtic/Gaelic  From the Afton River Hash: Celtic/Gaelic  From the Afton River
Emmanuel (boy)
Tree: Unknown  From the name Emanuel   Hash: Unknown  From the name Emanuel
Bill (boy)
Tree: Unknown  From the name William   Hash: Unknown  From the name William
Dallin (girl)
Tree: Unknown  From the name Dale      Hash: Unknown  From the name Dale
Ariel (boy)
Tree: Hebrew  Lion of God              Hash: Hebrew  Lion of God
Mckale (girl)
Tree: Unknown  From the name Michael   Hash: Unknown  From the name Michael
Sallyna (girl)
Tree: Greek  Moon                      Hash: Greek  Moon
Macha (boy)
Tree: Unknown  Plain                   Hash: Unknown  Plain
Bikita (girl)
Tree: African  Anteater                Hash: African  Anteater