kilrey https://blog.hatena.ne.jp/kilrey/ うっくつさん本を読む。 https://kilrey.hatenadiary.org/ Web 雑記 http://d.hatena.ne.jp/zariganitosh/20090716とhttp://d.hatena.ne.jp/odz/20090718/1247922506の話。 定義域と値域からハッシュ表のサイズを考えてみる。登場人物はハッシュ関数と折り畳み関数の二つ。 ハッシュ関数 例えば、文字列から32ビット整数に変換するハッシュ関数を考えてみよう。文字列の最大長をNとすると2^(8*N)程度の極めて巨大な定義域を持つ。値域は2^32である。 理想的なハッシュ関数は適当な入力に対して値域全体に均等に分布した結果を返す。この分布の均等さをエントロピーとして表現すると比較しやすい。 折… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkilrey.hatenadiary.org%2Fentry%2F20090718%2Fp1" title="ハッシュ表のサイズ - うっくつさん本を読む。" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-07-18 00:00:00 rich https://kilrey.hatenadiary.org/entry/20090718/p1 1.0 100%