frankHash s16

My advise in using this page

1. read through and understand hashing

2. use stock, student objects and implement a search function (such as lab 8)

   1. add a hash search implementation

   2. if you get stuck, the following is frank's implementation example

Data Structure

Data structure is usually the most important design in my program. The stockDB looks like this:

The implementation

Our stockDB use stock symbol as the key. The hash function used here is to add each character of the stock symbol (e.g. GOOG) and mod to our hash table size (i.e. (G+O+O+G)%HTSIZE).

The insert routine implements linear probing. Keep in mind that we need to check the flags. As long as it is NOT occupied (either empty or deleted), we can insert the entry.

The find routine is a bit more complicated. After we find the entry via key HT[index]==s, we copy the entire object to our input parameter.

There are other ways of design the find function. For example, you can do stock stockDBhash::find(stock s) which returns the found stock. However, you will need to figure out how to say "not found". Another way is to pass just the key into the find function such as int stockDBhash::find (string sym) In this case, find function needs to know not only stock, but also stock's members. My preference is always cleaner interfaces.