//main.cpp

//main.cpp

#include

#include

#include

#include

using namespace std;

unsigned long bernstein(string str, int M)

{

unsigned long b_hash = 5381;

for (int i = 0; i

{

b_hash = b_hash * 33 + str[i];

}

return b_hash % M;

}

float hash_goodness(string str, int M)

{

// vector array[M]; // Hint: This comes in handy

vector* array = new vector[M}; // Hint: This comes in handy

int permutation_count = 0;

float goodness = 0;

do {

if (permutation_count == M) break;

// Code for computing the hash and updating the array

} while(std::next_permutation(str.begin(), str.end()));

//Code for detecting number of collisions

return goodness;

}

int main()

{

string s = "arbitrary";

for (int i = 51; i

{

cout

}

}

The Problem We usually restrict the range of hash functions so as to store them in an array. Inthis POTD, we'll try to study the effect of the range on the performance of the hash function. The performance here shall be measured in terms of the number of collisions that we encounter with the hash function. As we saw in the last POTD, the hash function for a string is sensitive to the order in which the characters in the string are arranged. Here, we'll test the hashing by repeatedly shuffling a string and observing how often the hash of a shuffled string results in a collision. Specifically, given a string str and the range M of the hash function, we'll obtain M permutations of the string. To do so, we'll use the function std next permutation to permute the string. A sample usage for a string str s as follows: do str now contains a permutation of the original string stop permuting after M permutations while (std: next permutation (str.begin str.end The function std: next permutation keeps supplying permutations till it reaches the last permutation alphabetically. You must stop permuting beyond M permutations. Your task today is to write a function hash goodness that takes in a string (str) and the range of the hash (M) as the inputs. For M permutations of str count the number of collisions that result by using the Bernstein hash. Return collisions M which is a measure of how good the hash function is Example output: Goodness of hash Bernstein hash function for arbitrary with range 51 is: 0.294118 Goodness of hash Bernstein hash function for arbitrary with range 52 is 0.25 How does the goodness compare for range values 64, 67 and 100? And for prime numbers in general? Compile and Test A complete Makefile and a main. cpp file containing one simple test has been provided for you. To compile and run, run make /main The Problem We usually restrict the range of hash functions so as to store them in an array. Inthis POTD, we'll try to study the effect of the range on the performance of the hash function. The performance here shall be measured in terms of the number of collisions that we encounter with the hash function. As we saw in the last POTD, the hash function for a string is sensitive to the order in which the characters in the string are arranged. Here, we'll test the hashing by repeatedly shuffling a string and observing how often the hash of a shuffled string results in a collision. Specifically, given a string str and the range M of the hash function, we'll obtain M permutations of the string. To do so, we'll use the function std next permutation to permute the string. A sample usage for a string str s as follows: do str now contains a permutation of the original string stop permuting after M permutations while (std: next permutation (str.begin str.end The function std: next permutation keeps supplying permutations till it reaches the last permutation alphabetically. You must stop permuting beyond M permutations. Your task today is to write a function hash goodness that takes in a string (str) and the range of the hash (M) as the inputs. For M permutations of str count the number of collisions that result by using the Bernstein hash. Return collisions M which is a measure of how good the hash function is Example output: Goodness of hash Bernstein hash function for arbitrary with range 51 is: 0.294118 Goodness of hash Bernstein hash function for arbitrary with range 52 is 0.25 How does the goodness compare for range values 64, 67 and 100? And for prime numbers in general? Compile and Test A complete Makefile and a main. cpp file containing one simple test has been provided for you. To compile and run, run make /main