When building a hash table using linear probing for collision resolution, is the extra term always added to the hash or only when a collision occurs?

Question

I'm building a table, where an attempt to insert a new key into the table when there is a collision follows the sequence { hash(x) + i, where i = 1,2,3, ... }. If I'm building a hash table using linear probing would my Insert() algorithm do something like this:

hashValue = hash(x)
while hashValue is taken in table
  hashValue += 1

where I only add the increment value when there's a collision, or would I add the increment value to the hash right from the start when i = 1 , so something like this:

hashValue = hash(x) + 1
while hashValue is taken in table
  hashValue += 1

Answer 1

As long as you do it consistently, it does not matter. The effect of adding one (or any other constant, for that matter) to hash code has no effect on the composition of the table, except that the bucket numbering would be "shifted off" by a constant "offset". Since bucket numbering is a private matter of your has table, nobody should care.

In essence, a linear probing hash function is

H(x, i) = (H(x) + i) % N

where N is the number of buckets. It is conventional to start i at zero, which means incrementing the value of hash only when you get a collision.

Answer 2

It does not hurt (it simply shifts the probe sequence by one element), but it doesn't have any benefits either, and conceptually it's a bit silly. That's why the canonical form starts at hash(x) and increments only when encountering collisions.