Hash Table Bug

closed account (oEwqX9L8)
I have been trying to fix a bug in a hash table and can't seem to figure out the issue.

I get to the point with a table that looks like this:
hash 0:
hash 1: tuft
hash 2: bale done

Next I try to add a word ("toga") but I get a segmentation fault. The code breaks when I call "delete[] table;" (line 13) after rehashing the items into the new table in the following code.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void rehashTable(unsigned int newCapacity) {
    if (newCapacity == 0) {
      clear();
    }
    else {
      LinkedList<ItemType>* temp = new LinkedList<ItemType> [newCapacity];
      unsigned int oldCapacity = capacity;
      capacity = newCapacity;
      for (int i = 0; i < oldCapacity; i++) {
        for (int q = 0; q < table[i].getSize(); q++) {      temp[hashItem(table[i].getItem(q))].insertItem(temp[hashItem(table[i].getItem(q))].getSize(), table[i].getItem(q));
        }
      }
      delete[] table;
      table = temp;
    }
  }


I've been working with this for a long time and can't figure it out. Any ideas? Thanks!
Last edited on
closed account (48bpfSEw)
make your code more waterproof!

check if temp is not null after allocation with new.

check if you access within the borders of the size of table

flatten the comands on line 10 so that you can dump debug informations about parameters and returned values.

such ugly errors are a sign for bad memory writting/accessing.
you should set the compiler option to verify array accessings.

good luck!

As Necip suggested: You should improve line 10.

table[i].getItem(q) is used three times.
hashItem(...) two times.

So it would be better:
1
2
3
4
5
6
7
for (int q = 0; q < table[i].getSize(); q++)
{
      ... item = table[i].getItem(q);
      ... hash = hashItem(item);

      temp[hash].insertItem(temp[hash].getSize(), item); // Is using temp...getSize() correct at this point?
}


You problem is most likely an out of bounds access. Using hash as index is not a good idea. So you need to figure out where you use an invalid index.
closed account (oEwqX9L8)
Thanks for all your help everyone, I appreciate it!
Topic archived. No new replies allowed.