Data Structure in C++ Testing hash functions I tried this homework and there are

ID: 3842306 • Letter: D

Question

Data Structure in C++

Testing hash functions

I tried this homework and there are errors.

Please check my code and fix errors.

#include<iostream>
#include<fstream>
#include<functional>
#include<string>
#include<vector>
#include<cstdint>
#include<cmath>
#include<boost/math/distributions/chi_squared.hpp>
using std::cout;
using std::cin;
using std::endl;
using std::vector;
using std::string;
using std::ifstream;
using std::pow;

uint16_t x;

class hash_table{
public:
hash_table(){
hashes.resize(65536);
}

void h_length(string s){
hashes.at((s.length() % int(pow(2,16))))++;
}

void h_fchar(string s){
char fchar = s.front();
hashes.at(fchar)++;
}

void h_checksum(string s) {
int sum = 0;
for(int i = 0; i < s.length(); ++i){
sum += char(s[i]);
hashes.at(sum)++;
}
}

int checksum(string s){
int k = 0;
for(int i = 0; i < s.length(); ++i){
k = (k + 256 + s.at(i)) % 65536;
}
return k;
}

int frac(int k){
int m = 65536;
double d;
float i = j * 0.6180339887
float f = modf(i, &d);
float fr = f*m;
return fr;
}

void h_remainder(string s) {
int i = (checksum(s) % 65413);
hashes.at(i)++;
}

void h_multiplicative {
int i = frac(checksum(s));
hashes.at(i)++;
}

float chi_sq(){
boost::math::chi_squared c2d(65535.0);
float c2 = 0;
float expected_num = 99171/65536;
for(int i = 0; i < hashes.size(); i++){
c2 += ((pow((expected_num - hashes.at(i)), 2)) / expected_num);
}
float p = boost::math::cdf(c2d, c2);
return p;
}

private:
vector<int> hashes;
//vector<value> table;
}

int main () {
ifstream myfile;
myfile.open("words.txt");

string word;

cout << "String length: p = " << << endl;
cout << "First character: p = " << endl;
cout << "Checksum: p = " << endl;
cout << "Remainder: p = " << endl;
cout << "Multiplicative: p = " << endl;

return 0;
}

Your hash functions will hash strings into 16-bit (not 32-bit) int s. This is important, because were going to keep a table of the number of collisions for each hash value. With 16-bit int s there are only 65.536 possible hash values. so this table will easily fit in memory. If we used 32-bit int s then there would be 4,294,967.296 possble hashes. a more troublesome amount. For C you can get a 16-bit unsigned int type by doing #include cstdint uint16_t x; x has exactly 16 bits and is signed For each of the possible hash functions your program should Create a vector int hashes of size 65.536 Process the list of words. and for each word, compute its hash h Increment the entry in the table for that hash: hashes.at(h)++ When finished, use Pearson'sX test to determine the probability that the resulting distribution is uniformly distributed. (See below for the deets.) Hash functions to test The hash (non)functions you should test are: String length (modulo 16 First character 16 Additive checksum (add all characters together), modulo 2 Remainder (use a modulo of 65413. this is the first prime that is smaller than the table size). This will also test the base-256 mod 216 hash function Multiplicative (using the scheme described in class/in the lecture notes) Any other hash schemes you can think up. (ld suggest making your hash testing function take a function pointer. so that you can just write all the above hash functions and then test them one by one.)

Explanation / Answer

please find the below code: