c++ - 如何实现哈希表的删除功能？

Question

我有一个使用线性探测的哈希表。我的任务是按照以下准则编写 erase(int key) 函数。

 void erase(int key);

 Preconditions:  key >= 0
 Postconditions: If a record with the specified key exists in the table, then
 that record has been removed; otherwise the table is unchanged.

我还得到了一些完成任务的提示

• 重要的是要认识到插入函数将允许您向表中添加新条目，或更新表中的现有条目。

• 对于线性探测版本，请注意插入一个 项目有两次搜索。 insert() 函数调用函数 findIndex() 搜索表以查看该项目是否已在 table 。如果该项目不在表中，则进行第二次搜索 找到表中插入项目的位置。添加能力 删除一个条目需要插入过程 修改的。搜索现有项目时，请确保 当到达已被占用的位置时，搜索不会停止 但现在是空的，因为该项目已被删除。当搜索一个 插入新项目的位置，使用第一个空位置 - 确实如此 无论该职位是否曾经被占据过。

所以我开始编写删除(key)，我似乎遇到了提示所指的问题，但我不确定它的含义。我将在一秒钟内提供代码，但是我为测试代码所做的工作是设置哈希表，以便它会发生冲突，然后我删除该 key 并重新哈希表，但它不会进入正确的位置。

例如，我在哈希表中添加了一些元素:

The hash table is:
Index  Key    Data
    0   31     3100
    1    1     100
    2    2     200
    3   -1
    4   -1
    5   -1
    6   -1
    7   -1
    8   -1
    9   -1
   10   -1
   11   -1
   12   -1
   13   -1
   14   -1
   15   -1
   16   -1
   17   -1
   18   -1
   19   -1
   20   -1
   21   -1
   22   -1
   23   -1
   24   -1
   25   -1
   26   -1
   27   -1
   28   -1
   29   -1
   30   -1

所以除了前 3 个索引之外，我的所有值都是空的。显然，键 31 应该进入索引 1。但是由于键 1 已经存在，因此它发生冲突并稳定在索引 0 中。然后我删除键 1 并重新散列表，但键 31 仍保留在索引 0 处。

以下是可能值得关注的函数:

void Table::insert( const RecordType& entry )
{
   bool alreadyThere;
   int index;

   assert( entry.key >= 0 );

   findIndex( entry.key, alreadyThere, index );
   if( alreadyThere )
      table[index] = entry;   
   else
   {
      assert( size( ) < CAPACITY );
      index = hash( entry.key );
      while ( table[index].key != -1 )
         index = ( index + 1 ) % CAPACITY;
      table[index] = entry;
      used++;
   }
}

由于插入使用 findIndex，我也会将其包括在内

void Table::findIndex( int key, bool& found, int& i ) const
{
   int count = 0;

   assert( key >=0 );

   i = hash( key );
   while ( count < CAPACITY && table[i].key != -1 && table[i].key != key )
   {
      count++;
      i = (i + 1) % CAPACITY;
   }   
   found = table[i].key == key;
}

这是我当前的删除开始

void Table::erase(int key) 
{
    assert(key >= 0);

    bool found, rehashFound;
    int index, rehashIndex;

    //check if key is in table
    findIndex(key, found, index);

    //if key is found, remove it
    if(found)
    {
        //remove key at position
        table[index].key = -1;
        table[index].data = NULL;
        cout << "Found key and removed it" << endl;
        //reduce the number of used keys
        used--;
        //rehash the table

        for(int i = 0; i < CAPACITY; i++)
        {
            if(table[i].key != -1)
            {
                cout << "Rehashing key : " << table[i].key << endl;
                findIndex(table[i].key, rehashFound, rehashIndex);
                cout << "Rehashed to index : " << rehashIndex << endl;
                table[rehashIndex].key = table[i].key;
                table[rehashIndex].data = table[i].data;
            }
        }
    }
}

有人可以解释我需要做什么才能使其正确重新散列吗？我理解哈希表的概念，但我似乎在这里做错了什么。

编辑

根据用户的建议:

void Table::erase(int key)
{
    assert(key >= 0);
    bool found;
    int index;

    findIndex(key, found, index);

    if(found) 
    {
        table[index].key = -2;
        table[index].data = NULL;
        used--;

    }

}


//modify insert(const RecordType & entry)

while(table[index].key != -1 || table[index].key != -2)


//modify findIndex

while(count < CAPACITY && table[i].key != -1
      && table[i].key != -2 && table[i].key != key)

Answer 1

从表格中删除项目时，不要移动任何东西。只需在那里贴上“已删除”标记即可。在插入中，将删除标记视为空并且可用于新项目。在查找时，将它们视为已占用，并继续探测是否找到一个。调整表格大小时，忽略标记。

请注意，如果从未调整表的大小，这可能会导致问题。如果表从未调整过大小，一段时间后，表中将没有标记为从未使用过的条目，并且查找性能将陷入困境。由于提示提到跟踪是否曾经使用过空位置并将曾经使用过的单元格与从未使用过的单元格区别对待，我相信这是预期的解决方案。据推测，调整表格大小将是稍后的任务。