使用线性探测伪代码搜索

Question

我在我的 class 中遇到了使用线性探测在散列 table 中查找元素的伪代码，但没有给出变量代表什么的解释

A 是一个包含 N 个单元格的散列 table，起点在单元格 h(k) 处，想要找到键为 k

的元素

findElement(k)
   i = h(k)
   p = 0
   repeat
      c = A[i]
      if c == null
         return NO_SUCH_KEY
      else if c.key() == k
         return c.element()
      else
         i = (i+1) % N
         p = p+1
   until p == N
   return NO_SUCH_KEY

谁能解释一下 i = (i+1) % N 行的作用？是增加键值，那为什么p加1？

Answer 1

让我们浏览一下代码，评论我们所知道的，好吗？

重要的是，% 符号是取模运算符。 a % b returns 介于 0 和 b-1 之间的整数 c，其中 c 是 a 除以 [=19 的余数=].例如，15 除以 12 为 1，余数为 3：15 % 12 = 3。同样，16 除以 4 为 4，余数为 0：16 % 4 = 0.

findElement(k)

   // Assuming h() is a hashing function, i will be the hash of k.
   i = h(k)

   // We're unsure of p's purpose yet, it's probably a loop counter.
   p = 0
   repeat

      // c is the value at position i, which is the hash of k.
      // so c is a candidate for being the element for key k.
      c = A[i]

      // If there's nothing at A[i], then stop.
      if c == null
         return NO_SUCH_KEY

      // If c's key is k, then we've found the right node, return it.
      else if c.key() == k
         return c.element()

      // If there's something at A[i], but it's not for k, then there was a hash collision.
      else

         // Find the next index
         // In this case, we're just looking at the next integer from our starting point,
         // modulus N (the size of the node array).
         i = (i+1) % N

         // Increment the loop counter
         p = p+1

   // If we've been through the whole structure, stop and return NO_SUCH_KEY.
   until p == N
   return NO_SUCH_KEY

所以这段代码从 h(k) 开始寻找键并一直向前移动，在数组的末尾循环回到开头，直到遍历整个数组。在每一步，它都在寻找一个键为 k.

的节点

更好的变量名称应该是：

k: targetKey
i: candidateIndex
p: numElementsVisited
c: currentNode
A: storage
N: sizeOfStorage
h(): calculateHashValue()

使用线性探测伪代码搜索

Search with linear probing pseudocode

hashtable

data-structures