調べるkeyが、Hashの中に存在している場合は、nをHashのサイズとすればn/2である、と上で書いたが、それは違った。(1 + n) / 2であった。 従って、期待値は少々上昇し、n(1 - p/2) + p/2となる。実際にやってみた結果が少し多めだったので気が付いた。

線形探索を用いたHashを実装してみた。わざわざ効率の悪い実装をするなんて、なんという無駄な作業だ・・・ とりあえず5分くらいでPerlを使ってLinearProbingHashを実装した。っていうか、Perlの場合は、標準でもっと効率のいいHashを持ってるのに、それを無…