Implementing a Hash Table ADT

A hash table is a data structure that maps a set of keys to a given set of values. It uses a hash function to compute an index into an array of buckets or slots, from which the correct value can be found or to which a correct value can be inserted. A hash function will assign each key to a unique bucket or slot. In practice, however, there may be more than one key that will hash to the same bucket. Such an assignment is said to result in a collision.

In this assignment, you have to implement a Hash Table ADT using arrays and linked lists. The algorithm should accommodate the features described below:

1. Your program should take as input 10 non-negative integers as key values and insert them to a hash table.
2. The hash table has to be implemented using the hash function h(x) = x%10, where x is the input value.
3. Input values that return the same value for h(x) have to be properly accommodated such that if there is a collision, the index from the array to the appropriate bucket should point to a linked list that can take in all the values that hash to the same bucket. i.e., you can have an array of linked lists such that each entry of the array is a pointer to a bucket. For e.g., when h(x) returns 4, the input value should go into the linked list starting from A[4].
4. Your program should report when there is a collision and must specify the position (starting at 1 for the 1st element) in the input list of that key value where the collision occurred. It should also report the bucket number and the number of entries in each bucket
5. If there are no collisions, the program should report ‘NO’.
6. HashTable class has a printCollision function which you cannot re-write. The string you want to print has to be made available in the private data variable “collision” using listCollision function in class HashTable.

INPUT:

A list of 10 non-negative integers with a single space between the entries.

OUTPUT:

3-tuple indicating the position in the input list where the collision occurred, the corresponding bucket number and the number of elements in that bucket, each 3-tuple has to be separated by a single space.

CONSTRAINTS:

0 <= key <1000

#include <iostream>
#include <stdlib.h>
#include <string>
#include <sstream>
using namespace std;
typedef struct CellType* Position;
typedef int ElementType;
struct CellType{
    ElementType value;
    Position next;
};
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,x;
        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);
                bucket[i].makeEmptyList();
			}
			collision = "";
            x=0;
            reportCol = false;
        }
        void insert(int data)
		{
			bucketIndex = (data%10);
			posInsert = bucket[bucketIndex].end();
			bucket[bucketIndex].insertList(data,posInsert);
			listCollision(++x);
        }
        void listCollision(int pos)
		{       
			numElemBucket = bucket[bucketIndex].getCount();
			if(numElemBucket>1)
			{
			 collision = collision + '(';
			 if(pos+48==58)
			  {
			   collision += 49;
			   collision += 48;
			  }
			 else
			 {  
			  collision += pos+48;
			 }
			 collision += ',';
			 collision += bucketIndex+48;
			 collision += ',';
			 if(numElemBucket+48==58)
			  {
			   collision += 49;
			   collision += 48;
			  }
			 else
			 {  
			  collision += numElemBucket+48;
			 }
			 collision += ')';
			 collision += ' ';
		     reportCol = true;
			}
		}
           void printCollision();
};
void HashTable::printCollision()
{
    if (reportCol == false)
        cout <<"NO";
    else
        cout<<collision;
}

int main()
{    
    HashTable ht;
    int i, data;   
	for (i=0;i<10;i++)
	{
        cin>>data;
        ht.insert(data);
        }
//Prints the concatenated collision list
   ht.printCollision(); 
}