双哈希函数在 C++ 中是如何工作的?
How the Double Hash Function Works in C++?
我正在阅读有关 HashTable 的内容,并找到了一个易于理解的好资源 Here.
但是我对双重哈希函数感到困惑。这是双重哈希函数的详细信息。
Double hashing uses the idea of applying a second hash function to the
key when a collision occurs. The result of the second hash function
will be the number of positions form the point of collision to insert.
There are a couple of requirements for the second function:
it must never evaluate to 0
must make sure that all cells can be probed
A popular second hash function is: Hash2(key) = R - ( key % R ) where
R is a prime number that is smaller than the size of the table.
这里是双哈希函数的图像。
现在开始混乱了。正如他们在形象中所说的那样。 49 应该位于 [9]
索引的 7
位置。那么实际位置将是 [6]
那么为什么他们将 49 放在 [0]
索引处?其他剩余整数也一样。
当没有空索引时会发生什么?
图像有误,可能会采用不同的哈希方法。
当没有空单元格时,您将不得不重新哈希。请参阅双重哈希部分下方的 "Hashing with Rehashing" 部分。
图像确实错误。基本思路是根据second给定的值跳转到第no个有函数的地方,如果已经被占用,则继续跳相同的第no个。的地方,直到找到一个空单元格。为此,第二个哈希函数不能 return 0.
更多解释请看here。
我正在阅读有关 HashTable 的内容,并找到了一个易于理解的好资源 Here.
但是我对双重哈希函数感到困惑。这是双重哈希函数的详细信息。
Double hashing uses the idea of applying a second hash function to the key when a collision occurs. The result of the second hash function will be the number of positions form the point of collision to insert.
There are a couple of requirements for the second function:
it must never evaluate to 0 must make sure that all cells can be probed
A popular second hash function is: Hash2(key) = R - ( key % R ) where R is a prime number that is smaller than the size of the table.
这里是双哈希函数的图像。
现在开始混乱了。正如他们在形象中所说的那样。 49 应该位于 [9]
索引的 7
位置。那么实际位置将是 [6]
那么为什么他们将 49 放在 [0]
索引处?其他剩余整数也一样。
当没有空索引时会发生什么?
图像有误,可能会采用不同的哈希方法。
当没有空单元格时,您将不得不重新哈希。请参阅双重哈希部分下方的 "Hashing with Rehashing" 部分。
图像确实错误。基本思路是根据second给定的值跳转到第no个有函数的地方,如果已经被占用,则继续跳相同的第no个。的地方,直到找到一个空单元格。为此,第二个哈希函数不能 return 0.
更多解释请看here。