C++ Hashtable for Strings
I'm trying to use a hash table in C++ to store strings i.e a string key and data. I'm using code from the 2003 book Data structures for games programmers.
While I can implement an int hash table, I'm stuck at what's wrong when I try and do the same with a string one.
C++ keeps giving me the same error.
//code
#include <string>
#include <iostream>
#include "HashTable.h"
using namespace std;
//hash table
//***********************************************************************
unsigned long int Hash(int i) {
return i;
}
unsigned long int StringHash(const char* p_string) {
unsigned long int hash = 0;
int i;
int length = strlen(p_string);
for(i = 0; i < length; i++) {
hash += ((i + 1) * p_string[i]);
}
return hash;
}
HashTable<string, string> table(10, StringHash); <<--problem here ERROR BELOW
HashEntry<string, string>* entry;
//***********************************************************************
Error 6 error C2664: 'HashTable<KeyType,DataType>::HashTable(int,unsigned long (__cdecl *)(KeyType))' : cannot convert parameter 2 from 'unsigned long (__cdecl *)(const char *)' to 'unsigned long (__cdecl *)(KeyType)' j:\my_docs\college 2010 -2011\data structures for games\ca3_datastructures_gerry mc donnell\ca3_datastructures_gerry mc donnell\loginuser.h 31 CA3_DataStructures_gerry mc donnell
If anyone can help it would be great.
The stringhash
function was given by the book so I'm not sure what I'm doing wrong.
Hashtable.h
// ============================================================================
// Data Structures For Game Programmers
// Ron Penton
// HashTable.h
// This file holds the Linekd Hash Table implementation.
// ============================================================================
#ifndef HASHTABLE_H
#define HASHTABLE_H
#include "DLinkedList.h"
#include "Array.h"
// -------------------------------------------------------
// Name: HashEntry
// Description: This is the hash table entry class. It
// stores a key and data pair.
// -------------------------------------------------------
template< class KeyType, class DataType >
clas开发者_如何学Pythons HashEntry {
public:
KeyType m_key;
DataType m_data;
};
// -------------------------------------------------------
// Name: HashTable
// Description: This is the hashtable class.
// -------------------------------------------------------
template< class KeyType, class DataType >
class HashTable {
public:
// typedef the entry class to make is easier to work with.
typedef HashEntry<KeyType, DataType> Entry;
// ----------------------------------------------------------------
// Name: HashTable
// Description: construct the table with a size, and a hash
// function. The constructor will construct the
// m_table array with the correct size.
// Arguments: p_size: The size of the table
// p_hash: the hashing function.
// Return Value: None
// ----------------------------------------------------------------
HashTable(int p_size, unsigned long int (*p_hash)(KeyType))
: m_table(p_size) {
// set the size, hash function, and count.
m_size = p_size;
m_hash = p_hash;
m_count = 0;
}
// ----------------------------------------------------------------
// Name: Insert
// Description: Inserts a new key/data pair into the table.
// Arguments: p_key: the key
// p_data: the data attached to the key.
// Return Value: None
// ----------------------------------------------------------------
void Insert(KeyType p_key, DataType p_data) {
// create an entry structure.
Entry entry;
entry.m_data = p_data;
entry.m_key = p_key;
// get the hash value from the key, and modulo it
// so that it fits within the table.
int index = m_hash(p_key) % m_size;
// add the entry to the correct index, increment the count.
m_table[index].Append(entry);
m_count++;
}
// ----------------------------------------------------------------
// Name: Find
// Description: Finds a key in the table
// Arguments: p_key: the key to search for
// Return Value: a pointer to the entry that has the key/data,
// or 0 if not found.
// ----------------------------------------------------------------
Entry* Find(KeyType p_key) {
// find out which index the key should exist in
int index = m_hash(p_key) % m_size;
// get an iterator for the list in that index.
DListIterator<Entry> itr = m_table[index].GetIterator();
// search each item
while (itr.Valid()) {
// if the keys match, then return a pointer to the entry
if (itr.Item().m_key == p_key)
return &(itr.Item());
itr.Forth();
}
// no match was found, return 0.
return 0;
}
// ----------------------------------------------------------------
// Name: Remove
// Description: Removes an entry based on key
// Arguments: p_key: the key
// Return Value: true if removed, false if not found.
// ----------------------------------------------------------------
bool Remove(KeyType p_key) {
// find the index that the key should be in.
int index = m_hash(p_key) % m_size;
// get an iterator for the list in that index.
DListIterator<Entry> itr = m_table[index].GetIterator();
// search each item
while (itr.Valid()) {
// if the keys match, then remove the node, and return true.
if (itr.Item().m_key == p_key) {
m_table[index].Remove(itr);
m_count--;
return true;
}
itr.Forth();
}
// item wasn't found, return false.
return false;
}
// ----------------------------------------------------------------
// Name: Count
// Description: Gets the number of entries in the table.
// Arguments: None
// Return Value: Number of entries in the table.
// ----------------------------------------------------------------
int Count() {
return m_count;
}
// ----------------------------------------------------------------
// Name: m_size
// Description: This is the size of the table
// ----------------------------------------------------------------
int m_size;
// ----------------------------------------------------------------
// Name: m_count
// Description: This is the number of entries in the table.
// ----------------------------------------------------------------
int m_count;
// ----------------------------------------------------------------
// Name: m_table
// Description: This is the actual table, a list of linked
// lists of entries.
// ----------------------------------------------------------------
Array< DLinkedList< Entry > > m_table;
// ----------------------------------------------------------------
// Name: m_hash
// Description: a pointer to the hash function.
// ----------------------------------------------------------------
unsigned long int (*m_hash)(KeyType);
};
#endif
//array.h
Your Hashtable
constructor requires the hash function to take a KeyType
parameter.
You're creating a Hashtable
with std::string
as KeyType
, but passing a hash function that takes a char*
parameter. Those are not compatible.
Either make a hash with a char*
key type, or change your hash function to use an std::string
.
In HashTable.h
, the hash function has function signature unsigned long int (*p_hash)(KeyType)
. That is, if your hashtable is a HashTable<string, string>
, the expected form of the hash function is unsigned long int (*p_hash)(string)
, not unsigned long int (*p_hash)(const char*)
as posted.
HashTable<string, string> table( 10, StringHash );
string
(2nd template parameter) is your KeyType but your hash function expects a const char *
Either
unsigned long int StringHash( const string & p_string )
or
HashTable<string, const char *> table( 10, StringHash );
should work. (haven't compiled or tested)
精彩评论