C++ Hash Table collision and count issue
Nov 17, 2012 at 5:36pm UTC
Hi there guys. I don't know what should I do for:
-counting number of elements from table
-in case of collision, adding node at the end of the table
I have here the source codes:
table.h
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
#include <cstring>
using namespace std;
#define KeySize 16
#define ValueSize 64
#define DefaultTableSize 20
struct NODE
{
NODE(const char * Key1 = "\0" , const char * Name = "\0" )
{
strcpy(Key, Key1);
strcpy(FullName, Name);
next = NULL;
}
char Key[KeySize];
char FullName[ValueSize];
NODE *next;
};
class Hashtable
{
private :
int table_size;
NODE** table;
int size;
long hashString(char * Key);
NODE* find(char * Key);
NODE* current_entry;
int current_index;
public :
Hashtable(int T = DefaultTableSize);//constructor
virtual ~Hashtable();//destructor
bool put(NODE *);
bool get(NODE *);
bool contains(char * Key);
void removeAll();
void initIterator();
bool hasNext();
void getNextKey(char * Key);
friend void disp(NODE *);
};
HashFunction.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44
#include <cstring>
using namespace std;
#define KeySize 16
#define ValueSize 64
#define DefaultTableSize 20
struct NODE
{
NODE(const char * Key1 = "\0" , const char * Name = "\0" )
{
strcpy(Key, Key1);
strcpy(FullName, Name);
next = NULL;
}
char Key[KeySize];
char FullName[ValueSize];
NODE *next;
};
class Hashtable
{
private :
int table_size;
NODE** table;
int size;
long hashString(char * Key);
NODE* find(char * Key);
NODE* current_entry;
int current_index;
public :
Hashtable(int T = DefaultTableSize);//constructor
virtual ~Hashtable();//destructor
bool put(NODE *);
bool get(NODE *);
bool contains(char * Key);
void removeAll();
void initIterator();
bool hasNext();
void getNextKey(char * Key);
friend void disp(NODE *);
};
main.cpp
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74
#include <iostream>
#include "table.h"
using namespace std;
void dispAll(Hashtable* hashtable);
int main()
{
char temp1[KeySize];
Hashtable* hashtable = new Hashtable();
NODE N1("152" ,"John Smith" );
if (!hashtable->contains(N1.Key))
{
cout << "\nAdding node: " ;
disp(&N1);
hashtable->put(&N1);
}
strcpy_s(N1.Key, "1" );
strcpy_s(N1.FullName, "Lisa Smith" );
if (!hashtable->contains(N1.Key))
{
cout << "\nAdding node: " ;
disp(&N1);
hashtable->put(&N1);
}
strcpy_s(N1.Key, "254" );
strcpy_s(N1.FullName, "Sam Doe" );
if (!hashtable->contains(N1.Key))
{
cout << "\nAdding node: " ;
disp(&N1);
hashtable->put(&N1);
}
strcpy_s(N1.Key, "152" );
strcpy_s(N1.FullName, "Sandra Dee" );
if (!hashtable->contains(N1.Key))
{
cout << "\nAdding node: " ;
disp(&N1);
hashtable->put(&N1);
}
strcpy_s(N1.Key, "153" );
strcpy_s(N1.FullName, "Ted Baker" );
if (!hashtable->contains(N1.Key))
{
cout << "\nAdding node: " ;
disp(&N1);
hashtable->put(&N1);
}
dispAll(hashtable);
}
void dispAll(Hashtable *hashtable)
{
NODE N1;
cout << "\n\nNodes in table:" << endl;
hashtable->initIterator();
while (hashtable->hasNext())
{
hashtable->getNextKey(N1.Key);
hashtable->get(&N1);
disp(&N1);
}
}
Output
Adding node:
Key: 152
FullName: John Smith
Adding node:
Key: 1
FullName: Lisa Smith
Adding node:
Key: 254
FullName: Sam Doe
Adding node:
Key: 153
FullName: Ted Baker
Nodes in table:
Key: 152
FullName: John Smith
Key: 153
FullName: Ted Baker
Key: 1
FullName: Lisa Smith
Key: 254
FullName: Sam Doe
So, there is a collision between John Smith and Sandra Dee! I need to add her at the end of the table and count all nodes! Any ideas?
Thank you very much!
Topic archived. No new replies allowed.