I'm reading Data structures and algorith analysis by Weiss lately. There's just one part that doesn't make sense to me at all.

``````public class QuadraticProbingHashTable<AnyType>
{
{
this(DEFAULT_TABLE_SIZE);
}

{
allocateArray(size);
makeEmpty();
}

public void makeEmpty()
{
currentSize = 0;
for (int i = 0; i < array.length;i++)
array[i] = null;
}

public boolean contains(AnyType x)
{
int currentPos = findPos(x);
return isActive(currentPos);
}

public void insert(AnyType x)
{
int currentPos = findPos(x);
if (isActive(currentPos))
return;

array[currentPos] = new HashEntry<AnyType>(x,true);
double asd = (double) ++currentSize / (double) array.length;
if (asd > 0.7)       // Rehash
rehash();
}

public void remove(AnyType x)
{
int currentPos = findPos(x);
if( isActive(currentPos))
array[currentPos].isActive = false;
}

public static class HashEntry<AnyType>
{
public AnyType element;
public boolean isActive;

public HashEntry(AnyType e)
{this(e,true);}

public HashEntry(AnyType e, boolean i)
{element = e; isActive = i;}
}

public String toString()
{
String returnString = new String();
for(int a=0; a < array.length; a++)
{
returnString += a+". ";
if(array[a] == null)
returnString += "null" + "\n";
else
returnString += array[a].element.toString() + "\n";
}

return returnString;
}

private static final int DEFAULT_TABLE_SIZE = 11;

private HashEntry<AnyType> [ ] array;
private int currentSize;

private void allocateArray(int arraySize)
{
array = new HashEntry[arraySize];
}

private boolean isActive(int currentPos)
{
return array[currentPos] != null && array[currentPos].isActive;
}

private int findPos(AnyType x)
{
int offset = 1;
int currentPos = myhash(x);

while (array[currentPos] != null && !array[currentPos].element.equals(x))
{
currentPos += offset;
offset += 2;
System.out.println("currentPos: " + currentPos);
if (currentPos >= array.length)
currentPos -= array.length;
}
return currentPos;
}

private void rehash()
{
HashEntry<AnyType> [ ] oldArray = array;
allocateArray(nextPrime(2 * oldArray.length));
currentSize = 0;

for(int i = 0; i < oldArray.length; i++)
if(oldArray[i] != null && oldArray[i].isActive)
insert(oldArray[i].element);
}

private int myhash(AnyType x)
{
int hashVal = x.hashCode( );

hashVal %= array.length;
if( hashVal < 0 )
hashVal += array.length;

return hashVal;
}

private static int nextPrime( int n )
{
if( n % 2 == 0 )
n++;

for( ; !isPrime( n ); n += 2 )
;

return n;
}

private static boolean isPrime( int n )
{
if( n == 2 || n == 3 )
return true;

if( n == 1 || n % 2 == 0 )
return false;

for( int i = 3; i * i <= n; i += 2 )
if( n % i == 0 )
return false;

return true;
}
}``````

when the table is rehashed when the load factor is > 0.5 the table works. But higher load factor gives "arrayindexoutofbound".

Shouldn't the offset be set back to 1 when the currentPos exceeds the tableSize(array.length)? I changed it a bit and works perfectly. Is there something I'm doing wrong ? Or is it bad code in the book ?

Here's the new method with it's changes.

``````private int findPos(AnyType x)
{
int offset = 1;
int currentPos = myhash(x);

while (array[currentPos] != null && !array[currentPos].element.equals(x))
{
currentPos += offset;
offset += 2;
System.out.println("currentPos: " + currentPos);
if (currentPos >= array.length)
{
currentPos -= array.length;
offset = 1;
}
}
return currentPos;
}``````

Any help would be appreciated! :)

Bound it to the size of the table using modulus. Then you won't go out of bounds on the array. hash value % table size

Thanks! But what exactly do you mean ? What should I bound the table size using modulus ?

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.