时间戳

首页 > 解决方案 > 使用线性探测伪代码进行搜索

data-structures - 使用线性探测伪代码进行搜索

问题描述

我遇到了这个伪代码，用于在我的班级中使用线性探测在哈希表中查找元素，但没有解释变量代表什么

A是一个有N个单元格的哈希表，起点是单元格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？

标签： data-structureshashtable

解决方案

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

重要的是，%符号是模运算符。返回和之间a % b的整数，其中是除以的余数。例如，15 除以 12 为 1，余数为 3 ：。类似地，16 除以 4 为 4，余数为 0 ：。c0b-1cab15 % 12 = 316 % 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)并继续前进，在数组的末尾循环回到开头，直到它遍历整个数组。在每一步，它都在寻找一个带有 key 的节点k。

更好的变量名称应该是：

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

推荐阅读