C++: How do I lower the collision count? CODE TO BE FIXED #include <iostream> #i
ID: 3707394 • Letter: C
Question
C++:
How do I lower the collision count?
CODE TO BE FIXED
#include <iostream>
#include <string>
#include <cmath>
#include <fstream>
using namespace std;
long hashcode(char* s){
unsigned long seed = 31;
unsigned long hash = 0;
for (int i = 0; i < strlen(s); i++){
hash = (hash * seed) + s[i];
}
return hash % 10007;
};
int main(int argc, char * argv[]){
int count = 0;
int collisions = 0;
fstream input(argv[1]);
char x;
long array[30000] = { 0 };
//File stream
while (!input.eof()){
input >> x;
array[count] = hashcode(&x);
for(int i = 0; i<count; i++){
if(array[i]==array[count]){
collisions++;
break;
}
}
count++;
}
cout << "Total Input is " << count - 1 << endl;
cout << "Collision # is " << collisions << endl;
return 0;
}
... ./a.out f1
Total Input is 100000
Collision # is 89995
output should be:
The program should read the contents of the file, calculate the h(s) mod 10007 value, checks whether some other string generates the same value. If there, increase the collision counter by one. After processing all the inputs, the program prints out the total number of strings and the number of collisions. For example, we list the following command line and the results of this command.
./a.out f1
Total Input is 10000
Collision # is 4744
f1:
lglwneynql
iufefwvzxw
wtlzotieuc
qgrgfewomj
fcuggrkvca
zwpedsmlwl
nfkotdyjkq
xnyvfhhkhk
yfuzdopdnx
ciuynoedek
ragjueltld
mlbhmvztvu
lqsotznhsm
....
Explanation / Answer
#include <algorithm>
#include <iostream>
#include <string>
#include <cmath>
#include <fstream>
using namespace std;
long hashcode(char* s){
unsigned long seed = 31;
unsigned long hash = 0;
for (int i = 0; i < strlen(s); i++){
hash = (hash * seed) + s[i];
}
return hash % 10007;
};
int main(int argc, char * argv[]){
int count = 0;
int collisions = 0;
fstream input(argv[1]);
char x;
long array[30000] = { 0 };
//File stream
while (!input.eof()){
input >> x;
array[count] = hashcode(&x);
for(int i = 0; i<count; i++){
if(array[i]==array[count]){
collisions++;
break;
}
}
count++;
}
cout << "Total Input is " << count - 1 << endl;
cout << "Collision # is " << collisions << endl;
return 0;
}
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.