hashing issue. Help!

This is a discussion on hashing issue. Help! within the C++ Programming forums, part of the General Programming Boards category; Hi, I'm a newbie in Computer Sciences desperately trying to get some C++ homework help! I've gone to many tutors, ...

  1. #1
    Registered User
    Join Date
    May 2010
    Posts
    5

    Unhappy hashing issue. Help!

    Hi, I'm a newbie in Computer Sciences desperately trying to get some C++ homework help! I've gone to many tutors, I've asked my classmates, and they were unable to help me (or not willing to help me). My prof was the only one helpful but was not available on the weekend. So now I'm turning to the Internet. Desperate cries calls for desperate measures.

    I'm supposed to write code for a hashmap to function. But I'm currently having problem with the get() function. When it runs, it crashes somewhere on the modulo calculation, and when I look at it, somehow by magic the capacity had been assigned a zero when I'm guessing it's not supposed to.

    Here is the hashmap.h

    Code:
    #pragma once
    
    #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
    	//		chainLgth:	length of the linear probe chain to the stock
    	bool get(char const * const symbol, stock& s,
    			 unsigned int& symbolHash, unsigned int& hashIndex,
    			 unsigned int& usedIndex, unsigned int& chainLgth)
    			 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
    	//		chainLgth:	length of the linear probe chain to the stock
    	bool put(const stock& s,
    			 unsigned int& symbolHash, unsigned int& hashIndex,
    			 unsigned int& usedIndex, unsigned int& chainLgth);
    
    	// 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
    	//		chainLgth:	length of the linear probe chain to the stock
    	bool remove(char const * const symbol, stock &s,
    				unsigned int& symbolHash, unsigned int& hashIndex,
    				unsigned int& usedIndex, unsigned int& chainLgth);
    
    	friend ostream& operator<<(ostream& out, const hashmap& h);
    
    private:
    	static unsigned int hashStr(char const * const symbol);		// hashing function
    
    	struct slot
    	{
    		enum state {empty, deleted, full};
    
    		stock	slotStock;
    		state	slotState;
    	};
    
    	slot	*slots;
    	int		capacity;
    	int		nStocks;
    
    	int		nextIndex(int index) const;
    	//intline void nextIndex(int& index) const;
    	int		prevIndex(int index) const;
    	bool	slotEmpty(int index) const;
    	void	setSlotEmpty(int index);
    };
    Here is the hashmap.cpp. This is where the problem is located at (in red).

    Code:
    // enable Visual C++ memory leak checking
    #ifdef _DEBUG
    #include <ostream>
    #define _CRTDBG_MAP_ALLOC
    #include <crtdbg.h>
    #define DEBUG_NEW new(_NORMAL_BLOCK, __FILE__, __LINE__)
    #define new DEBUG_NEW
    #endif
    
    #include "hashmap.h"
    
    hashmap::hashmap(int capacity) :
    	slots(new slot[capacity])
    		//constructor. This is the good constructor. No changes!
    {
    	for (int i = 0; i < capacity; i++)
    		slots[i].slotState = slot::empty;
    }
    
    hashmap::~hashmap(void)
    {
    	delete[] slots;
    }
    
    bool hashmap::get(char const * const symbol, stock& s,
    				  unsigned int& symbolHash, unsigned int& hashIndex,
    				  unsigned int& usedIndex, unsigned int& chainLgth)
    	 const
    {
    
    	/* INSTRUCTION */
    	// use hashStr to generate a hash code for symbol
    	// compute array index using % or the equivalent
    	// if slots[index] empty, stock is not present
    	// else do linear probing to find either an empty slot or the stock we're looking for
    
    	int tempIndex;
    
    	symbolHash = hashStr(symbol);
    	hashIndex = symbolHash % capacity;
    
    	tempIndex = hashIndex+1;
    
    	if(slots[hashIndex].slotState==slot::empty)
    		{
    		return false;
    		}
    
    	while(tempIndex != hashIndex)
    	{
    
        if(tempIndex > capacity)
    		{
    		tempIndex = 0;
    		}
    	}
    
    	if(slots[tempIndex].slotState==slot::empty || slots[tempIndex].slotState==slot::deleted)
    		{
    		return false;
    		}
    
    	if(0==strcmp(slots[tempIndex].slotStock.getSymbol(), symbol))
    		{
    			{
    			s.copyData(slots[hashIndex].slotStock);
    			return true;
    			}
    			tempIndex++;
    		}
    
    	return false;
    }
    
    bool hashmap::put(const stock& s,
    				  unsigned int& symbolHash, unsigned int& hashIndex,
    				  unsigned int& usedIndex, unsigned int& chainLgth)
    {
    
    	// use hashStr to generate a hash code for symbol
    	// compute array index using % or the equivalent
    	// if slots[index] empty, store the stock there
    	// else do linear probing to find an empty slot
    
    
    
    	return false;
    
    
    }
    
    bool hashmap::remove(char const * const symbol, stock& s,
    					 unsigned int& symbolHash, unsigned int& hashIndex,
    					 unsigned int& usedIndex, unsigned int& chainLgth)
    {
    	return false;
    }
    
    unsigned int hashmap::hashStr(char const * const str)
    {
    	// Hash string according to the formula in java.lang.String.hashCode():
    	//
    	//   str[0]*(31^(n-1)) + str[1]*(31^(n-2)) + ... + str[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.
    
    	return 0;
    }
    
    ostream& operator<<(ostream& out, const hashmap& h)
    {
    	out << "<print the contents of the hashmap>" << endl;
    	return out;
    }
    My brother told me that it was a memory code and I should try to restart the program completely so that the problem will go away, but the problem is still there.

    I'm not asking anyone to do the homework for me. I just want someone... SOMEBODY descent to help me on what I'm doing wrong and what a correct piece of code should I go for, cuz I'm totally stuck. The assignment is due very soon, and I have a big Bio test to study for on the next day, and my mind is going crazy!!

    I appreciate all the help I can get to get through this. Thank you!!

  2. #2
    a_capitalist_story
    Join Date
    Dec 2007
    Posts
    2,639
    Where do you ever set the value of the member variable capacity?
    Last edited by rags_to_riches; 05-15-2010 at 11:13 AM. Reason: Clarify

  3. #3
    spurious conceit MK27's Avatar
    Join Date
    Jul 2008
    Location
    segmentation fault
    Posts
    8,300
    You don't assign to capacity in the constructor. Use:

    Code:
    hashmap::hashmap(int capacity) :
    	slots(new slot[capacity])
    		//constructor. This is the good constructor. No changes!
    {
            this->capacity = capacity;
    	for (int i = 0; i < capacity; i++)
    		slots[i].slotState = slot::empty;
    }
    C programming resources:
    GNU C Function and Macro Index -- glibc reference manual
    The C Book -- nice online learner guide
    Current ISO draft standard
    CCAN -- new CPAN like open source library repository
    3 (different) GNU debugger tutorials: #1 -- #2 -- #3
    cpwiki -- our wiki on sourceforge

  4. #4
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    Quote Originally Posted by MK27 View Post
    You don't assign to capacity in the constructor. Use:

    Code:
    hashmap::hashmap(int capacity) :
    	slots(new slot[capacity])
    		//constructor. This is the good constructor. No changes!
    {
            this->capacity = capacity;
    	for (int i = 0; i < capacity; i++)
    		slots[i].slotState = slot::empty;
    }
    Better:
    Code:
    hashmap::hashmap(int capacity) :
    	capacity(capacity),
    	slots(new slot[capacity])
    {
    	for (int i = 0; i < capacity; i++)
    		slots[i].slotState = slot::empty;
    }
    Even better is to use a vector.

    You should also define a private copy-constructor and assignment-operator and leave them unimplemented, so as to prevent copying of instances of your class.

    (void) is an old C throwback. In C++ just use ()
    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"

  5. #5
    Registered User
    Join Date
    May 2010
    Posts
    5
    I think I'm gonna like it here Thank you for your advice!!

    ...but now it's giving me another memory error. This one could be difficult to locate on the two files I posted.

    Unhandled exception at 0x634a31ea (msvcr90d.dll) in lab3.exe: 0xC0000005: Access violation reading location 0xcdcdcdc1.

    It crashes right before searching the item in the hash table.

    I can show you all of my header and cpp files if you want to. I have a stock one, a date one, and a lab3driver one besides the hashmap.

    I'm going to bed now. It's late. Very late.

  6. #6
    Algorithm Dissector iMalc's Avatar
    Join Date
    Dec 2005
    Location
    New Zealand
    Posts
    6,262
    That value is an offset from the recogniseable special value of 0xcdcdcdcd. Whenever you see a value that is close to that, or close to some other odd value like 0xdddddddd or 0xfeeefeee or 0xfdfdfdfd or 0xbaadf00d or 0xBADCAB1E, then do a search on the net and you'll find hundreds of links like this
    It again indicates that something is probably uninitialised.
    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. float calculation issue
    By George2 in forum C# Programming
    Replies: 1
    Last Post: 05-26-2008, 04:56 AM
  2. Creating Linked List Using Hashing and Stack
    By m0ntana in forum C Programming
    Replies: 2
    Last Post: 04-07-2007, 07:11 AM
  3. Replies: 8
    Last Post: 09-11-2006, 11:26 AM
  4. Double Hashing
    By carrja99 in forum C++ Programming
    Replies: 1
    Last Post: 03-28-2003, 07:36 AM
  5. my first issue of GDM
    By DavidP in forum A Brief History of Cprogramming.com
    Replies: 0
    Last Post: 09-12-2002, 04:02 PM

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