Как мне запрограммировать реализацию двойного хеша для строк?

Question

Как мне запрограммировать реализацию двойного хеша для строк?

Привет всем здесь впервые, но я хотел бы начать с того, чтобы сначала спросить, верно ли мое понимание двойного хеширования.

Двойное хеширование работает, сначала реализуя хеш-функцию, а затем проверяя, открыто ли это место. если текущая точка не открыта, то с помощью второй хэш-функции определите другую точку и затем умножьте ее на текущую попытку, а затем добавьте ее к области индекса, определенной первым алгоритмом хеширования.

текущий код у меня есть:

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;
}

я только что понял, что не включил мою вторую хэш-функцию

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;
}

это может выглядеть не так, но в реальной ситуации tsize вызывается правильно.

1

c++double-hashing string-hashing

Решение

Другие решения

Или вы могли бы полностью упростить это, сказав

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;

Который выполняет то же самое, делая цикл while намного меньше (и избавляясь от дополнительной переменной). Я предполагаю, что вы не хотите разрешать дубликаты (следовательно, второе условие в цикле while?).

0

Источник

Accepted Answer

Ваше заявление if неверно:

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

Должно быть:

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

или, что еще лучше, поскольку вы тратите больше, чем% op, выполняя оператор if, и ответ один и тот же, независимо от этого, вы можете просто полностью избавиться от if:

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

0