Section 3 - Implementing Quadratic Probing

6B.3.1 Class Prototype and Constructor

We have already seen the class HashEntry, which is prototyped, but not shown, inside the new class FHhashQP prototype, below:

template <class Object>
class FHhashQP
{
protected:
   static const int INIT_TABLE_SIZE = 7;
   static const float INIT_MAX_LAMBDA;

   enum ElementState { ACTIVE, EMPTY, DELETED };
   class HashEntry;

   FHvector<HashEntry> mArray;
   int mSize;
   int mLoadSize;
   int mTableSize;
   float mMaxLambda;

public:
   FHhashQP(int tableSize = INIT_TABLE_SIZE);
   bool contains(const Object & x) const;
   void makeEmpty();
   bool insert(const Object & x);
   bool remove(const Object & x);
   static long nextPrime(long n);
   int size() const { return mSize; }
   bool setMaxLambda( float lm ); 

protected:
   void rehash();
   int myHash(const Object & x) const;
   int findPos( const Object & x ) const;
};

Here is the constructor:

template <class Object>
FHhashQP<Object>::FHhashQP(int tableSize) : mSize(0)
{
   if (tableSize < INIT_TABLE_SIZE)
      mTableSize = INIT_TABLE_SIZE;
   else
      mTableSize = nextPrime(tableSize);
   mArray.resize(mTableSize);
   makeEmpty();
   mMaxLambda = INIT_MAX_LAMBDA;
}

and makeEmpty():

template <class Object>
void FHhashQP<Object>::makeEmpty()
{
   int k, size = mArray.size();

   for(k = 0; k < size; k++)
      mArray[k].state = EMPTY;
   mSize = mLoadSize = 0;
}

6B.3.2 contains(), insert() and remove()

These three are very easy now that we have studied findPos(). contains() has only one line.

template <class Object>
bool FHhashQP<Object>::contains(const Object & x) const
{
   return mArray[findPos(x)].state == ACTIVE;
}

Because of lazy deletion, remove() isn't much longer:

template <class Object>
bool FHhashQP<Object>::remove(const Object & x)
{
   int bucket = findPos(x);

   if ( mArray[bucket].state != ACTIVE )
      return false;

   mArray[bucket].state = DELETED;
   mSize--;    // mLoadSize not dec'd: it counts non-EMP locs
   return true;
}

And insertion is also easy - we must always check the load factor after we insert, because that added element may push the load factor over the limit, necessitating a rehash:

template <class Object>
bool FHhashQP<Object>::insert(const Object & x)
{
   int bucket = findPos(x);

   if ( mArray[bucket].state == ACTIVE )
      return false;

   mArray[bucket].data = x;
   mArray[bucket].state = ACTIVE;

   // check load factor
   if( ++mLoadSize > mMaxLambda * mTableSize )
      rehash();

   return true;
}

6B.3.3 reHash()

Compare with the FHhashSC. You'll find they are analogous. Since we are using simpler data structures (a single vector), it is easier here:

template <class Object>
void FHhashQP<Object>::rehash()
{
   FHvector<HashEntry> oldArray = mArray;
   int k, oldTableSize = mTableSize;

   mTableSize = nextPrime(2*oldTableSize);
   mArray.resize( mTableSize );
   for(k = 0; k < mTableSize; k++)
      mArray[k].state = EMPTY;

   mSize = mLoadSize = 0;
   for(k = 0; k < oldTableSize; k++)
      if (oldArray[k].state == ACTIVE)
         insert( oldArray[k].data );
}

6B.3.4 Client

You can test out the quadratic probing hash template by using the client from the earlier separate chaining hash main(). Replace the string "SC" everywhere with "QP", and you will be #including the FHhashQP.h header file and using its template class. The output should be identical.