Jump to content

  • Log In with Google      Sign In   
  • Create Account

[C++] Problems designing a proper hash table w/ chaining


Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.

  • You cannot reply to this topic
25 replies to this topic

#21 Robot Ninja   Members   -  Reputation: 569

Like
0Likes
Like

Posted 21 December 2012 - 03:27 PM

You don't need any dynamic allocation (beyond what's required for creating a ListNode for the SortedList). Could you explain why you think you need to do any more than that?

This is what my table's insert code looks like right now:
template <typename Key, typename Data, typename HashFunc>
void ChainedHashTable<Key, Data, HashFunc>::Insert( const HashContainer<Key, Data> &container )
{
	/* ...Table resize code can go here... */

	// Hash an appropriate index.
	std::size_t index = Normalize( hash(container.GetKey()) );

	// Insert the key and data into the hash table.
	// SortedList object will deal with sorting and inserting into the chain.
	m_pTable[index].Insert(container);
}

This is my list's Insert code:
template <typename T>
void SortedList<T>::Insert( const T &item )
{
	// Make new node the front if it has the 'lowest' value, or list is empty
	if (m_pFront == nullptr || item < m_pFront->Data())
		m_pFront = new ListNode(item, m_pFront);
	else
	{
		ListNode *pLinkingNode = m_pFront; // newNode will be pointed to by this.
		// Keep iterating until we find the 'in-order' pos, until we hit the end.
		while (pLinkingNode->Next() != nullptr && 
			pLinkingNode->Next()->Data() < item )
		{
			pLinkingNode = pLinkingNode->Next();
		}

		// Insert the node in its appropriate position
		ListNode *pNewNode = new ListNode(item, pLinkingNode->Next());
		pLinkingNode->SetNext(pNewNode);
	}

	m_count++;
}

My list only takes one parameter, so what I feed it has to be contained in one object. ...[moment of realization]...Wait, so would something like this work:
template <typename Key, typename Data, typename HashFunc>
void ChainedHashTable<Key, Data, HashFunc>::Insert( const Key &key, const Data &data )
{
	/* ...Table resize code can go here... */

	// Hash an appropriate index.
	std::size_t index = Normalize( hash(key) );

	// Insert the key and data into the hash table.
	// SortedList object will deal with sorting and inserting into the chain.
	m_pTable[index].Insert(HashContainer(key, data));
}


Sponsor:

#22 e‍dd   Members   -  Reputation: 2105

Like
1Likes
Like

Posted 21 December 2012 - 04:44 PM

Wait, so would something like this work:

template <typename Key, typename Data, typename HashFunc>
void ChainedHashTable<Key, Data, HashFunc>::Insert( const Key &key, const Data &data )
{
	/* ...Table resize code can go here... */

	// Hash an appropriate index.
	std::size_t index = Normalize( hash(key) );

	// Insert the key and data into the hash table.
	// SortedList object will deal with sorting and inserting into the chain.
	m_pTable[index].Insert(HashContainer(key, data));
}

Yes :)



#23 Robot Ninja   Members   -  Reputation: 569

Like
0Likes
Like

Posted 21 December 2012 - 08:18 PM

Thank you edd for helping me out so much. I feel like I should buy you a small gift for the holidays. lol

I think the design for my hash table is almost complete - I just have to clean up compiler errors here and there. I've been learning from some template programming mistakes as I go through my code. There is one error that I'm encountering right now that has be a little bewildered:

error C2678: binary '<' : no operator found which takes a left-hand operand of type 'const HashContainer<Key,Data>' (or there is no acceptable conversion)

It's pointing to one of the beginning lines of my list's Insert code:
if (m_pFront == nullptr || item < m_pFront->GetData())

However, I'm pretty sure I have the appropriate operator< overload inside my HashContainer class. Do you or anyone else have any idea what it could be?

*EDIT* I figured out what the problem was. My GetKey function was returning a const reference to the key, but I did not append the const keyword at the end of the function declaration. However, the last compiler error I have now is this hot mess:

error LNK2019: unresolved external symbol "public: __thiscall HashContainer<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>::~HashContainer<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>(void)" (??1?$HashContainer@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@H@@QAE@XZ) referenced in function "public: void __thiscall ChainedHashTable<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int,struct Hash<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > > >::Insert(class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> > const &,int const &)" (?Insert@?$ChainedHashTable@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@HU?$Hash@V?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@@@@@QAEXABV?$basic_string@DU?$char_traits@D@std@@V?$allocator@D@2@@std@@ABH@Z)
1>MSVCRTD.lib(crtexe.obj) : error LNK2019: unresolved external symbol _main referenced in function ___tmainCRTStartup
1>C:\Users\Nova\Dropbox\ThachDev\~C++\Data_Structures\Debug\BORG_Language.exe : fatal error LNK1120: 2 unresolved externals

Edited by Robot Ninja, 21 December 2012 - 09:29 PM.


#24 e‍dd   Members   -  Reputation: 2105

Like
1Likes
Like

Posted 21 December 2012 - 10:35 PM

error LNK2019: unresolved external symbol "public: __thiscall HashContainer<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>::~HashContainer<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>(void)"

The trick with error messages like this is to resist intimidation and the urge to give up. If we replace "std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >" with "std::string", this message should become a bit clearer:

 

error LNK2019: unresolved external symbol "public: __thiscall HashContainer<std::string,int>::~HashContainer<std::string,int>(void)"

 

In other words, the linker can't find a definition for your HashContainer's destructor. Have you provided one?



#25 Robot Ninja   Members   -  Reputation: 569

Like
0Likes
Like

Posted 21 December 2012 - 11:10 PM


error LNK2019: unresolved external symbol "public: __thiscall HashContainer<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>::~HashContainer<class std::basic_string<char,struct std::char_traits<char>,class std::allocator<char> >,int>(void)"

The trick with error messages like this is to resist intimidation and the urge to give up. If we replace "std::basic_string<char, struct std::char_traits<char>, class std::allocator<char> >" with "std::string", this message should become a bit clearer:
 
 

error LNK2019: unresolved external symbol "public: __thiscall HashContainer<std::string,int>::~HashContainer<std::string,int>(void)"

 
 
In other words, the linker can't find a definition for your HashContainer's destructor. Have you provided one?
 


Ah I see, that makes sense. Okay, so I replaced the semicolon at the end of my destructor's declaration and replaced it empty brackets. I also realized that I named my entry point "Main" instead of just "main", which explains the "tmainCRTStartup" error. Thanks so much for your help. My program compiles successfully. Now I just have to test my code logic. Seriously, I need to buy you a beer or something.

#26 Khatharr   Crossbones+   -  Reputation: 2996

Like
0Likes
Like

Posted 22 December 2012 - 04:48 AM

That's definitely the best mangle I've seen in quite some time. biggrin.png


void hurrrrrrrr() {__asm sub [ebp+4],5;}

There are ten kinds of people in this world: those who understand binary and those who don't.




Old topic!
Guest, the last post of this topic is over 60 days old and at this point you may not reply in this topic. If you wish to continue this conversation start a new topic.



PARTNERS