CSCI 3342 Submission 10
Implementing a HashTable Class

Overview

For this submission you will implement a HashTable class (according to the specifications in hashtable.h) that compiles separately and links with the supplied pre-compiled driver hashtable_main.o, and behaves like the supplied demo executable demo_hashtable_main. By now you will recognize this as being pretty much "business as usual".

The data items to be stored in the HashTable object (the "hash table") are birthdate/name pairs in which the birthdates are the keys and the names are the corresponding information associated with the keys. The names are those of allegedly "famous" people.

Once the data is loaded into the hash table, and after the user has chosen the table capacity and a probe increment size to use for collision resolution via open addressing, the user may perform searching, insertion, deletion and updates.

Steps to Perform

1. Copy the demo executable demo_hashtable_main, along with its required TextItems file hashtable.txt and the sample input file famous_names.txt. Then run the program, first choosing Option 2 from the menu, and reading carefully the program description displayed. Of course, you can also print off a hard copy of the file hashtable.txt and study it off-line, and you may want to do that as well, since there are several screens if you read it on-line.
2. Study the program description until you get a good feel for what to expect when you run the program.
3. When you do run the program, be sure you experiment enough to produce the message indicating each of the various errors described in hashtable.txt.
4. Also, be sure to try different table capacities and probe increment sizes and display the resulting hashLog file after each attempt. Be sure to use values that fail to put all the data in the hash table, as well as ones that succeed in placing all the data in the hash table.
5. Finally, in your testing, do some searching, additions, deletions and updates using birthdate keys that appear in the table as well as some that don't.
6. Write pseudocode for the HashTable class implementation, as specified in hashtable.h, and be sure to call your implementation file hashtable.cpp.
7. Translate your pseudocode into C++ and start your (incremental) testing using the supplied driver in the way suggested in previous submissions, and be sure to note in your self-assessment comment any parts of the class that you have not implemented ... the corresponding menu option should report a "not implemented" message if the user chooses an option that has not yet been implemented in the class. Continue testing your program until you are convinced it works correctly in all scenarios that are possible, given what has in fact been implemented.
8. Make sure your source code is identified, formatted, and documented properly, according to our current guidelines.
9. Finally, submit the required files by copying them to the appropriate submissions subdirectory.

Additional Notes, Requirements, Specifications and/or Hints (if any)

1. As is typical when you have a driver supplied in the form of a .o file, you need to insert a line like

   extern const string MY_ID_INFO = "\t\tLastname:Firstname:A00123456:u00";
   

   in the global namespace of your class implementation file, with your own identification information replacing the generic information shown here.
2. Note that menu options 3, 4, 6, 11 and 12 are present just to allow the user to experiment with the hash table in various ways. If this were a "production" program, those options would not be there. The program would simply allow database creation, followed by searching and possibly further insertions, deletions and updates.
3. Note the use of the size_t typedef, as seen in various places in the file hashtable.h. This is a typedef similar to the STL's size_type, since it too provides a convenient built-in alias for a non-negative integer type. To quote Danny Kalev, of InformIT:

   ... it was introduced to ensure portability of code. Consider the DOS days, when size_t was actually unsigned long. Old code that ran on DOS and which used size_t can compile on 32 bit systems without forcing the programmer to change every unsigned long in function prototypes and variable declarations to unsigned int. Instead, size_t is automatically mapped to the correct datatype used for storing sizeof() values on the target system. In fact, it's not much different from using a symbolic constant, say

   const int MAX=1024;
   

   to ease future maintenance of the code.

   Bottom line ... it's a very convenient type to use when you need a non-negative integer type here and there throughout your code, as you do here. It apparently lives in a number of different headers, including <cstddef>, <cstdlib> and <cstring>.

4. It is very important to realize that, when designing and writing this class, you do not have to arrange for any of the messages that you see displayed when running the program to appear. All of these are produced by the driver that links to your class to produce the executable. On the other hand, it is your class that produces the hashLog file, so your class does have to create that file and place the required and properly formatted contents into it. But, for example, the user interaction determining whether that file is actually produced is handled by the driver.
5. It is also important to realize the various "states" the hash table may be in. Before the user sets the capacity and probe increment, the hash table contains nothing and nothing can be put into it. That is, the user must set the capacity to a strictly positive value if the table is to receive data. When the user does set the capacity (and the probe value at the same time), and thereafter until the program ends or the hash table is cleared, each location in the table has exactly one of the three states shown in the following three rows (in which the value in the first column is in the birthDate field, and the value in the second column is in the name field):

   0    empty
   -1   empty
   date name
   

   The first state is the state of each location after the user has set the capacity and probe increment, but before the table (and that location in particular) has received any data. The second state is the state of a location that once held data but is now empty. The third state is the state of a location that currently holds data.
6. Note that there is no testing script required for this submission, but instead a "testing log file" (my_tests.log). Because the program is menu driven, with quite a few menu options, writing a testing script would be quite time consuming. But a "testing log" is quite easy to create. If you execute the Linux script command everything you do at the terminal from then onward will be captured in a file called typescript. This makes it very easy to run a program and capture the user interaction. The typescript file will also capture many strange-looking control characters, but the text will be very readable even without removing those extraneous characters. Terminating the script capture process is done with a Ctrl + D. The final step before submitting would be to rename the typescript file to my_tests.log.