The Problem

We usually restrict the range of hash functions so as to store them in an array. In this POTD, well 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, well 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, well obtain M permutations of the string. To do so, well use the function std::next_permutation() to permute the string. A sample usage for a string str is 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 untill 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 collisionsM, which is a measure of how good the hash function is.

//Hash.cpp

#include

#include

#include

#include

#include "Hash.h"

unsigned long bernstein(std::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(std::string str, int M)

{

std::vector* array = new std::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 determining goodness

return goodness;

}

//Hash.h

#ifndef _HASH_H #define _HASH_H

#include #include #include #include

unsigned long bernstein(std::string str, int M); float hash_goodness(std::string str, int M);

#endif

The Problem We usually restrict the range of hash functions so as to store them in an array. In this 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 oharacters 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 oollision. Speoifically, given a string str and the range M of the hash funotion, we'll obtain M permutations of the string. To do so, we'll use the funotion std: :next_permutation() to permute the string. A sample usage for a string str is 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 funotion std: :next_permutation() keeps supplying permutations untill it reaches the last permutation alphabetically. You must stop permuting beyond M permutations. Your task today is to write a funotion 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.705882 Goodness of hash Bernstein hash function for "arbitrary" with range-52 is: 0.75 Goodness of hash Bernstein hash function for "arbitrary" with range-53 is: 0.283019 Goodness of hash Bernstein hash function for "arbitrary" with range-54 is: 0.574874 Goodness of hash Bernstein hash function for "arbitrary" with range-55 is: 0.672727 How does the goodness oompare for range values 64, 67 and 100? And for prime numbers in general? The Problem We usually restrict the range of hash functions so as to store them in an array. In this 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 oharacters 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 oollision. Speoifically, given a string str and the range M of the hash funotion, we'll obtain M permutations of the string. To do so, we'll use the funotion std: :next_permutation() to permute the string. A sample usage for a string str is 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 funotion std: :next_permutation() keeps supplying permutations untill it reaches the last permutation alphabetically. You must stop permuting beyond M permutations. Your task today is to write a funotion 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.705882 Goodness of hash Bernstein hash function for "arbitrary" with range-52 is: 0.75 Goodness of hash Bernstein hash function for "arbitrary" with range-53 is: 0.283019 Goodness of hash Bernstein hash function for "arbitrary" with range-54 is: 0.574874 Goodness of hash Bernstein hash function for "arbitrary" with range-55 is: 0.672727 How does the goodness oompare for range values 64, 67 and 100? And for prime numbers in general