I have an assignment where I must use perfect hashing to hash names from an input array, with the number of names given.
This is my code:
Dictionary.h
#include <string>
#include <vector>
using namespace std;
class Dictionary {
public:
// Insert an input set of n keys to the dictionary. This method should print out the following information:
// 1. The hash functions comprising the perfect hash (both levels)
// 2. The sum of squares of the number of keys mapped to each bin of the first level hash function, and
// 3. The number of trials needed to generate each hash function.
void bulkInsert(int n, string *keys);
// Insert a key to the dictionary.
// Print out whether the insertion caused a collision in the second level hash.
// Handle collision with separate chaining.
void insert(string key);
// Remove a key from the dictionary, if it exists.
void remove(string key);
// Return whether a key is found in the dictionary.
// Print the buckets (both first and second level) accessed during the operation.
bool find(string key);
//make random matrix and print after
void makeRandom(int nR, int nC);
//format key and hash for first level, return index of hash
int firstLevelHash(string input, int nR, int nC);
//print hash
void printHash();
private:
vector<vector<int>> randomMat;
vector<vector<int>> randomMat2;
vector<vector<string>> hashTable;
};
Dictionary.cpp
#include "Dictionary.h"
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <cstdlib>
#include <time.h>
#include <vector>
#include <algorithm>
using namespace std;
void Dictionary::bulkInsert(int n, string *keys) {
int numRow = (ceil(log2(n)));
int numCol = 64;
int trialNum = 1;
bool repeat = true;
while ( repeat ) {
//make random matrix
makeRandom(numRow, numCol);
//check hashtable empty, clear if not
if ( !( hashTable.empty() ) ) {
hashTable.clear();
}
//create hashtable, given by 2^numRow
for ( int i = 0; i < ( 2^numRow ); i++ ) {
vector<string> row;
hashTable.push_back(row);
}
//loop through keys and hash first level
for ( int i = 0; i<n; i++) {
int ind = firstLevelHash(keys[i], numRow, numCol);
hashTable[ind].push_back(keys[i]);
}
//check condition on whether to repeat hash
int limit = 4*n;
int summation = 0;
for ( int i = 0; i < hashTable.size(); i++ ) {
summation = summation + ((hashTable[i].size())^2);
}
if ( summation < limit ) {
repeat = false;
}
//second level hashing
}
}
void Dictionary::insert(string key) {
}
void Dictionary::remove(string key) {
}
bool Dictionary::find(string key) {
return false;
}
//randomizes randomMat and prints;
void Dictionary::makeRandom(int nR, int nC) {
vector<int> row;
for ( int i = 0; i < nR; i++ ) {
row.clear();
for ( int j = 0; j < nC; j++ ) {
int random = rand()%2;
row.push_back(random);
}
randomMat.push_back(row);
}
}
//returns vector for key of length 64
int Dictionary::firstLevelHash(string input, int nR, int nC) {
//check length of input
//if less than 8, add space to front
if ( input.size() < 8 ) {
for( int p = 0; p < 8-(input.size()); p++) {
input = " " + input;
}
}
//obtain string of length 64 of bits of input
string binStr = "";
for ( char& chr : input) {
binStr += bitset<8>(chr).to_string();
}
vector<int> keyVector;
//go through string and convert each to bit
for ( int i = 0; i < binStr.size(); i++ ) {
string substr = binStr.substr(i, 1);
int val = stoi(substr);
keyVector.push_back( val );
}
vector<int> hashFinalValue;
//multiply by hash
for ( int j = 0; j < nR; j++ ) {
int hashVal = 0;
for ( int p = 0; p < nC; p++ ) {
hashVal = hashVal + (randomMat[j][p] * keyVector[p]);
}
hashVal = hashVal % 2;
hashFinalValue.push_back( hashVal );
}
//convert binary to decimal to get index
int index = 0;
int q = 1;
for ( int m = 0; m < hashFinalValue.size(); m++ ) {
index += hashFinalValue[m] * ( 2^(hashFinalValue.size()-q) );
q++;
}
return index;
}
//prints hashTable
void Dictionary::printHash() {
for ( int i = 0; i < hashTable.size(); i++ ) {
for ( int j = 0; j < hashTable[i].size(); j++ ) {
cout << hashTable[i][j];
cout << " | ";
}
cout << "\n";
}
}
my_test_dictionary.cpp
#include "Dictionary.h"
#include <iostream>
using namespace std;
int main(){
cout<<"adfad";
Dictionary dict;
string strs[] = {"Fred Astaire", "Lauren Bacall", "Brigitte Bardot", "John Belushi", "Ingmar Bergman"};
int n = 5;
dict.bulkInsert(n, strs);
dict.printHash();
return 0;
}
When I compile using g++ Dictionary.cpp my_test_dictionary.cpp, I immediately get "Segmentation fault (core dumped)", and the "adfad" on the first line of main is not printed at all.
Please help. I am broken.
Your assertion that the program fails before reaching main is false. In fact, it crashes here:
#0 0x00007ffff7f60484 in std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >::basic_string(std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&) () from /usr/lib/x86_64-linux-gnu/libstdc++.so.6
#1 0x0000555555558783 in __gnu_cxx::new_allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > >::construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&> (this=0x5555555742b0, __p=0x31,
__args#0="Lauren Bacall") at /usr/include/c++/8/ext/new_allocator.h:136
#2 0x00005555555579ce in std::allocator_traits<std::allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::construct<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > const&> (__a=..., __p=0x31,
__args#0="Lauren Bacall") at /usr/include/c++/8/bits/alloc_traits.h:475
#3 0x00005555555570ea in std::vector<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> >, std::allocator<std::__cxx11::basic_string<char, std::char_traits<char>, std::allocator<char> > > >::push_back (this=0x5555555742b0, __x="Lauren Bacall") at /usr/include/c++/8/bits/stl_vector.h:1079
#4 0x000055555555650b in Dictionary::bulkInsert (this=0x7fffffffdb40, n=5, keys=0x7fffffffdaa0) at Dictionary.cc:39
#5 0x000055555555af9c in main () at my_test_dictionary.cc:12
This fact you would have trivially discovered if you'd run your program under debugger.
The reason you don't see the adfad output has to do with buffering (as Daniel Langr) already correctly noted.
To solve the buffering problem, always use std::cerr instead when adding "debug prints".
Now, the reason for actual crash is a bit hard to spot (but Botje did correctly spot it). This loop:
//create hashtable, given by 2^numRow
for ( int i = 0; i < ( 2^numRow ); i++ ) {
executes just once, not the 8 times you expected. See this answer for explanation.