Thread: Hash Table

I am trying to create a hash table with linear probing. So, i am not wanting to use link list. I cant figure out what PRIVATE data members i will need. Can someone please help me out because the book i have uses link list and i am not sure what i need to get me going?

The information about each stock or mutual fund that i want to keep track of is:

* ticker symbol (e.g., IBM for International Business Machines)
* stock or fund name (e.g. International Business Machines)
* share price (e.g. 25.73)
(this should be stored as an int, not as a float or a double)
* Date of that share price (e.g. May, 23, 1967)

I will appreciate any help. I need to get going on this

Code:

#include "stock.h"

class hashmap
{
public:
	hashmap(int capacity);
	~hashmap(void);

	// Gets the stock associated with the provided stock symbol from the hashmap,
	// returns true if successful, false if not.
	//
	// Additional data returned:
	//		symbolHash:	result of applying hashStr() to stock symbol
	//		hashIndex:	array index produced by applying the modulo operator
	//						to the hash value produced by hashStr()
	//		usedIndex:	array index where the stock was actually found
	bool get(char const * const symbol, stock& s,
			 int& symbolHash, int& hashIndex, int& usedIndex) const;

	// Adds the stock to the hashmap, returns true if successful,
	// false if not (if the symbol is already present as a key or
	// if the hash table was already full).
	//
	// Additional data returned:
	//		symbolHash:	result of applying hashStr() to stock symbol
	//		hashIndex:	array index produced by applying the modulo operator
	//						to the hash value produced by hashStr()
	//		usedIndex:	array index where the stock will actually be stored
	bool put(const stock& s, int& symbolHash, int& hashIndex, int& usedIndex);

	// Removes the stock associated with the provided symbol from the hashmap,
	// returns true if successful, false if not (if the symbol is not present as a key).
	// Returns a copy of the stock in s.
	//
	// Additional data returned:
	//		symbolHash:	result of applying hashStr() to stock symbol
	//		hashIndex:	array index produced by applying the modulo operator
	//						to the hash value produced by hashStr()
	//		usedIndex:	array index where the stock was actually found
	bool remove(char const * const symbol, stock &s,
				int& symbolHash, int& hashIndex, int& usedIndex);

	friend ostream& operator<<(ostream& out, const hashmap& h);

private:


 

	static int hashStr(char const * const symbol);	// hashing function
	
};

Code:

#include "date.h"

using namespace std;

class stock
{
public:
	stock(char const * const symbol, char const * const name, int sharePrice, date priceDate);
		// sharePrice is given as a number of CENTS
	stock(const stock& s);						// copy constructor
	stock(void);								// default constructor
	char const * const getSymbol(void) const;
	stock& operator=(const stock& s);
	stock& operator=(stock const * const s);
	~stock(void);

	// display column headers
	static void displayHeaders(ostream& out);	// display the headers when this instance is printed

	// prints share price as DOLLARS
	// (e.g. 2483 would print out as 24.83 and 200 would print out as 2.00)
	friend ostream& operator<<(ostream& out, const stock& s);

	friend class hashmap;
	
	
private:

int  sharePrice;   // not sure if these are what i want
char* name;
char* symbol;
date priceDate;


};

Code:

#include "hashmap.h"

hashmap::hashmap(int capacity): capacity(capacity), hashTable( new item[capacity])
{

}

hashmap::~hashmap(void)
{
}

bool hashmap::get(char const * const symbol, stock& s,
				  int& symbolHash, int& hashIndex, int& usedIndex) const
{

  //hashIndex = this->hashStr(symbol);

	return false;
}

bool hashmap::put(const stock& s, int& symbolHash, int& hashIndex, int& usedIndex)
{

hashIndex = this->hashStr( s.symbol ); 
    symbolHash = (int&)s.symbol;
    usedIndex = hashIndex;



	
    return false;



	
}

I would imagine you'd just use a single array of objects (as opposed to an array of linked lists). Since for linear probing you just find the next available slot when there is a collision, you don't have to keep any extra data other than the object.

