user3011391 user3011391 - 1 month ago 17
Java Question

Re-Sizing Hash Table

I'm attempting to resize my

hash table
however; I am keep getting a
NullPointerException
.
I know if the size is greater than
0.75
then the table size has to double, if it's less than
0.50
then the table size is halved. So far I have this..

public boolean add(Object x)
{
int h = x.hashCode();
if (h < 0) { h = -h; }
h = h % buckets.length;

Node current = buckets[h];
while (current != null)
{
if (current.data.equals(x)) { return false; }
// Already in the set
current = current.next;
}
Node newNode = new Node();
newNode.data = x;
newNode.next = buckets[h];
buckets[h] = newNode;
currentSize++;
double factor1 = currentSize * load1; //load1 = 0.75
double factor2 = currentSize * load2; //load2 = 0.50
if (currentSize > factor1) { resize(buckets.length*2); }
if (currentSize < factor2) { resize(buckets.length/2); }

return true;
}


Example.
Size = 3. Max Size = 5


if we take the
Max Size
and multiply by
0.75
we get
3.75
.

this is the factor that says if we pass it the
Max Size
must
double


so if we add an extra
element
into the
table
the size is
4
and is
> 3.75
thus the new
Max Size
is
10
.

However; once we increase the size, the
hashcode
will change with the addition of a new
element
, so we call
resize(int newSize)


private void resize(int newLength)
{
//
HashSet newTable = new HashSet(newLength);

for (int i = 0; i < buckets.length; i++) {
newTable.add(buckets[i]);
}
}


Here is my constructor if the
buckets[i]
confuses anyone.


public HashSet(int bucketsLength)
{
buckets = new Node[bucketsLength];
currentSize = 0;
}


I feel that the logic is correct, unless my
resize
method is not retrieving the
elements
.

Answer

If that is all your code for resize(), then you are failing to assign newTable to a class attribute, i.e. your old table. Right now you fill it with data and then don't do anything with it, since it is defined inside resize and therefore not available outside of it.

So you end up thinking you have a larger table now, but in fact you are still using the old one ;-)