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:
Your program should take as input 10 non-negative integers as key values and insert them to a hash table.
The hash table has to be implemented using the hash function h(x) = x%10, where x is the input value.
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].
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
If there are no collisions, the program should report ‘NO’.
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
Sample input:
77 23 231 785 900 345 287 16 5 234
Expected Output:
(6,5,2) (7,7,2) (9,5,3)
#include <iostream>
#include <stdlib.h>
#include <string>
#include <sstream>
using namespace std;
/* Definitions as shown in the lecture */
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;
}
};
/*UPTO THIS LINE, THE CODE WIL BE PREPENDED BEFORE YOUR FUNCTIONS*/
class HashTable
{
private:
List bucket[10];
int bucketIndex;
int numElemBucket;
Position posInsert;
string collision;
bool reportCol;
bool reportCol2; //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;
reportCol2=false;
numElemBucket=0;
}
int insert(int data)
{
/*Write your code here to insert data into
hash table and report collision*/
bucketIndex = data%10;
if(bucket[bucketIndex].getCount()==0)
{
bucket[bucketIndex].makeEmptyList();
}
else
{
reportCol=true;
reportCol2=true;
}
posInsert = bucket[bucketIndex].end();
bucket[bucketIndex].insertList(data,posInsert);
numElemBucket++;
if(reportCol2==true)
{
listCollision(bucket[bucketIndex].getCount());
reportCol2=false;
}
return numElemBucket;
}
void listCollision(int pos)
{
/*Write your code here to generate a properly formatted
string to report multiple collisions*/
if(collision.empty())
{
std::ostringstream oss;
oss << "(" << numElemBucket << "," << bucketIndex << "," << pos << ")"<<" " ;
collision += oss.str();
}
else
{
std::ostringstream oss;
oss << "(" << numElemBucket << "," << bucketIndex << "," << pos << ")"<<" " ;
collision += oss.str();
}
}
void printCollision();
};
int main()
{
HashTable ht;
int i, data;
for (i=0;i<10;i++)
{
cin>>data;
ht.insert(data);
}
/*Write your code here to call insert function of HashTable ADT and if there is a collision, use listCollision to generate the list of collisions*/
/* Warning: Do NOT edit the code below - it will be appended during compilation
//Prints the concatenated collision list
ht.printCollision();
}
void HashTable::printCollision(){
if (reportCol == false)
cout <<"NO";
else
cout<<collision;
}
*/
No comments:
Post a Comment