Thank, i would do something like this if symbol is the key?

Code:

struct item						
	{
		char* symbol;
		stock items;
	
		
		  
	};
	item* hashTable;	           
	size_t Tablesize;	
    int capacity;

Yeah, maybe. I don't see anything wrong with that on its surface.

You're using char* for a lot of things. I'd normally use the C++ string class. Using C-style strings means you'll have to do a lot of work to make sure the strings are copied properly, but if your stock class is done that might not be much of a problem.

Is the Tablesize supposed to be the same for all hash maps? If so, then it should be static, and you'll have to give more details why it didn't work.

If you're allowed to set a different Tablesize for different instances of the hash map, then it should not be static. That means either you shouldn't use it in hashStr (and maybe just do the calculation with Tablesize after you call hashStr) or hashStr shouldn't be static.

>> The place to do this is in the functions
>> that call this function.

That's the same thing I suggested (in parentheses in the last post). It is not saying to do it inside hashStr where you have it now, it is saying to do it in the code that calls hashStr. If you do that, you can leave Tablesize as not static and hashStr as static.

This is what i did. Is this really hashing?

Code:

bool hashmap::put(const stock& s, int& symbolHash, int& hashIndex, int& usedIndex)
{

 
    symbolHash = (int&)s.symbol;
    usedIndex = hashIndex;

    hashIndex = this->hashStr( s.symbol );   // call hashStr function

   hashIndex %= Tablesize;          

	
    return false;



	
}

Code:

int hashmap::hashStr(char const * const str)
{

 size_t length = strlen( str );

    int hash = 0;
    for ( unsigned i = 0; i < length; i++ )
    {
             hash = 31 * hash + str[i];
    }
    return hash ;

I was told that "You have to store an instance of stock at each slot"
"Each slot needs to contain either a pointer to an instance of stock,
or an entire instance of stock sitting there in the slot. The hash table
should be able to store things without necessarily knowing what they are."

Whats a slot? Am i doing what he said by
wrapping stock items; in the hasmmap class? I am going to use symbol as my key
Do i only need it in the stock class?

Code:

private:


	struct item						
	{
		char* symbol;
		int  sharePrice;
		char* name;
		date priceDate;
		stock items;     // probobly dont need this then?



	};

Here are my headers.

Code:

class stock
{
public:
	stock(char const * const symbol, char const * const name, int sharePrice, date priceDate);
	// sharePrice is given as a number of CENTS
	stock(const stock& s);						// copy constructor
	stock(void);								// default constructor
	char const * const getSymbol(void) const;
	stock& operator=(const stock& s);
	stock& operator=(stock const * const s);
	~stock(void);

	// display column headers
	static void displayHeaders(ostream& out);	// display the headers when this instance is printed

	// prints share price as DOLLARS
	// (e.g. 2483 would print out as 24.83 and 200 would print out as 2.00)
	friend ostream& operator<<(ostream& out, const stock& s);

	friend class hashmap;


private:

	int  sharePrice;
	char* name;
	char* symbol;
	date priceDate;
	static int size;


};

Code:

#include "stock.h"

class hashmap
{
public:
	hashmap(int capacity);
	~hashmap(void);


	bool get(char const * const symbol, stock& s,
		int& symbolHash, int& hashIndex, int& usedIndex) const;


	bool put(const stock& s, int& symbolHash, int& hashIndex, int& usedIndex);

	bool remove(char const * const symbol, stock &s,
		int& symbolHash, int& hashIndex, int& usedIndex);

	friend ostream& operator<<(ostream& out, const hashmap& h);

private:


	struct item						
	{
		char* symbol;
		int  sharePrice;
		char* name;
		date priceDate;
		stock items;     // probobly dont need this then?



	};
	item* hashTable;	           
	size_t Tablesize;	
	int capacity;



	static int hashStr(char const * const symbol);	// hashing function

};