Hash Table

This is a discussion on Hash Table within the C++ Programming forums, part of the General Programming Boards category; I am trying to create a hash table with linear probing. So, i am not wanting to use link list. ...

  1. #1
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221

    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;
    
    
    
    	
    }

  2. #2
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  3. #3
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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;

  4. #4
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  5. #5
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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
    	
    };
    Last edited by mrsirpoopsalot; 11-12-2009 at 06:17 PM.

  6. #6
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    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.

  7. #7
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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;
    	
    }
    Last edited by mrsirpoopsalot; 11-12-2009 at 09:41 PM.

  8. #8
    Registered User
    Join Date
    Jan 2005
    Posts
    7,317
    >> 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.

  9. #9
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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 ;

  10. #10
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    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

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

  11. #11
    Registered User
    Join Date
    Sep 2006
    Location
    vancouver wa
    Posts
    221
    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
    
    };

  12. #12
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,304
    This is intended to be a design-time choice, not a run-time choice:
    "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.
    My homepage
    Advice: Take only as directed - If symptoms persist, please see your debugger

    Linus Torvalds: "But it clearly is the only right way. The fact that everybody else does it some other way only means that they are wrong"

Popular pages Recent additions subscribe to a feed

Similar Threads

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21