Hash Table reinserting after increasing in size

Question

I've been working on this hash table implementation and I've hit a roadblock. I modified the constructor and insert functions to be able to resize the array if capacity is reached, but I'm having problems with the resize. Right now, it seems to be infinitely inserting negative data and I'm not sure why. Should I implement an iterator within the resize or is there a simpler way of doing it?

Here are the functions:

resize:

template <class RecordType>
void table<RecordType>::resize( )
{

    RecordType *oldData = data;
    int oldSize = CAPACITY;
    int newSize = CAPACITY *2;

    //create a new table
    RecordType *newData;
    newData = new RecordType[CAPACITY];

    size_t i;
    used = 0;

    for (i = 0; i < CAPACITY; i++)
        newData[i].key = NEVER_USED;

    data = newData;
    delete[] newData;

    //place data from old table to new, larger table.
    for(int i = 0; i < oldSize; i++)
    {
            RecordType next = oldData[i];
            insert(next);
    }

    CAPACITY = newSize;
    delete[] oldData;
}

constructor:

template <class RecordType>
table<RecordType>::table( )
{
    CAPACITY = 30;
    data = new RecordType[CAPACITY];

    size_t i;

    used = 0;
    for (i = 0; i < CAPACITY; ++i)
        data[i].key = NEVER_USED;

}

insert:

template <class RecordType>
void table<RecordType>::insert(const RecordType& entry)
// Library facilities used: cassert
{
    bool already_present;   // True if entry.key is already in the table
    size_t index;        // data[index] is location for the new entry

    assert(entry.key >= 0);

    // Set index so that data[index] is the spot to place the new entry.
    find_index(entry.key, already_present, index);

    // If the key wasn't already there, then find the location for the new entry.
    if (!already_present)
    {
        if (size( ) >= CAPACITY)
        {
            resize( ); // resize the table.

            insert(entry); // reinsert entry into new table.
        }
        else if (size( ) < CAPACITY)
        {
            index = hash(entry.key);

            while (!is_vacant(index))
                index = next_index(index);
            ++used;
        }
    }

    data[index] = entry;
    size_t i;
    for (i=0; i<CAPACITY; i++) cout << data[i].key << ' ';
    cout << endl;
}

Thanks for the help!

Rob Rob · Accepted Answer · 2013-06-08T04:09:18

Your resize() is calling insert() which is putting data into the data[]. Then resize() overwrites data with the empty (full of NEVER_USED) newData array. My guess is that you want to get rid of newData and just use data instead.

You probably should rethink CAPACITY *= CAPACITY as well, as this is going to blow up when you try to use this code for something real.

Hash Table reinserting after increasing in size

1 Answers