Question

Data Structure in C++

PROGRAMMING PROJECTS Implement the class umapHash Key, which creates a hash function for miniPair ob- iects that uses only the key of the pair (first). The third template argument is a func- tion object type that takes a Key argument. Place the class in the header file "umaphash.h" 37. (a) // a hash function object type that applies KeyHashFunc // to the key in a miniPair object template <typename Key, typename T, typename KeyHashFunc> class umapHashKey public: unsigned int operator() (const miniPaircconst Key. T>& item) const: b) Use the hash class to implement the unordered map class umap, and place it in the p.h". Use the miniMap class in "d map.h" and the unordered set uset in "d uset.h" as a guide for your work. Run Program 11-4 using the un- ordered map class. Use umapHashKey to implement a hash function for iaicstring, time24> objects that uses the only the string (key).

please type the code and the output.
thanks

Answer 1

C++ program for hashing with chaining

In hashing there is a hash function that maps keys to some values. But these hashing function may lead to collision that is two or more keys are mapped to same value. Chain hashing avoids collision. The idea is to make each cell of hash table point to a linked list of records that have same hash function value.

Let’s create a hash function, such that our hash table has ‘N’ number of buckets.
To insert a node into the hash table, we need to find the hash index for the given key. And it could be calculated using the hash function.
Example: hashIndex = key % noOfBuckets

Insert: Move to the bucket corresponds to the above calculated hash index and insert the new node at the end of the list.

Delete: To delete a node from hash table, calculate the hash index for the key, move to the bucket corresponds to the calculated hash index, search the list in the current bucket to find and remove the node with the given key (if found).

Let's say hash table with 7 buckets (0, 1, 2, 3, 4, 5, 6) Keys arrive in the Order (15, 11, 27, 8) 2 3 4 5 627

Please refer Hashing | Set 2 (Separate Chaining) for details.

We use a list in C++ which is internally implemented as linked list (Faster insertion and deletion).

filter_none

edit

play_arrow

brightness_4

// CPP program to implement hashing with chaining #include<iostream> #include <list> using namespace std;    class Hash {     int BUCKET;    // No. of buckets        // Pointer to an array containing buckets     list<int> *table; public:     Hash(int V); // Constructor        // inserts a key into hash table     void insertItem(int x);        // deletes a key from hash table     void deleteItem(int key);        // hash function to map values to key     int hashFunction(int x) {         return (x % BUCKET);     }        void displayHash(); };    Hash::Hash(int b) {     this->BUCKET = b;     table = new list<int>[BUCKET]; }    void Hash::insertItem(int key) {     int index = hashFunction(key);     table[index].push_back(key); }    void Hash::deleteItem(int key) {   // get the hash index of key   int index = hashFunction(key);      // find the key in (inex)th list   list <int> :: iterator i;   for (i = table[index].begin();            i != table[index].end(); i++) {     if (*i == key)       break;   }      // if key is found in hash table, remove it   if (i != table[index].end())     table[index].erase(i); }    // function to display hash table void Hash::displayHash() {   for (int i = 0; i < BUCKET; i++) {     cout << i;     for (auto x : table[i])       cout << " --> " << x;     cout << endl;   } }    // Driver program int main() {   // array that contains keys to be mapped   int a[] = {15, 11, 27, 8, 12};   int n = sizeof(a)/sizeof(a[0]);      // insert the keys into the hash table   Hash h(7);   // 7 is count of buckets in                // hash table   for (int i = 0; i < n; i++)     h.insertItem(a[i]);        // delete 12 from hash table   h.deleteItem(12);      // display the Hash table   h.displayHash();      return 0; }