>k番目に使われたエントリのハッシュが
>既に使われている確率をPkとして

大変申し訳ありませんがもう少し詳しく説明して
頂けないでしょうか？

>ハッシュ関数の値域の大きさをN
Nはデータ数だと考えればよいでしょうか？

「ハッシュ関数の検索はO(1)で出来る」と言われたのですが
これは本当なのでしょうか？データ数がNであれば、最悪N回
ハッシュ関数で計算をしなければならないので、O(N/2)くらい
だと思っているのですが間違いでしょうか？