double probe hash table

Question

I am trying to edit my hash table to form a double hashing class but can't seem to get it right.

I was wondering if anyone had any insight. I was told that all I needed to do was edit the findPos() where I now have to provide new probes using a new strategy.

**I did some research and it says in double probing you would use R-(x mod R) where R >size and a prime smaller than the table size. So do I make a new rehash function?

here is my code:

template <typename HashedObj>
class HashTable
{
  public:
    explicit HashTable( int size = 101 ) : array( nextPrime( size ) )
      { makeEmpty( ); }

    bool contains( const HashedObj & x ) const
    {
        return isActive( findPos( x ) );
    }

    void makeEmpty( )
    {
        currentSize = 0;
        for( auto & entry : array )
            entry.info = EMPTY;
    }

    bool insert( const HashedObj & x )
    {
            // Insert x as active
        int currentPos = findPos( x );
        if( isActive( currentPos ) )
            return false;

        if( array[ currentPos ].info != DELETED )
            ++currentSize;

        array[ currentPos ].element = x;
        array[ currentPos ].info = ACTIVE;
            // Rehash; 
        if( currentSize > array.size( ) / 2 )
            rehash( );
        return true;
    }

    bool insert( HashedObj && x )
    {
            // Insert x as active
        int currentPos = findPos( x );
        if( isActive( currentPos ) )
            return false;

        if( array[ currentPos ].info != DELETED )
            ++currentSize;

        array[ currentPos ] = std::move( x );
        array[ currentPos ].info = ACTIVE;

            // Rehash; see Section 5.5
        if( currentSize > array.size( ) / 2 )
            rehash( );

        return true;
    }

    bool remove( const HashedObj & x )
    {
        int currentPos = findPos( x );
        if( !isActive( currentPos ) )
            return false;

        array[ currentPos ].info = DELETED;
        return true;
    }

    enum EntryType { ACTIVE, EMPTY, DELETED };

  private:
    struct HashEntry
    {
        HashedObj element;
        EntryType info;

        HashEntry( const HashedObj & e = HashedObj{ }, EntryType i = EMPTY )
          : element{ e }, info{ i } { }

        HashEntry( HashedObj && e, EntryType i = EMPTY )
          : element{ std::move( e ) }, info{ i } { }
    };

    vector<HashEntry> array;
    int currentSize;

    bool isActive( int currentPos ) const
      { return array[ currentPos ].info == ACTIVE; }

    int findPos( const HashedObj & x ) const
    {
        int offset = 1;
        int currentPos = myhash( x );

        while( array[ currentPos ].info != EMPTY &&
               array[ currentPos ].element != x )
        {
            currentPos += offset;  // Compute ith probe
            offset += 2;
            if( currentPos >= array.size( ) )
                currentPos -= array.size( );
        }

        return currentPos;
    }

    void rehash( )
    {
        vector<HashEntry> oldArray = array;

            // Create new double-sized, empty table
        array.resize( nextPrime( 2 * oldArray.size( ) ) );
        for( auto & entry : array )
            entry.info = EMPTY;

            // Copy table over
        currentSize = 0;
        for( auto & entry : oldArray )
            if( entry.info == ACTIVE )
                insert( std::move( entry.element ) );
    }

    size_t myhash( const HashedObj & x ) const
    {
        static hash<HashedObj> hf;
        return hf( x ) % array.size( );
    }
};

Answer 1

It appears that you want to implement double hashing for probing. This is a technique for resolving collisions by using a second hash of the input key. In the original quadratic function, you continually add an increasing offset to the index value until you find an empty spot in the hash table. The only important difference in a double hashing function would be the value of the offset.

If I were you, I would create a new hash function which is similar to the first one, but I would replace the return statement with return R - ( hf(x) % R ); for a provided R value. Then I would change findPos to set offset equal to this second hash function (Also remember to remove the offset += 2; line because the offset is no longer increasing).

Answer 2

I am not sure of understanding your code, but let me pose some observations that they should not be considered as an answer, but their size is greater that what is allowed to comment.

1. If you use quadratic probing, then I think in the method findPos() you should advance currentPos in some as currentPos*currentPos % array.size(). Currently, as I see, you increase currentPos in one unity (offset is initially 1), after 2 unities, after 4 and so on
2. Probably you are trying a fast way for compute the quadratic probe. If this is the case, then offset should not be increased by two, but multiplied by two. That would be some as offset *= 2, but because you should count the number of collisions you should increase offset.

3. Maybe a simpler way would be:

   currentPos += 2*offset++ - 1; // fast way of doing quadratic resolution

Your resizing is ok, given that it guarantees that the table will be at least half empty and consequently the search of availables entries when the insertion is executed is guaranteed.

Good luck