Hash Table

mrsirpoopsalot · 11-11-2009, 11:21 PM

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;



	
}

Daved · 11-12-2009, 01:05 PM

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.

mrsirpoopsalot · 11-12-2009, 06:06 PM

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;

Daved · 11-12-2009, 06:14 PM

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.

mrsirpoopsalot · 11-12-2009, 07:01 PM

I am trying to add data to the table.
It wont let me return the hash function.

Driver.cpp

Code:

static void addStock(const stock& s)
{
	int		usedIndex, hashIndex, symbolHash;

	if (hm.put(s, symbolHash, hashIndex, usedIndex)) {
		cout << "added " << left << setw(8) << s.getSymbol();
		printAdditional(symbolHash, hashIndex, usedIndex);
		}
	else
		cout << s.getSymbol() << " not added" << endl;
}

Code:

int main(void)
{
	_CrtSetDbgFlag( _CRTDBG_ALLOC_MEM_DF | _CRTDBG_LEAK_CHECK_DF);

	printStocks();
	searchStock("IBM");
	addStock(stock("IBM", "International Business Machines", 2573, date(date::MAY, 23, 1967)));

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 % Tablesize;

	
}

Code:

error C2597: illegal reference to non-static member 'hashmap::Tablesize'
error C3867: 'hashmap::Tablesize': function call missing argument list; use '&hashmap::Tablesize' to create a pointer to member

Tablesize is defined in the hashmap class private section
i tried declaring it as a static, but that didnt help much.

Code:

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;
		stock items;
	
		
		  
	};
	item* hashTable;	           
	size_t Tablesize;	
    int capacity;

 

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

Daved · 11-12-2009, 07:38 PM

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.

mrsirpoopsalot · 11-12-2009, 07:45 PM

There really isnt any requiremments.
however, the only thing that was said was.

You will need to apply
the modulo operator to the result of this function to generate
the required table index. The place to do this is in the functions
that call this function.

Thats confusing me because its saying to apply the mod in the function then it said not to!

Code:

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


	// Hash string according to the formula in java.lang.String.hashCode():
	//
	//   s[0]*(31^(n-1)) + s[1]*(31^(n-2)) + ... + s[n-1]
	//
	// s is the array of characters, n is the number of characters in the string,
	// and 31^n means 31 to the nth power.
	//
	// This function is declared static because its result depends
	// only on the characters in the string. You will need to apply
	// the modulo operator to the result of this function to generate
	// the required table index. The place to do this is in the functions
	// that call this function.
	//
	// You can and should do this computation entirely with integers. In other
	// words, there is no need to use floating point values. In particular, you
	// should not use the pow() function from <math.h> in this lab.

size_t length = strlen( str );

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

Daved · 11-12-2009, 11:42 PM

>> 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.

mrsirpoopsalot · 11-13-2009, 01:21 AM

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 ;

iMalc · 11-13-2009, 02:51 PM

A similar but better hash is FNV-1a, see here:
FNV hash

mrsirpoopsalot · 11-14-2009, 05:16 PM

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

};

iMalc · 11-14-2009, 09:10 PM

This is intended to be a design-time choice, not a run-time choice:

Quote:

"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."

To store things without knowing what they are to me suggests templates would be the thing to use. The only thing your hashmap class requires about the type that it stores, is that it contains a function that can provide a hash of that item's data. It doesn't need to actually know this, it's just an assumption it makes.

No need to use "(void)" in C++. Just use "()" especially considering you're put in in things like constructors that don't even exist in C anyway.

11-12-2009, 01:05 PM	#2
Daved Registered User Join Date: Jan 2005 Posts: 7,137	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.
Daved is offline

11-12-2009, 06:06 PM	#3
mrsirpoopsalot Registered User Join Date: Sep 2006 Location: vancouver wa Posts: 198	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;
mrsirpoopsalot is offline

11-12-2009, 06:14 PM	#4
Daved Registered User Join Date: Jan 2005 Posts: 7,137	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.
Daved is offline

11-12-2009, 07:38 PM	#6
Daved Registered User Join Date: Jan 2005 Posts: 7,137	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.
Daved is offline

11-12-2009, 11:42 PM	#8
Daved Registered User Join Date: Jan 2005 Posts: 7,137	>> 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.
Daved is offline

11-13-2009, 02:51 PM	#10
iMalc Algorithm Dissector Join Date: Dec 2005 Location: New Zealand Posts: 2,475	A similar but better hash is FNV-1a, see here: FNV hash __________________ My homepage Advice: Take only as directed - If symptoms persist, please see your debugger
iMalc is offline

Thread Tools
Show Printable Version Email this Page
Display Modes
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Dictionary in C# to hash table in C?	dinoman	C Programming	2	04-12-2009 09:23 PM
Writing array, to file	zootreeves	C Programming	9	09-08-2007 05:06 PM
Group Project Help/Volunteer	DarkDot	C++ Programming	3	04-24-2007 11:36 PM
Hash table creation and insertion	tgshah	C Programming	1	01-23-2006 07:54 PM
Not sure on hash table memory allocations	Thumper333	C Programming	3	09-27-2004 09:00 PM