为了搜索我想从哈希表中删除的每个“符号”,我选择生成我插入它的哈希键。但是,我在删除函数中看到的问题是,当我需要从发现碰撞的位置删除一个符号时,它以前会导致我的 while 循环条件在我不想要的地方测试 false。
bool hashmap::get(char const * const symbol, stock& s) const
{
int hash = this->hashStr( symbol );
while ( hashTable[hash].m_symbol != NULL )
{ // try to find a match for the stock associated with the symbol.
if ( strcmp( hashTable[hash].m_symbol , symbol ) == 0 )
{
s = &hashTable[hash];
return true;
}
++hash %= maxSize;
}
return false;
}
bool hashmap::put(const stock& s, int& usedIndex, int& hashIndex, int& symbolHash)
{
hashIndex = this->hashStr( s.m_symbol ); // Get remainder, Insert at that index.
symbolHash = (int&)s.m_symbol;
usedIndex = hashIndex;
while ( hashTable[hashIndex].m_symbol != NULL ) // collision found
{
++usedIndex %= maxSize; // if necessary wrap index around
if ( hashTable[usedIndex].m_symbol == NULL )
{
hashTable[usedIndex] = s;
return true;
}
else if ( strcmp( hashTable[usedIndex].m_symbol , s.m_symbol ) == 0 )
{
return false; // prevent duplicate entry
}
}
hashTable[hashIndex] = s; // insert if no collision
return true;
}
// What if I need to remove an index i generate?
bool hashmap::remove(char const * const symbol)
{
int hashVal = this->hashStr( symbol );
while ( hashTable[hashVal].m_symbol != NULL )
{
if ( strcmp( hashTable[hashVal].m_symbol, symbol ) == 0 )
{
stock temp = hashTable[hashVal]; // we cansave it
hashTable[hashVal].m_symbol = NULL;
return true;
}
++hashVal %= maxSize; // wrap around if needed
} // go to the next cell meaning their was a previous collision
return false;
}
int hashmap::hashStr(char const * const str)
{
size_t length = strlen( str );
int hash = 0;
for ( unsigned i = 0; i < length; i++ )
{
hash = 31 * hash + str[i];
}
return hash % maxSize;
}
我需要做什么才能从我的 hashTable 中删除之前冲突的“符号”? 我希望它不是直接在上面的 java 方程式。
最佳答案
看起来您正在实现一个具有开放寻址的哈希表,对吗?在该方案中删除有点棘手。参见 http://www.maths.lse.ac.uk/Courses/MA407/del-hash.pdf :
“删除 key 对于开放寻址是有问题的:如果有两个冲突的 key x 和 y 且 h(x) = h(y),并且 key x 插入到 key y 之前,并且有人想删除 key x,这不能简单地通过将 T[h(x)] 标记为 FREE 来完成,因为那样 y 将不再被发现。一种可能性是将 T[h(x)] 标记为 DELETED(另一个特殊条目),它被跳过当搜索一个键时。标记为 DELETED 的表位置也可以重新用于存储另一个键 z,如果确定该键 z 不在表中(即到达键 z 的探测序列,但没有找到它)。这种重用使插入方法复杂化。此外,具有 DELETED 键的位置会填满表格。”
关于c++ - 删除 C++ 时哈希键冲突,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/1569915/