Квадратичное зондирование

Эй, ребята, у меня есть небольшое задание по анализу квадратичного зондирования. Я надеялся, что кто-нибудь сможет объяснить мне, что мне нужно сделать. Не очень хорошо понимаю концепцию, и в книге просто есть параграф. Мне дали этот код ниже и сказали:

Внедрить квадратичное зондирование, а затем запустить тесты на количество зондов
требуется при различных коэффициентах нагрузки для получения графика, подобного показанному
на рисунке 5.12. Для простоты можно предположить, что
хранятся целые числа, и что никогда не будет более 1000
они хранятся в любое время. Не перефразировать.

график можно увидеть на http://orion.lcg.ufrj.br/Dr.Dobbs/books/book3/chap5.htm

Может кто-нибудь объяснить мне, что значит запустить тест на количество зондов …
Спасибо за любую помощь

int nextPrime( int n );

// QuadraticProbing Hash table class
//
// CONSTRUCTION: an approximate initial size or default of 101
//
// ******************PUBLIC OPERATIONS*********************
// bool insert( x )       --> Insert x
// bool remove( x )       --> Remove x
// bool contains( x )     --> Return true if x is present
// void makeEmpty( )      --> Remove all items
// int hashCode( string str ) --> Global method to hash strings

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;

array[ currentPos ].element = x;
array[ currentPos ].info = ACTIVE;

// Rehash; see Section 5.5
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;

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

#endif

0

Решение

Задача ещё не решена.

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


По вопросам рекламы [email protected]