Поиск с линейным зондированием псевдокода

Question

Я наткнулся на этот псевдокод для поиска элемента в таблице ha sh с использованием линейного зондирования в моем классе, но не было дано никакого объяснения того, что представляют собой переменные

A - таблица ha sh с 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?

Answer 1

Давайте go через код, комментируя то, что мы знаем, не так ли?

Важно, что символ % является оператором модуля. a % b возвращает целое число c между 0 и b-1, где c - остаток от a, деленный на b. Например, 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()