Hash Table implementing Resize function

Question

I've been given an assignment to adjust a hash table implementation to allow for dynamic resizing. While I've looked around for clues and info, I'm still confused as to how hash tables behave and therefore how I should go about with the resize. I was told I need to add a resize function, call it in insert and modify the constructor. I think I've done right with the insert, seems simple enough, but the resize itself and the constructor are what I'm struggling with.

EDIT: So I've worked on the resize function, insert and constructor but I'm getting an error at the for loop in resize() to insert old data into the larger table, and I'm not sure what is going wrong now. Any ideas?

Here is the header:

#ifndef TABLE1_H
#define TABLE1_H
#include <cstdlib>    // Provides size_t
#include <cassert>  // Provides assert

namespace main_savitch_12A
{
template <class RecordType>
class table
{
public:
size_t CAPACITY; 
    // CONSTRUCTOR
    table( );
    // MODIFICATION MEMBER FUNCTIONS
    void insert(const RecordType& entry);
    void remove(int key);
void resize( );
    // CONSTANT MEMBER FUNCTIONS
    bool is_present(int key) const;
    void find(int key, bool& found, RecordType& result) const;
    size_t size( ) const { return used; }
private:
    // MEMBER CONSTANTS -- These are used in the key field of special records.
    enum { NEVER_USED = -1 };
    enum { PREVIOUSLY_USED = -2 };
    // MEMBER VARIABLES
    RecordType *data; //[CAPACITY];
    size_t used;
    // HELPER FUNCTIONS
    size_t hash(int key) const;
    size_t next_index(size_t index) const;
    void find_index(int key, bool& found, size_t& index) const;
    bool never_used(size_t index) const;
    bool is_vacant(size_t index) const;
};

constructor implementation:

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;

}

resize implementation:

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

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

    //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;

    //place data from old table to new, larger table.
    for (int i = 0; i < oldSize; i++)
    {
        insert(newData[hash(i)]); //this is where I'm having trouble.
    }

    data = newData;
    delete[] oldData;
}

insert implementation:

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!

You could just build a new table, fill it with your old data, and then swap the data. — Vaughn Cato

Mats Petersson Mats Petersson · Accepted Answer · 2013-06-07T23:41:45

Currently, data is a fixed size array. You need a variable size storage

RecordType data[CAPACITY];

So, data needs to be a pointer rather than a fixed array, and you need to dynamically allocate it in the constructor.

Of course, also change CAPACITY from being a constant to a variable (per table, so not static - I would change it's name to something that doesn't look like a macro/constant too.

This bit is "almost there":

table *newT;
newT = new table(newSize);

The type should not be the hashtable, but RecordType.

And, as the comment says, you need to transfer the current data to the new data, and then make the new table the current data. Finally, delete the now old data.

Edit: I'm intentionally NOT writing the code for you. Your task is to learn. I wrote dynamically resizeable hash-tables some 20-odd years back, and I don't think I need to practice it right now. You are the one learning how to do it.

Hash Table implementing Resize function

1 Answers