//Dictionary.h
#pragma once
#include
#include
using namespace std;
template
class Dictionary {
private:
void operator =(const Dictionary&) {}
Dictionary(const Dictionary&) {}
public:
Dictionary() {}
virtual ~Dictionary() {}
//virtual void clear() = 0;
virtual void insert(const Key& k, const E& e) = 0; //
//virtual E remove(const Key& k) = 0;
//virtual E removeAny() = 0;
virtual E find(const Key& k)const = 0; //
virtual int size() = 0; //
};
template
class KVpair {
private:
Key k;
E e;
public:
KVpair() {}
KVpair(Key kval,E eval)
{
k = kval; e = eval;
}
KVpair(const KVpair&o)
{
k = o.k; e = o.e;
}
void operator=(const KVpair&o)
{
k = o.k; e = o.e;
}
Key key() { return k; }
void setKey(Key ink) { k = ink; }
E value() { return e; }
};
template
class hashdict :public Dictionary {
private:
KVpair*HT;
int M;
int currcnt;
Key EMPTYKEY;
int p(Key K,int i)const
{return i;} //linear probing
int h(int x)const { return x%M; }
int h(char*x)const {
int i, sum;
for {sum = 0, i = 0; x[i] != '\0'; i++ }sum += (int)x[i];
return sum%M;
}
void hashInsert(const Key&k, const E&e) {
int home;
int pos = home = h(k);
for (int i = 1; EMPTYKEY != (HT[pos]).key(); i++) {
Assert(k != (HT[pos]).key(), "Duplicates not allowed");
pos = (home + p(k, i)) % M;
}
KVpair<Key, E>temp(k, e);
HT[pos] = temp;
}
E hashSearch(const Key&k)const {
int home;
int pos = home = h(k);
for (int i = 1; (k != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key()); i++)
pos = (home + p(k, i)) % M;
if (k == (HT[pos]).key())
return (HT[pos]).value();
else return NULL;
}
public:
hashdict(int sz, Key k) {
M = sz;
EMPTYKEY = k; //"k"defines an empty slot
currcnt = 0;
HT = new KVpair[sz];
for (int i = 0; i < M; i++)
(HT[i]).setKey(EMPTYKEY); //setKey
}
~hashdict() { delete HT; }
E find (const Key&k)const
{
return hashSearch(k);
}
int size() { return currcnt; }
void insert(const Key&k, const E&it) {
Assert(currcnt < M, "Hash table is full");
hashInsert(k, it);
currcnt++;
}
};
void Assert(bool val, string s) {
if (!val) {
cout << "Assertion Failed: " << s << endl;
exit(-1);
}
}
//hashList.cpp
#include "stdafx.h"
#include "Dictionary.h"
#include
using namespace std;
int main()
{
hashdicthashlist(5, 0);
hashlist.insert(1, 1);
hashlist.insert(2, 1);
hashlist.insert(3, 1);
hashlist.insert(4, 1);
hashlist.insert(55, 2);
int i = hashlist.size();
return 0;
}