I need to read a file and then store each word to the hash table with linked list collision handling, and count how many times each word appeared (node's value). When I run my code with small text (like 30 lines) it works, but starting from about 100 it crashes (Segmentation fault: 11). I know my hashCode
function is bad but it should not crash. I think the problem is how I increment the value.
using namespace std;
class HashNode
{
public:
string key;
string value;
public:
HashNode(string key, int value)
{
this->key = key;
this->value = value;
}
friend class HashTable;
};
class HashTable {
private:
list<HashNode> *buckets;
int size;
int capacity;
int collisions;
public:
HashTable(int capacity){
buckets = new list<HashNode>[capacity];
this->capacity = capacity;
this->size = 0;
this->collisions = 0;
}
~HashTable()
{
for (int i = 0; i < capacity; i++)
buckets[i].clear();
delete[] this->buckets;
}
int hashCode(string key)
{
int sum = 0;
for (int k = 0; k < key.length(); k++)
sum = sum + int(key[k]);
return sum % capacity;
}
void insert(string key)
{
int value=0;
int index = hashCode(key) % this->capacity;
for (list<HashNode>::iterator it = buckets[index].begin(); it != buckets[index].end(); ++it)
if (it->key == key)
{
it->value+=1;
return;
}
if (buckets[index].size() > 0)
collisions++;
buckets[index].push_back(HashNode(key, value));
this->size++;
}
int getCollisions()
{
return this->collisions;
}
};
int main() {
string user_input;
string word;
ifstream inFile;
string parameter;
string command;
HashTable object(80000);
inFile.open("file.txt");
cout << "Welcome " << endl;
if (!inFile)
{
cout << "Unable to open the file";
exit(1);
}
listOfCommand();
while (inFile >> word)
{
object.insert(word);
}
}
What can cause this crash? Any help will be appreciated!
Most likely char is signed in your system, so converting it to integer in line sum = sum + int(key[k]);
results in negative value, and then you get segmentation fault when try to get buckets[index]
with negative index.
A quick way to fix it would be at first to convert key[k]
to unsigned char, and only then to int:
for (int k = 0; k < key.length(); k++) {
unsigned char c = static_cast<unsigned_char>(key[k]);
sum = sum + static_cast<int>(c);
}