Open Addressing

Open addressing: the colliding item is placed in a different cell of the table, each table cell inspected is referred to as a “probe”. Colliding items lump together, causing future collisions to cause a longer sequence of probes. There are three different ways we can handle this:

• 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$

  Link to original

• Double Hashing

  Double Hashing: we use a secondary hash function $h^{\prime }(k)$. If $h$ maps some key $k$ to a cell $A[i]$ with $i=h(k)$, that is already occupied, then we iteratively try the buckets:

  $$A[(i+f(j))\text{ mod }N]\text{ for }j=1,2,\dots ,N-1$$

  Where $f(j)=j\cdot h^{\prime }(k)$.

  The secondary hash function $h^{\prime }(k)$ cannot have zero values. The table size $N$ must be prime to allow probing of all of the cells.

  A common choice of compression function for the secondary hash function:

  $$h^{\prime }(k)=q-k\text{ mod }q$$

  Where $q<N$ and $q$ is prime.

  Link to original

• Quadratic Hashing: (not incl., p.396, individual study)