• Average number of probes (item in table)

     -(1/alpha) * log_e (1-alpha)
  

• Average number of probes (item NOT in table)

     1/(1 - alpha)
  

• Example: 4100 Active records

  remember: Binary search takes 12 probes

  Prime Tablesize	alpha	success avg. no. probes	no success avg. no. probes	linear success
  10000	.41	1.28	1.69	1.3
  7000	.58	1.49	2.38	1.7
  5000	.82	2.09	5.55	3.27
  4500	.91	2.64	11.11	6.12
  4200	.97	3.61	33.33	21.5

• Advantages - Avoids clustering

• Disadvantages - May not cover every entry in table

• Example: Table size 8, if hash address is 4, then retry are 4, 5, 8

• Radke's Method: Table size prime number equal to 4M+3, then

  • half the slots probed using: K, K+1^2, K+2^2, K+3^2, etc

  • half the slots probed using: K-1^2, K-2^2, K-3^2, etc.

• What if we allow deletions for the quadratic method?