Compsci 108, Fall 2005, C/C++ Questions

The code in hashsearch.cpp is a subset of the code we have studied in class. This code reads a text file and determines how many unique words there are in the file. Each word is hashed and stored in a "home-brewed" HashSet class.

When run (as shown below) the output for different files indicates how many unique words there are in each file. 

prompt hashsearch kjv10.txt
reading kjv10.txt total words: 823135 unique words: 32674
reading time 0.44
prompt hashsearch hawthorne.txt
reading hawthorne.txt total words: 85753 unique words: 13542
reading time 0.04
Code Questions:
  1. Why is the method hash private in HashSet?
  2. Why is the return type of hash an unsigned int?
  3. Why is the method hash const when it's only called from method HashSet::add which is not const?
  4. The code below is from method HashSet::add. Describe the general purpose of the code (why it's needed) and describe each line of code (what it does and why). char * copy = new char[strlen(s)+1]; strcpy(copy,s);
  5. Suppose the two lines above are replaced by this single line: char * copy = s; The code compiles and executes, but produces different output. What do you expect the new output to be and why?
  6. Someone proposes a new implementation of method size as shown below, claiming that this saves space because the instance variable mySize is no longer needed. This implementation is correct. Comment on whether this method is better and why. int HashSet::size() const{ int total = 0; for(int k=0; k < TABLE_SIZE; k++){ Node * list = myTable[k]; while (list != 0){ total++; list = list->next; } } return total; }
  7. In the current version, the HashSet method HashSet::add can call new twice, allocating storage for a string and for a node. Ideally, every call of new will be accompanied by a call of delete. This usually happens in the destructor of a class when the class is responsibile for managing its storage (e.g., when it calls new it should call delete).

    Here are examples of how to call delete after calling new:

    char * s = new char[10]; strcpy(s,"hello"); // do something with s delete [] s; Info * head = new Info("word",NULL); // do something with head delete head; In the destructor, you should delete every string and every node that have been allocated via a call to HashSet::add, i.e., the storage allocated by the HashSet object whose destructor will (automatically) be called.

    Once you delete the storage referenced by a pointer, it is an error to access that storage. This means that you cannot access the fields of a node/struct after the node/struct has been deleted.

    (over)

    HashSet::~HashSet() { }