Linear Probing

Linear Probing: handles collisions by placing the colliding item in the next (circularly) available table cell. If we try to insert a key $(k,v)$ into a cell $i$ that is already occupied, we try again at $(i+1)\mathrm{mod}N$ (and repeat until we find an empty cell to insert into).

In order to get(k):

• We start at cell $h(k)$
• Probe consecutive locations until one of the following occurs:
  • item with key $k$ is found
  • empty cell is found
  • $N$ cells have been unsuccessfully probed

Example pseudo-code:

def get(k):
	i = h(k)
	p = 0
	repeat:
		c = A[i]
		if c == null:
			return null
		else if c.getKey() == k:
			return c.getValue()
		else:
			i = (i + 1) mod N
			p += 1
	until p == N
	return null

In order to remove(k):

• search for an entry with key $k$
• if such an entry $(k,v)$ is found, replace it with special item “available” and we return element $v$
• else, return $null$

In order to put(k,v):

• throw an exception if the table is full
• start at cell $h(k)$
• probe consecutive cells until:
  • a cell $i$ is found that is either empty or stores “available”
  • or until $N$ cells have been unsuccessfully probed
• we store $(k,v)$ in cell $i$