I'm trying to design a my own hash table data structure using chaining, but my main issue is designing flexible components that can serve my hash table class. Before anyone asks why I'm trying to make my own hash table, this is part of an assignment for one of my classes, and I figured that a custom hash table would help in future game projects (I heard hash tables were commonly used for managing game assets).
My hash table contains a sorted linked list class that I also created for a previous assignment, but I'm trying to figure out how I would deal with a look up in the hash table. My first idea was to implement a find function in my list class, but I can't figure out how to design it so that it is flexible enough for my hash table to use (i.e. if my hash table decided to do a look up with a string rather instead of a number, and vice versa). Please feel free to critique my class design. This is all a learning process so I would love to hear from more experienced programmers.
*EDIT* Just added a "Front()" function to provide access to the first node in the list.
Here is my list class. My get function should be returning a ptr to the data object, right?:
/************************************************************************
* SortedList class template.
* Will manage and sort inherent C++ types.
* *NOTE* Overloaded operator<() must be available in custom
* class objects in order for sorting to work properly.
************************************************************************/
template <typename T, typename Node = ListNode<T>>
class SortedList
{
public:
/** Class constructor.
*/
SortedList();
/** Class destructor.
* Deallocates heap memory generated by the class in addition to
* destroying the class instance.
*/
~SortedList();
/** List manipulator.
* Inserts an item to the list in sorted order.
* @param item An item of the same type as the list.
*/
void Insert(const T &newItem);
/** Iterator
* Returns a ptr to the beginning of the list.
*/
Node* Front();
/** List manipulator.
* Empties the entire list i.e. pops off all items.
*/
void Clear();
/** Utility function.
* Returns true if the list is empty, else returns false.
*/
bool IsEmpty() const;
/** Utility function.
* Returns the number of elements in the list.
*/
int Size() const;
private:
unsigned int m_count; ///< Keeps track of how many items in the list.
Node<T> *m_pFront; ///< Points to the front of the list.
/** List manipulator.
* Takes a an item off the front of the list, and returns it.
* @throw (char*) Throws a char* exception if called against an empty list.
*/
T Pop();
};
/************************************************************************
* Method Definitions
************************************************************************/
template <typename T, typename Node>
SortedList<T, Node>::SortedList() : m_count(0), m_pFront(nullptr) {}
template <typename T, typename ListNode>
SortedList<T, Node>::~SortedList()
{
Clear();
}
template <typename T, typename Node>
void SortedList<T, Node>::Insert(const T &newItem)
{
// Make new node the front if it has the 'lowest' value, or list is empty
if (m_pFront == nullptr || newItem < *(m_pFront->Data()))
m_pFront = new Node(newItem, m_pFront);
else
{
Node *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()) < newItem )
{
pLinkingNode = pLinkingNode->Next();
}
// Insert the node in its appropriate position
Node *pNewNode = new Node(newItem, pLinkingNode->Next());
pLinkingNode->SetNext(pNewNode);
}
m_count++;
}
template <typename T, typename Node>
inline Node* SortedList<T, Node>::Front() const
{
return m_pFront;
}
template <typename T, typename Node>
void SortedList<T, Node>::Clear()
{
while (m_count != 0)
Pop();
}
template <typename T, typename Node>
inline bool SortedList<T, Node>::IsEmpty() const
{
if (m_count == 0)
return true;
else
return false;
}
template <typename T, typename Node>
inline int SortedList<T, Node>::Size() const
{
return m_count;
}
template <typename T, typename Node>
void SortedList<T, Node>::Print() const
{
if (m_count == 0)
{
std::cout << "There are no items in the list.\n";
}
else
{
Node* pCurrentNode = m_pFront;
for (unsigned int i = 0; i < m_count; i++)
{
std::cout << *(pCurrentNode->Data()) << std::endl;
pCurrentNode = pCurrentNode->Next();
}
}
}
template <typename T, typename Node>
T SortedList<T, Node>::Pop()
{
// Proceed with pop unless the list is empty
if (m_count > 0)
{
T tempItem = *(m_pFront->Data()); // Hold item to be returned
// Preserve pointer to node after the front and delete the current front
Node *pTempNode = m_pFront;
m_pFront = m_pFront->Next();
delete pTempNode;
m_count--;
return tempItem;
}
else
{
throw std::runtime_error("Error: Cannot pop an item from an empty list!");
}
}
Here is my default node structure for my list (Is it overkill to encapsulate the data members of the node?):
template <typename T>
class ListNode
{
public:
/** Class constructor.
* @param item Object to store inside the node.
* @param pNext Ptr to the following node.
*/
ListNode(const T &item, ListNode *pNext = nullptr)
: m_data(&item), m_pNext(pNext) {}
/** Class destructor
* Deallocates heap memory generated by the class in addition to
* destroying the class instance.
*/
~ListNode() {}
/** Getter function.
* Returns a ptr to the object stored in the node.
*/
T* Data() const { return &m_data; }
/** Getter function.
* Returns a ptr to the next node.
*/
ListNode* Next() const { return m_pNext; }
/** Setter function.
* Changes the next node pointed to.
* @param pNext Ptr to new node.
*/
void SetNext(ListNode *pNext) { m_pNext = pNext; }
protected:
T m_data; ///< Stores node's value.
ListNode *m_pNext; ///< Points to next node, if any.
};
Lastly, here is the current design of my hash table class. I haven't actually implemented anything here yet, since I'm still redesigning the list class:
template <typename Data, typename Key>
class ChainedHashTable
{
public:
ChainedHashTable( int size = 11 );
~ChainedHashTable();
/** Hashing func.
* Returns the hash value according to a hash key.
* @param key The seed value used to hash.
*/
int Hash( Key key ) const;
/** Insertion func.
* Use this to add items to the hash table.
* @param item Const reference to object being added to the table.
*/
void Insert( const Data &data, Key key );
/** Search func.
* Returns the index value of the object in question.
*/
Data* LookUp( Key key ) const;
private:
std::vector<SortedList> *m_pTable;
/** Collision resolution func.
* Inserts data into the hashed chain, in order.
* @param index Value of the index where the collision occurred.
*/
void Resolve( int index ) const;
};
I seemed to have forgotten some of the basics. Thanks.
[/quote]
The same goes for traits. +50 more to you!
