Hashing

λ = the factor of table full

(Subscript[f, u])(λ) = expected number of probes for unsuccessful search

(Subscript[f, s])(λ) = expected number of probes for successful search

(Subscript[f, s])(λ) =(1/λ)(∫_0^λ)(Subscript[f, u])(x)\[DifferentialD]x 
or (for separate chaining) = (1/λ)(∫_0^λ)(1+(Subscript[f, u])(x))\[DifferentialD]x
Comment: 1 in the above formula is the cost of retireving the list from the hash table.

Example (Subscript[f, s])(λ)=(λ^2)

Plot[{(λ^2),(1/λ)(∫_0^λ)(x^2)\[DifferentialD]x},{λ,0.0001,1},PlotTheme->"Classic"]

Linear probing

Expected number of probes for unsuccessful search:

Ending up in an empty cluster:

1

Ending up in a non-empty cluster:

(∑_(i=1)^∞)i×(λ^(i-1))

Together, on average:

(1/2)(1+(∑_(i=1)^∞)i×(λ^(i-1)))

Expected number of probes for successful search:

(1/λ)(∫_0^λ)(1/2)(1+((((1/(1-x))))^2))\[DifferentialD]x

ConditionalExpression[((-2+λ)/(2 (-1+λ))),Re[λ]≤1||λ∉Reals]

((-2+λ)/(2 (-1+λ)))==(1/2)(1+((1/(1-λ))))

Simplify[(1/2)(1+((1/(1-λ))))]

Plot[{(1/2)(1+((((1/(1-λ))))^2)),(1/2)(1+((1/(1-λ))))},{λ,0,.999}]

Double hashing

These derivations are based under (somewhat unrealistic) assumption that all consecutive probes are statistically independent.

Expected number of probes for unsuccessful search:

(1/(1-λ))

Same as:

(∑_(i=1)^∞)i×((λ^(i-1))-(λ^i))

Explanation:
If (λ^n) is the probability of making alt least n+1 trials then (λ^(i-1))-(λ^i)is the probability of making exactly i trials.

Same as:

(∑_(i=0)^∞)(λ^i)

Same as:

(∑_(i=1)^∞)i×(λ^(i-1))×(1-λ)

Explanation:
1 probe with probability of 1-λ (hit an empy slot at the first trial)
2 probes wih probability λ×(1-λ)(hit an occupied slot at the first trial and an empty slot at the second trial)

3 probes wih probability (λ^2)×(1-λ)(hit an occupied slot at the first 2 trials and an empty slot at the third trial)
...
i probes wih probability (λ^(i-1))×(1-λ)(hit an occupied slot at the first i-1 trials and an empty slot at the i-th trial)
Hence the term i×(λ^(i-1))×(1-λ) in the above summation.

Expected number of probes for successful search:

(1/λ)(∫_0^λ)(1/(1-x))\[DifferentialD]x

Expand[-((Log[1-λ])/λ)]

Plot[{(1/(1-λ)),(1/λ)Log[(1/(1-λ))]},{λ,0,.999}]

All four cases (linear probing and double hashing):

Plot[Tooltip[{(1/2)(1+((((1/(1-λ))))^2)),(1/2)(1+((1/(1-λ)))),(1/(1-λ)),(1/λ)Log[(1/(1-λ))]}],{λ,0,.999}]

Separate chaining

Expected number of probes for unsuccessful search:

λ

Explanation: 
λ is the average length of a list since there are B lists with a total of λB elements in them.

Expected number of probes for successful search:

(1/λ)(∫_0^λ)(1+x)\[DifferentialD]x

Simplify[%]

Expand[%]

Plot[{λ,1+(λ/2)},{λ,0,10}]