c++linked-listhashmaphash-function

How to correctly implement hash insert function in c++?


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!


Solution

  • 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);
    }