Hash table implementation in C++

Question

I am trying the following code for Hash table implementation in C++. The program compiles and accepts input and then a popup appears saying " the project has stopped working and windows is checking for a solution to the problem. I feel the program is going in the infinite loop somewhere. Can anyone spot the mistake?? Please help!

    #include <iostream>
    #include <stdlib.h>
    #include <string>
    #include <sstream>

    using namespace std;

    /* Definitions as shown */
    typedef struct CellType* Position;
    typedef int ElementType;

    struct CellType{
    ElementType value;
    Position next;
    };

    /* *** Implements a List ADT with necessary functions.
    You may make use of these functions (need not use all) to implement your HashTable ADT    */          

    class List{

    private:
        Position listHead;
        int count;

    public:
        //Initializes the number of nodes in the list
        void setCount(int num){
            count = num;
        }

        //Creates an empty list
        void makeEmptyList(){
            listHead = new CellType;
            listHead->next = NULL;
        }        

        //Inserts an element after Position p
        int insertList(ElementType data, Position p){
            Position temp;
            temp = p->next;
            p->next = new CellType;
            p->next->next = temp;
            p->next->value = data;    
            return ++count;            
        }        

        //Returns pointer to the last node
        Position end(){
            Position p;
            p = listHead;
            while (p->next != NULL){
                p = p->next;
            }
            return p;            
        }

        //Returns number of elements in the list
        int getCount(){
            return count;
        }
};
class HashTable{
    private:
        List bucket[10];
        int bucketIndex;
        int numElemBucket;
        Position posInsert;
        string collision;
        bool reportCol; //Helps to print a NO for no collisions

        public:    
        HashTable(){ //constructor
            int i;
            for (i=0;i<10;i++){
                bucket[i].setCount(0);
            }
            collision = "";
            reportCol = false;
        }


            int insert(int data){
                           bucketIndex=data%10;
                            int col;

                           if(posInsert->next==NULL) 

              bucket[bucketIndex].insertList(data,posInsert);

                      else { while(posInsert->next != NULL){
                                posInsert=posInsert->next;

                               }
                           bucket[bucketIndex].insertList(data,posInsert);
                                reportCol=true;}
                                if (reportCol==true) col=1;
                                else col=0;
                                numElemBucket++;       

                                       return col ;        
            /*code to insert data into 
              hash table and report collision*/
         }

         void listCollision(int pos){
            cout<< "("<< pos<< "," << bucketIndex << "," << numElemBucket << ")"; /*codeto      generate a properly formatted 
               string to report multiple collisions*/ 
        }

        void printCollision();

     };

     int main(){

     HashTable ht;
     int i, data;


     for (i=0;i<10;i++){
        cin>>data;
       int abc= ht.insert(data);
       if(abc==1){
       ht.listCollision(i);/* code  to call insert function of HashTable ADT and if there is  a collision, use listCollision to generate the list of collisions*/
      }


   //Prints the concatenated collision list
     ht.printCollision(); 

     }}

     void HashTable::printCollision(){
      if (reportCol == false)
          cout <<"NO";
      else
          cout<<collision;
      }

The output of the program is the point where there is a collision in the hash table, thecorresponding bucket number and the number of elements in that bucket.

Solution

After trying dubbuging, I come to know that, while calling a constructor you are not emptying the bucket[bucketIndex].

So your Hash Table constructor should be as follow:

HashTable(){ //constructor
            int i;
            for (i=0;i<10;i++){
                bucket[i].setCount(0);
                 bucket[i].makeEmptyList();  //here we clear for first use
            }
            collision = "";
            reportCol = false;

        }

//Creates an empty list
void makeEmptyList(){
        listHead = new CellType;
        listHead->next = NULL;
    } 

Comments

[Red Alert]

maybe you should do some debugging and see which loop it gets stuck in? It sounds like you are using visual studio, which means you can just step through your code until it gets stuck...

[tadman]

You've got 10 sprinkled throughout your code here. Shouldn't that be, at the very least, a constant? Also it's generally a good idea to use a prime number as your bucket size.