我正在尝试编辑我的哈希表以形成双重哈希类,但似乎无法正确完成。
我想知道是否有人有任何见解。有人告诉我,我需要做的就是编辑 findPos(),我现在必须在其中使用新策略提供新探针。
**我做了一些研究,它说在双重探测中你会使用 R-(x mod R),其中 R >size 和一个小于表大小的素数。那么我是否要创建一个新的 rehash 函数?
这是我的代码:
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( );
}
};
最佳答案
我不确定是否理解您的代码,但让我提出一些意见,它们不应被视为答案,但它们的大小大于允许评论的大小。
- 如果您使用二次探测,那么我认为在方法
findPos()
中您应该将currentPos
提前为currentPos*currentPos % array.size( )
。目前,正如我所见,您将currentPos
增加一个单位(offset
最初为 1),在 2 个单位之后,在 4 个单位之后等等 - 您可能正在尝试一种快速计算二次探针的方法。如果是这种情况,那么
offset
不应增加二,而应乘以二。这将是offset *= 2
,但是因为您应该计算碰撞次数,所以您应该增加offset
。 也许更简单的方法是:
currentPos += 2*offset++ - 1;//进行二次解析的快速方法
您的调整大小是可以的,因为它保证表至少有一半是空的,因此保证在执行插入时搜索可用条目。
祝你好运
关于c++ - 双探测哈希表,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/33189714/