Expand HashTable

[GeorgeGento]

Hello.I have a problem with my expand function and i cant get it to work.I runned the debugger and it has a segmentation fault at the pointers.The rest of the program is working .Any help would be appriciated.


void HashTable::Expand()
{
int index;
tablesize *= 2;
item *temphashtable = new item[tablesize];
for (int i=0;i < tablesize;i++)
{
index = Hash(hashtable[i].data);
if(temphashtable[index].data == -1)
{
temphashtable[index].data = hashtable[i].data;
}
else
{
item *New = new item;
New->data = -1;
New->next = NULL;
while(temphashtable[index].next != NULL)
{
temphashtable[index].next = temphashtable[index].next->next;
}
temphashtable[index].next = New;

}
while(hashtable[i].next != NULL)
{
index = Hash(hashtable[i].data);

if(temphashtable[index].data == -1)
{
temphashtable[index].data = hashtable[i].data;
}
else
{
item *New = new item;
New->data = hashtable.[data];
New->next = NULL;
while(temphashtable[index].next != NULL)
{
temphashtable[index].next = temphashtable[index].next->next;
}
temphashtable[index].next = New;

}
}

}
delete[]hashtable;
item *hashtable = new item[tablesize];
for (int i=0;i < tablesize;i++)
{
index = Hash(temphashtable[i].data);
if(hashtable[index].data == -1)
{
hashtable[index].data = temphashtable[i].data;
}
else
{
item *New = new item;
New->data = temphashtable[i].data;
New->next = NULL;
while(hashtable[index].next != NULL)
{
hashtable[index].next = hashtable[index].next->next;
}
hashtable[index].next = New;

}
while(temphashtable[i].next != NULL)
{
index = Hash(temphashtable[i].data);
if(hashtable[index].data == -1)
{
hashtable[index].data = temphashtable[i].data;
}
else
{
item *New = new item;
New->data = temphashtable[i].data;
New->next = NULL;
while(hashtable[index].next != NULL)
{
hashtable[index].next = hashtable[index].next->next;
}
hashtable[index].next = New;
}
}

}
delete[]temphashtable;

}

[jonnin]

delete[]hashtable;
item *hashtable = new item[tablesize];
this should not compile, it should say variable redeclare. how can it crash if it can't compile? Also, put in code tags <> on the side bar editor. No one wants to read the whitespace stripped code.

I don't know what the heck you are doing, to be honest.
it should be one of a couple of patterns.
most likely guess is you want this pattern:

make new bigger table
for all of old table, check each location if used. if used, re-hash that data into new table using your NEW, LARGER TABLE SIZE AWARE hash function.
for example
srand(datatoint(yourdata));
while(location not used) location = rand()%newtablesize; check location;
newtable[location] = olddata;
or something like that.

delete old table/ swap in new table.

I lost track in the indents but this is way, way, way too much code for what you appear to be doing.

[dhayden]

int index;
tablesize *= 2;   // IMPORTANT. tablesize is now the NEW table size. Don't forget!
item *temphashtable = new item[tablesize];
for (int i=0;i < tablesize;i++)    // You forgot.
{
index = Hash(hashtable[i].data);  // i goes out of bounds. 

Use separate variables for the old and new table sizes. I suspect you'll need a local variable for the old table size because Hash() probably uses the new tablesize.

[dhayden]

I think one problem is that hashtable is an array of items. It should be an array of pointers to items. Basically each entry in hashtable is the head pointer to a linked list of items in that bucket.

As I mentioned before, be crystal clear about what is the old size and what is the new. Also about what is an index into the old hashtable and what is an index into the new one.

NEVER walk through a linked list to add items to its tail (O(n) time). Always prefer to add to the head (2 instructions). This is what simple singly linked lists are for.

The code below compiles but I haven't tested it.

class HashTable {
private:
    struct item {		// an item in a bucket
	int data;
	item *next;
    };

    void Expand();
    unsigned tableSize;		// size of the table
    item** hashtable;		// array of tablesize pointers. Each
				// is the head of a list of items in
				// that bucket 
    unsigned Hash(int);		// return the hash value for an item's data
};

void
HashTable::Expand()
{
    unsigned oldTableSize = tableSize;
    tableSize *= 2;		// note: Hash() will now hash into new size
    
    // Each bucket contains the head pointer to a list of items in that
    // bucket.
    item **newhashtable = new item* [tableSize]; // create new table

    for (unsigned oldIndex = 0; oldIndex < oldTableSize; oldIndex++) { // for each old bucket
	while (item *cur = hashtable[oldIndex]) {
	    hashtable[oldIndex] = cur->next;		// remove it from old table
	    unsigned newIndex = Hash(cur->data);	// get the new index
	    cur->next = newhashtable[newIndex];		// add new item to the HEAD of the list
	    newhashtable[newIndex] = cur;
	}
	// When you get here, hashtable[i] is nullptr
    }

    delete[]hashtable;		// delete the old buckets
    hashtable = newhashtable;	// switch to the new buckets.
}

[GeorgeGento]

Thanks for the replies.I've fixed the problem.