課題

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

package LinearProbingHash;

sub search{
    my $this = shift;
    my $key = shift;
    foreach(keys %{$this->{_data}}){
        $this->{_count}++;
        if($_ eq $key){
            last;#終了
        }
    }
    return $this->{_data}->{$key};
}

コンストラクタとかは省略。keys %{$this->{_data}}というのがミソで、わざわざ線形探索を行うための工夫である。普段からこんなスクリプト書くやつがいたら、俺は殴る。
とりあえず、線形探索を使って行った場合の比較回数の理論値を出そう。
調べるkeyが、Hashの中に存在している場合は、nをHashのサイズとすればn/2である。また、Hashの中に存在していない場合はnである。従って、Hashの中に存在している確率をpと置くと、p(n/2) + (1-p)nである。一応計算すると、n(1-p/2)が期待値となる。
分散も調べてみよう・・・と思ったが、面倒なのでプログラムに計算させることにする。

my $e = $n * (1 - $p /2);
my $v = 0;
for($i = 1; $i <= $n; $i++){
    $v += ( ($e - $i) * ($e - $i) ) / ($n * $p);
}
$v += ( ($p * $n / 2) * ($p * $n / 2) ) * (1 - $p);

で、完成したわけですが、それは公開しません。