2 Replies - 2396 Views - Last Post: 17 November 2012 - 12:07 PM Rate Topic: -----

#1 IssHauti  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 1
  • Joined: 13-November 12

c++ Hash Table collision and count

Posted 17 November 2012 - 10:18 AM

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
#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
#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
#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

Nodes in table:
Key: 153
FullName: Ted Baker

Nodes in table:
Key: 1
FullName: Lisa Smith

Nodes in table:
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!

Is This A Good Question/Topic? 0
  • +

Replies To: c++ Hash Table collision and count

#2 #define  Icon User is offline

  • Duke of Err
  • member icon

Reputation: 1325
  • View blog
  • Posts: 4,551
  • Joined: 19-February 09

Re: c++ Hash Table collision and count

Posted 17 November 2012 - 12:04 PM

View PostIssHauti, on 17 November 2012 - 08:18 PM, said:

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:


Although you have not supplied table.cpp, it looks like the size member variable is to be used for the count of elements. When elements are added the size is changed etc.

You have two options, I think, for adding at the end of the table. You can write a function to append to the table, or a less efficient option : create a new and larger table and copy the data over (edit : probably not a great idea).

Edit: looking again another option could be just to add new NODE's as in a tree or create a new table.

This post has been edited by #define: 17 November 2012 - 12:27 PM

Was This Post Helpful? 1
  • +
  • -

#3 ishkabible  Icon User is offline

  • spelling expret
  • member icon




Reputation: 1622
  • View blog
  • Posts: 5,709
  • Joined: 03-August 09

Re: c++ Hash Table collision and count

Posted 17 November 2012 - 12:07 PM

Quote

counting number of elements from table

generally an integer denoting the number of elements is kept track of to determine the load and when to rehash; that's also generally used to keep track of the number of elements in the table.

Quote

in case of collision, adding node at the end of the table

liner chaining is used frequently. there are other methods but this is by far the simplest and still does a good job.
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1