• Number of Probes (P) - time it takes to find an item.

  Insert 16, 28, 49, 68, 62

    H(16) = 5
    H(28) = 6
    H(49) = 5
    H(68) = 2
    H(62) = 7
  

  

  What is P(68)? P(5)? P(62)?

• Knuth has estimated the average search time for items that are in the table to be:

      alpha = (number of active records)/ (table size)
      (density factor)
  
      avg. no. probes = (1/2) (1 + 1/(1 - alpha))
  

• Knuth has estimated the average search time for items that are NOT in the table to be:

      alpha = (number of active records)/ (table size)
      (density factor)
  
      avg. no. probes = (1/2) (1 + 1/(1 - alpha)^2)
  

• Who is Knuth? Turing Award Winner 1974

  Wrote "Art of Computer Programming Vol. 1-3"

  Most widely referenced CS book!

• Example: 4100 active records

  Remember Binary search - 12 probes

  Prime Tablesize	alpha	success avg. no. probes	no success avg. no. probes
  10000	.41	1.3	1.93
  7000	.58	1.7	3.41
  5000	.82	3.27	15.93
  4500	.91	6.12	62.23
  4200	.97	21.5	868.55

• Main point - the more dense the table, the more probes needed!

• When do we stop a search?

• Problem: Clustering

• What if we allow deletions?