Hash table's resizing crashes program

Question

I'm trying to implement Hash Table in c++ using STL list of pairs. Initial maxSize I set to 1, and I'd like to increase hash table's size twice as soon as its currentSize is greater than 75% of maximum capacity. I am getting error "Cannot dereference end list operator". Here is my implementation:

template<class V>
class HashTable {
public:
    int currentSize;
    int maxSize;
    std::list<std::pair<std::string, V> > *arr;

    HashTable() {
        this->currentSize = 0; 
        this->maxSize = 1; 
        this->arr = new std::list<std::pair<std::string, V> >[maxSize];
        arr->assign(maxSize, std::pair<std::string, V>());
    }
    ~HashTable() {
        delete[] arr;
    }

    void add(std::string key, V value) {
        if (currentSize >= 0.75 * maxSize) {
            rehash();
        }
        currentSize++;
        int idx = hashFunction(key);
        std::list<std::pair<std::string, int> >::iterator it = arr->begin();
        std::advance(it, idx);
        it = arr->erase(it);
        arr->insert(it, std::pair<std::string, V> (key, value));
    }

    int hashFunction(std::string key) {
        int total = 0;
        for (int i = 0; i < key.length(); i++) {
            total += int(key[i]) * pow(31, key.length() - i - 1);
        }
        return total % maxSize;
    }

    void rehash() {
        maxSize *= 2;
        std::list<std::pair<std::string, V> > *newArr = new std::list<std::pair<std::string, V> >[maxSize];
        newArr->assign(maxSize, std::pair<std::string, V>());
        for (auto it = arr->begin(); it != arr->end(); it++) {
                int idx = hashFunction(it->first);
                it = arr->begin();
                std::advance(it, idx);
                it = arr->erase(it);
                newArr->insert(it, std::pair<std::string, V>(it->first, it->second));
        }
        delete[] arr;
        arr = newArr;
    }

Interesting fact to point is that when I hard-code the maxSize for example by setting it to 20 and then adding 2 elements, it works and outputs e.g. "1: abc -> 123, 5: bca -> 42".

`std::list > *arr;` -- Why not `std::vector >> arr;`? That removes you having to do any manual memory management. — PaulMcKenzie, Dec 02 '20 at 13:27
I see a [Rule of Three](https://stackoverflow.com/questions/4172722/what-is-the-rule-of-three) violation, though I'm not sure if this is the cause of errors. Why do you use manual memory management instead of `std::vector`? — Yksisarvinen, Dec 02 '20 at 13:27
And you don't seem to use that array. You only ever use first element of that array. — Yksisarvinen, Dec 02 '20 at 13:30
`int main() { HashTable h1; HashTable h2 = h1; }` -- That simple program has a double-delete error. — PaulMcKenzie, Dec 02 '20 at 13:36

Sam Varshavchik · Accepted Answer · 2020-12-02T13:40:02.637

There are multiple bugs in the shown code.

In your rehash:

it = arr->erase(it);

erase() always returns an iterator to the value that follows the one that was just erased. That's how it works. So, if it already happened to be referencing the last value in arr, erase() removes it and effectively returns end(). Afterwards:

for (  ... ; it++)

This ends up increment it, as always. But in this case it is already end(). Incrementing the end() iterator value is undefined behavior.

Additionally:

newArr->insert(it, ...

it is not an iterator to newArr, it is an iterator to another container. An iterator can only be passed as a parameter to its own container's insert(). More undefined behavior.

Hash table's resizing crashes program

1 Answers1