Search with linear probing pseudocode

I came across this pseudocode for finding an element in a hash table using linear probing in my class but no explanation was given on what the variables represent

A is a hash table with N cells and starting point is at cell h(k), want to find element with key 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

can someone explain what does the line i = (i+1) % N do? is it to increase key value, in that case why is p incremented by 1?

Solution

Let's go through the code, commenting what we know, shall we?

Importantly, the % symbol is the modulus operator. a % b returns an integer c between 0 and b-1, where c is the remainder of a divided by b. For example, 15 divided by 12 is 1, with a remainder 3: 15 % 12 = 3. Similarly, 16 divided by 4 is 4, with a remainder 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

So this code looks for the key starting from h(k) and keeps moving forward, looping at the end of the array back to the start, until it's gone through the entire array. At each step, it's looking for a node with key k.

Better names for the variables would have been:

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