Homework Help is Here – Start Your Trial Now!
Engineering
Computer Engineering
C++ PROGRAMMING Topic: HashTable - PolyHash Quadratic Explain the c++ code below.: SEE ATTACHED PHOTO FOR THE PROBLEM INSTRUCTIONS  It doesn't have to be long, as long as you explain what the important parts of the code do. (The code is already implemented and correct, only the explanation needed). You can also explain line by line for an upvote, thanks.

C++ PROGRAMMING Topic: HashTable - PolyHash Quadratic Explain the c++ code below.: SEE ATTACHED PHOTO FOR THE PROBLEM INSTRUCTIONS  It doesn't have to be long, as long as you explain what the important parts of the code do. (The code is already implemented and correct, only the explanation needed). You can also explain line by line for an upvote, thanks.

Computer Networking: A Top-Down Approach (7th Edition)
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
See similar textbooks
icon
Related questions
Question

C++ PROGRAMMING
Topic: HashTable - PolyHash Quadratic

Explain the c++ code below.: SEE ATTACHED PHOTO FOR THE PROBLEM INSTRUCTIONS 

It doesn't have to be long, as long as you explain what the important parts of the code do. (The code is already implemented and correct, only the explanation needed). You can also explain line by line for an upvote, thanks.
 
EXPLAIN THE CODE BELOW: 
 
#include <cstdlib>
#include <math.h>
#include <cstring>
#include <iostream>
using namespace std;
 
class HashTable {
  string* table;
  int N;
  int count;
  
    // TODO: Polynomial Hash Code using a=7
   int hash_code(string key) {
    int code;
    int hash = 0;
    for (int i = 0; i < key.size(); i++) {
      char ch = key[i];
      code += ((ch - 96) * pow(7, key.size() - (i + 1)));
    }
    return code;
  }
 
  
  // TODO: This hash table uses a MAD compression function
  // where a = 11, b = 461, p = 919
  int compress(int code) {
    return (((11*code)+461) % 919) % N;
  }
  
   // Using the knowledge that a hash function is composed of two portions
  int hashfn(string key) {
    return compress(hash_code(key));
  }
  
  public:
   HashTable(int N) {
        this->N=N;
        table=(string*)malloc(sizeof (string) * N);
        for(int j=0; j<N; j++){
          table[j] = "a";
        }
        count = 0;
    }
 
    // TODO Implement insert
      int insert(string key) {
      int hval = hashfn(key);
      int coll  = 0;
      if(count != N){
        for(int j=0; j < N; j++){
          int i = (hval + j*j) % N;
          if(table[i].compare(key) == 0){
            return -1;
          }
          if (table[i] == "a"){
            table[i] = key;
            count++;
            break;
          }
          coll++;
        }
      }
      return coll;
  }
    
    
    // TODO Implement search
    // Tip: str1.compare(str2) will return 0 if both strings are the same
    int search(string key) {
      int cells=0,i;
       for(int j=0;j<N;j++){
        i = (hashfn(key) +(j*j)) % N;
        if(table[i].compare(key)==0){
          return cells;
        }
        cells++;
      } 
      return -1;
    }
    
    
    // TODO Implement remove
    int remove(string key) {
      int cells=0,i;
       for(int j=0;j<N;j++){
        i=(hashfn(key) +(j*j)) % N;
        if(table[i].compare(key)==0){
          table[i]="a";
          return cells;
        }
        cells++;
      } 
      return -1;
    }
 
    
    // TODO Implement print
    void print() {
      for(int i=0;i<N;i++){
        cout<<i <<"\t";
      }
      cout<<endl;
      for(int i=0;i<N;i++){
        if (table[i]=="a"){
          cout<<"\t";
        } else{
          cout<<table[i] <<"\t";
        }
        
      }
      cout<<endl;
    }
};
Expert Solution
steps

Step by step

Solved in 2 steps

SEE SOLUTIONCheck out a sample Q&A here
Blurred answer
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY
SEE MORE TEXTBOOKS