[Lab]Storing stock prices in hashtable

[P1X3]

Another assignment from Data Structures class.

 

This time we will be storing stock prices in a hashtable and use linear probing to handle collisions.

As in previous thread, output of the program should be same as the one provided in lab3CorrectOutput.txt

 

So far I feel pretty good about this assignment and completed most of the code. However, I a question about search/get method. 

Let's say I add 5 stocks to the array and all of them happen to have same hashIndex.

AddStock(Apple); // HashIndex=5, UsedIndex = 5;

AddStock(Google); // HashIndex=5, UsedIndex = 6;

AddStock(IBM); // HashIndex=5, UsedIndex = 7;

AddStock(NASA); // HashIndex=5, UsedIndex = 8;

AddStock(LTT); // HashIndex=5, UsedIndex = 9;

 

 

Then I remove first 4 stocks leaving myself with stock "LTT" whose hashindex is still 5 and its stored in usedindex=9.

So I decide to search for stock "LTT". I calculate hashindex of LTT and it happens to be 5. I peek into 5 and it's null/empty. Okay lets check next one. Oups, that one is empty/null as well.

What happens next? (1) Well I guess it's not in the list. (2) lets keep looking until we reach hashIndex again.

This got me confused because of line "IBM not found (hc 0x00011A54, hi 9, ui -1, sl 2)" after IBM has been added, found and removed. Either I am misunderstanding what SL means or something else.

IF SequenceLength is 2 then doesnt that mean that code checked hashIndex and then hashIndex+1 only? Or did the code actually made loop searching for stock IBM?

CS260 - Lab3 - Your Name----------------------------------------------------------------------------no stocks----------------------------------------------------------------------------IBM not found (hc 0x00011A54, hi  9, ui -1, sl  1)added IBM     (hc 0x00011A54, hi  9, ui  9, sl  1)----------------------------------------------------------------------------symbol  name                                      price   date------  ----                                      -----   ----IBM     International Business Machines           25.73   May 23, 1967----------------------------------------------------------------------------found IBM     (hc 0x00011A54, hi  9, ui  9, sl  1)removed IBM   (hc 0x00011A54, hi  9, ui  9, sl  1)IBM not found (hc 0x00011A54, hi  9, ui -1, sl  2)IBM not removed

lab3.zip

[WanderingFool]

Read over the lab P1X3, and this is all I can guess (it would have been handy if your teacher had more not found entries).

I can think of a few ways to implement this (producing the same type of behaviour), but I will explain the way which is just easier to explain.  To start I will assume a stock can be in 3 states:

1.  Empty State: No values, hasn't been set at all
2. Invalid State: The item has been removed from the hashmap, and can be written over (different from Empty state, but add will still overwrite this)
3. Vaid State: Item is included in hash array

With this assumtion this is how I would conclude the "IBM not found (hc 0x00011A54, hi 9, ui -1, sl 2)" has an SL as 2.

1. IBM add: IBM tries to insert at 9, 9 is in an empty state so add to 9 (SL of 1).
2. IBM remove: IBM tries finding itself at 9, which it succeeds.  IBM will now set 9 to an invalid state. 
3. IBM find: IBM tries looking in 9, finds an invalid state (this means there is a chance IBM was inserted when there was a collision at 9).
   3.1.  IBM now has to look at 10, finds an Empty State (As an empty state never was inserted into, the HM has never had 10 set thus can cut short the search)

That is just my guess of how things work.  So in your example you provided, searching for LTT will find 4 invalid states, before finding the correct LTT.  If you searched Apple after removing those, you would find 4 invalid states, 1 valid state, and then an empty state (thus ending the search with a fail). 

[P1X3]

Read over the lab P1X3, and this is all I can guess (it would have been handy if your teacher had more not found entries).

I can think of a few ways to implement this (producing the same type of behaviour), but I will explain the way which is just easier to explain.  To start I will assume a stock can be in 3 states:

1.  Empty State: No values, hasn't been set at all
2. Invalid State: The item has been removed from the hashmap, and can be written over (different from Empty state, but add will still overwrite this)
3. Vaid State: Item is included in hash array

With this assumtion this is how I would conclude the "IBM not found (hc 0x00011A54, hi 9, ui -1, sl 2)" has an SL as 2.

1. IBM add: IBM tries to insert at 9, 9 is in an empty state so add to 9 (SL of 1).
2. IBM remove: IBM tries finding itself at 9, which it succeeds.  IBM will now set 9 to an invalid state. 
3. IBM find: IBM tries looking in 9, finds an invalid state (this means there is a chance IBM was inserted when there was a collision at 9).

   3.1.  IBM now has to look at 10, finds an Empty State (As an empty state never was inserted into, the HM has never had 10 set thus can cut short the search)

That is just my guess of how things work.  So in your example you provided, searching for LTT will find 4 invalid states, before finding the correct LTT.  If you searched Apple after removing those, you would find 4 invalid states, 1 valid state, and then an empty state (thus ending the search with a fail). 

 

Damn it. I haven't though about keeping track of slot state, and instead I just deleted the Stock from it.

I noticed that while keep track of slot states my insert/get/remove methods are 1/3 shorter.

I need to hit the book again.

[P1X3]

After changing search/get method I have finally completed the assignment. Completed to fulfill requirements.

Any kind of feedback is appreciated.

lab3.zip

[WanderingFool]

Not enough time to load it up it up in Visual studio, but read through your hashmap quickly.  A few comments

 

In HashMap::get

		// This is invalid/removed slot and next is empty		if (slots[usedIndex].slotState == Slot::INVALID && 			slots[usedIndex+1].slotState == Slot::EMPTY)		{			seqLength++;			break;		}

using slots[usedIndex+1] can be dangerous (no mod used).  Also it looks that portion of code could just be changed to this

		// This is invalid/removed slot and next is empty		if (slots[usedIndex].slotState == Slot::INVALID)		         continue;

In Hashmap::put

When an invalid state is found, only put the new value in it, if the stock doesn't exist later on (I hope you get this, don't have enough time to write why)

 

The rest looks pretty good from initial inspection though