реализация пользовательской хеш-таблицы - ошибка памяти при отображении строк в целые числа - PullRequest
Новая
       16

реализация пользовательской хеш-таблицы - ошибка памяти при отображении строк в целые числа

0 голосов
/ 10 ноября 2019

Я практикую реализацию хэш-карты в C ++. Моя цель - в конечном итоге сопоставить слова с парой целых чисел, соответствующих их строке и столбцу в текстовом файле. Я взял реализацию хеш-карты из здесь и основывался на этом. Код работает нормально, когда я передаю слова только одной буквой. Однако, когда у меня есть слово с более чем одной буквой, код компилируется в Visual Studio, но во время выполнения при нарушении прав чтения в этой строке: 

HashNode<K, V> *entry = table[hashValue];

(внутри функции-члена insert). Я подумал, что могут быть некоторые хитрости, которые я должен учитывать при использовании струн в структуре храма, о которых я мог не знать;Тем не менее, я не мог найти его после нескольких часов поиска в Интернете. Любые идеи о том, как это исправить, с благодарностью. 

#include <string>
#include <iostream>
#include <tuple>
#include <vector>
using namespace std;

#define TABLE_SIZE 1028

template <typename K, typename V>
class HashNode {
public:
    HashNode(const K &key, const V &value) :
        key(key), value(value), next(NULL) {
    }

    K getKey() const {
        return key;
    }

    V getValue() const {
        return value;
    }

    void setValue(V value) {
        HashNode::value = value;
    }

    HashNode *getNext() const {
        return next;
    }

    void setNext(HashNode *next) {
        HashNode::next = next;
    }

private:
    // key-value pair
    K key;
    V value;
    // next bucket with the same key
    HashNode *next;
};

template <typename K, typename V, typename F = KeyHash<K>>
class HashMap {
public:
    HashMap() {
        // construct zero initialized hash table of size
        table = new HashNode<K, V> * [TABLE_SIZE]();
    }

    ~HashMap() {
        // destroy all buckets one by one
        for (int i = 0; i < TABLE_SIZE; ++i) {
            HashNode<K, V> *entry = table[i];
            while (entry != NULL) {
                HashNode<K, V> *prev = entry;
                entry = entry->getNext();
                delete prev;
            }
            table[i] = NULL;
        }
        // destroy the hash table
        delete[] table;
    }

    void get(const K &key, vector<V> &value) {
        unsigned long hashValue = hashFunc(key);
        HashNode<K, V> *entry = table[hashValue];

        while (entry != NULL) {
            if (entry->getKey() == key) {
                value.push_back(entry->getValue());
                //return true;
            }
            entry = entry->getNext();
        }
        //return false;
    }

    void insert(const K &key, const V &value) {
        unsigned long hashValue = hashFunc(key);
        HashNode<K, V> *prev = NULL;
        HashNode<K, V> *entry = table[hashValue];

        while (entry != NULL && entry->getKey() == key) {
            prev = entry;
            entry = entry->getNext();
        }

        if (entry == NULL) {
            entry = new HashNode<K, V>(key, value);
            if (prev == NULL) {
                // insert as first bucket
                table[hashValue] = entry;
            }
            else {
                prev->setNext(entry);
            }
        }
        else {
            // just update the value
            entry->setValue(value);
        }
    }

    void remove(const K &key) {
        unsigned long hashValue = hashFunc(key);
        HashNode<K, V> *prev = NULL;
        HashNode<K, V> *entry = table[hashValue];

        while (entry != NULL && entry->getKey() != key) {
            prev = entry;
            entry = entry->getNext();
        }

        if (entry == NULL) {
            // key not found
            return;
        }
        else {
            if (prev == NULL) {
                // remove first bucket of the list
                table[hashValue] = entry->getNext();
            }
            else {
                prev->setNext(entry->getNext());
            }
            delete entry;
        }
    }

private:
    // hash table
    HashNode<K, V> **table;
    F hashFunc;
};


int main()
{
    struct MyKeyHash
    {
        unsigned long operator()(const string & s) const
        {
            int hash = 7;
            for (int i = 0; i < s.length(); i++)
            {
                hash = hash * 31 + s[i];
            }
            return hash;
        }
    };

    HashMap<string, tuple<int, int>, MyKeyHash> hmap;
    hmap.insert("BB", make_pair(3, 3));
    hmap.insert("A", make_pair(1, 2));
    hmap.insert("A", make_pair(4, 2));

    vector<tuple<int, int>> value;
    hmap.get("B", value);
    for (auto it : value)
    {
        cout << get<0>(it) << ", " << get<1>(it) << endl;
    }
}

Ответы [ 2 ]

1 голос
/ 10 ноября 2019

Вы пропустили важный шаг для использования хэш-карты. Вы вычислили хеш, и у вас есть таблица для хранения вещей, но вы не можете использовать хеш напрямую как индекс в таблице. Его необходимо уменьшить по модулю размера таблицы, чтобы поддерживать корректность индекса.

В этом случае после вычисления хеша (вызова члена hashFunc) необходимо включить 

hashValue = hashValue % TABLE_SIZE;

В конечном итоге вы захотите добавить код, чтобы определить, когда вам нужно увеличить размер хеш-таблицы, что потребует, чтобы TABLE_SIZE был членом HashMap.

1 голос
/ 10 ноября 2019 
unsigned long hashValue = hashFunc(key);
//...
table[hashValue]

hashValue возвращается из функции 

unsigned long operator()(const string & s) const
{
    int hash = 7;
    for (int i = 0; i < s.length(); i++)
    {
        hash = hash * 31 + s[i];
    }
    return hash;
}

, которая может возвращать произвольно большие значения (в диапазоне int). Но table - это массив длиной TABLE_SIZE (1028). Если выходное значение оказывается больше этого значения, вы обращаетесь к нему за пределами.

При написании функции это более вероятно произойдет для более длинных входных строк.

Вы, вероятно, имели в виду 

unsigned long hashValue = hashFunc(key)%TABLE_SIZE;

Также обратите внимание, что ваша хеш-функция переполняется, вызывая неопределенное поведение (потому что вы используете целые числа со знаком), если строка достаточно длинная. Вы должны использовать unsigned long вместо int, соответствовать типу возвращаемого значения и быть без знака.

...