- 2 Operations On Hash Tables 20 In This Problem You Will Implement A Data Structure For Hashing With Linear Probing 1 (115.33 KiB) Viewed 36 times
#ifndef HASHTABLE_H
#define HASHTABLE_H
class HashTable
{
public:
HashTable(int max);
virtual ~HashTable();
protected:
private:
int *list;
int maxSize;
};
#endif // HASHTABLE_H
#include "HashTable.h"
HashTable::HashTable(int max)
{
//ctor
}
HashTable::~HashTable()
{
//dtor
}
#include <iostream>
using namespace std;
int main()
{
cout << "Assignment - Q2" << endl;
HashTable h1(20);
h1.Insert(13);
h1.Insert(17);
h1.Insert(57);
h1.Insert(77);
h1.Delete(57);
h1.Print();
cout << h1.Find(77) << endl;
return 0;
}
2. Operations on Hash Tables [20] In this problem, you will implement a data structure for hashing with linear probing. Assume that we have functions for insertions, deletions, and finds. Define four functions as per description. Assume the keys are non-negative integers, which are hashed into a table of size maxSize. An empty table entry can be indicated using -2. Use -1 in a location to indicate that the entry formerly in the location has been deleted. Use hash function key%20. a. Find(x) which returns the index of where x is stored if it is in the hash table and -1 otherwise. b. Insert(x) which inserts x into the hash table with the precondition that x is not currently in the table. Naturally, a location with a -1 in it can be used to place a newly inserted item. Your algorithm should indicate when the hash table is full and x cannot be inserted. c. Delete(x) which removes x from the hash table using lazy deletion. d. Print() which prints all the valid items in the hash table. e. Rehash() which returns a new table of the same size maxSize which contains all the items of the old table, but has no items marked as deleted. [Hint. Create a new object of HashTable, insert all the valid items from the current HashTable to the newly created one]. CodeBlocks Details Project Name: AsnHashDemo Files: HashTable.h HashTable.cpp main.cpp