アルゴリズムイントロダクション Chapter 11

ハッシュテーブル

11.1-4

SmallArray = new Array;

def insert ( x )
   l = SmallArray.length + 1;
   HugeArray[x.key] = (x, l);
   SmallArray[l] = x.key;
   SmallArray.length++;
end

def search ( key )
   (x, l) = HugeArray[key];
   if SmallArray[l] == key
      return x;
   else
      return nil;
end

11.3-5

分母：collisionするペアの最大数。
分子：ペアの数
$\epsilon \;>\; \frac{B\lceil U/B\rceil\left(\lceil U/B\rceil - 1\right)}{U(U-1)} \;>\; \frac{U(U/B-1)}{U^2} \;=\; \frac{1}{B} \,-\, \frac{1}{U}$
これが、ハッシュ関数それぞれについて成り立つから。

11.3-6

二つの違うタプルのハッシュ値が同じになるのは、差を取って0となるとき。つまり、
$\sum_{j} (n^'_j - n_j)b^j = 0$
の時。bの取りうる値はp個で、そのうち最大n-1個が解となる(Exercise 31.4-4)ので、
$\frac{n-1}{p}$
が衝突する確率の上界となる。