red ketchum - 1 year ago 67

C++ 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 Source

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( );
```