How do i program a Double hash implementation meant for strings?

Question

Hello everyone first time here but i'd like to start by first asking if my understanding of double hashing is correct.

Double hashing works by first implementing a hash function then checking to see if that spot is open. if the current spot is not open then using a second hash function determine another spot and then multiply it by the current attempt and then add it to the index spot that was determined by the first hashing algorithm.

the current code i'd have is:

unsigned int findPos(hashedObj& x)
{
    int offset = 1;
    int iteration = 0;
    unsigned int originalPos = myhash1( x );
    unsigned int index = originalPos;
    unsigned int secondPos = myhash2( x );
    while( array[ index ].info != EMPTY && array[ index ].element != x )
    {
        iteration = offset++ * secondPos;
        if ( ( originalPos + iteration ) > array.size( ) )
            index = ( originalPos + iteration ) % array.size( );
        else
            index = originalPos + iteration;
    }
    return ( index );
}

unsigned int hash1( const string& key, const int Tsize )
{
    //start the hashvalue at 0
    unsigned int hashVal = 0;

    //cout<<" the size of the table is: "<< Tsize <<endl;

    //add the ascii value for every word to hashval, multiply by 37 each time
    for ( int i = 0; i < key.length(); i++ )
        hashVal = 37 * hashVal + key[ i ];
    //mod hashval so it remains smaller than the table size
    hashVal %= Tsize;

    //return the itemes index value
    return hashVal;
}

i just realized i didnt include my second hash function

unsigned int hash2( const string& key, const int Tsize )
{
//store the sum of ascii numerical values
int hashVal = 0;

//add the values of all chars while multiplying each one with a prime number
for ( int i = 0; i < key.length(); i++ )
    hashVal = 29 * hashVal + key[ i ];

//mod the hashed value with a prime smaller than the table size, subtract that number
//with the prime just used and return that value
unsigned int index = 44497 - ( hashVal % 44497 );

return index;
}

it may not look like it but in the real deal tsize is being called correctly.

Answer 1

Your if statement is incorrect:

if ( ( originalPos + iteration ) > array.size( ) )
    index = ( originalPos + iteration ) % array.size( );
else
    index = originalPos + iteration;
}

Should be:

if ( ( originalPos + iteration ) >= array.size( ) )
    index = ( originalPos + iteration ) % array.size( );
else
    index = originalPos + iteration;
}

or better yet, since you're wasting more than the % op by doing the if, and the answer is the same regardless, you can just get rid of the if altogether:

index = ( originalPos + iteration ) % array.size( );

Answer 2

Or you could completely simplify it by saying

unsigned int hashkey = myhash1( x );
unsigned int stepSz = myhash2( x );
while( array[ index ].info != EMPTY && array[ index ].element != x )
        hashKey = (hashKey + stepSz) % capacity;
return hashkey;

Which accomplishes the same thing while making the while loop a lot smaller (and getting rid of the extra variable). I'm assuming you don't want to allow duplicates (hence the second condition in the while loop?).