Hello,
I'm having some trouble with implementing a hashtable (hashmap) for a
class at school.
The map's constructor is called with a hash function and the number of
possible keys the function returns. The get and set methods do work
well, only the []-operator does not work. When trying to do something
like map['D'] = "December", it seems like the = has no effect. At
least, if the value for the same key is read after assigning it, it
will be null.
I guess I got some pointer wrong or similar but I just cannot find the
mistake. I'd appreciate any help you can give.
So here's the code for the hashmap:
// ---
template<class KeyType, class DataType> class myhash {
public:
typedef unsigned int (*hashFunctionT ype)(const KeyType &);
typedef pair<KeyType, DataType> pairType;
typedef typename list<pairType>: :iterator listIterator;
private:
list<pairType> **data;
hashFunctionTyp e hashFunction;
inline pairType *findEntry(cons t unsigned int k, const KeyType &key)
const
{
for(listIterato r z = data[k]->begin(); z != data[k]->end(); z++)
if(z->first == key)
return &(*z);
return NULL;
}
public:
void set(const KeyType &key, const DataType &value)
{
unsigned int k = hashFunction(ke y);
if(data[k] == NULL)
{
data[k] = new list<pairType>( );
data[k]->push_back(*n ew pairType(key, value));
}
else
{
pairType *p = findEntry(k, key);
if(p == NULL) data[k]->push_back(*n ew pairType(key, value));
else p->second = value;
}
}
void get(const KeyType &key, DataType &value)
{
unsigned int k = hashFunction(ke y);
if(data[k] == NULL) throw new notfound_error( );
pairType *p = findEntry(k, key);
if(p == NULL) throw new notfound_error( );
value = p->second;
}
DataType &operator[] (const KeyType &key)
{
unsigned int k = hashFunction(ke y);
pairType *p;
if(data[k] == NULL) data[k] = new list<pairType>( ); // create new
list
else
{
p = findEntry(k, key);
if(p != NULL) return p->second;
nCollisions++;
}
DataType *d = new DataType(); // create new data type in case write
access is coming next to that element
p = new pairType(key, *d); // create key-value pair
data[k]->push_back(*p );
return *d; // return reference to data element
}
};
// ---
I left out the definition of the constructor and destructor as they
don't do interesting things.
Now in this test program the myhash template gets specialised with a
char as KeyType and a wrapper class around a const char * as DataType:
// ---
unsigned int hashfunc(const char &c) {
unsigned int i = c - 'A';
return (i*i)%100;
}
class constcharpointe r {
const char *_ptr;
public:
constcharpointe r(const char *ptr) { _ptr = ptr; }
constcharpointe r() { _ptr = 0; }
operator const char* () { return _ptr; }
};
int main() {
using namespace std;
myhash<char,con stcharpointer> h(hashfunc,100) ;
h['D'] = "Dezember";
cerr << "h['D']: " << h['D'] << endl; // this one triggers a
segmentation fault (null pointer returned)
cerr << "strcmp: " << strcmp(h['D'], "Dezember") << endl;
return 0;
}
// ---
The constcharpointe r class was written by the author of the programming
task and thus I guess should be working fine.
Regards,
Denis
