ハッシュテーブルの自動拡張
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/08/22 14:07 UTC 版)
「ハッシュテーブル」の記事における「ハッシュテーブルの自動拡張」の解説
ハッシュテーブルはエントリの数が配列のサイズに近づくほど衝突の確率が高くなり、性能が悪化してしまう。この比率をload factor(座席利用率)と呼び、n/Nの形で表す。nはエントリの数、Nは配列のサイズを指す。 連鎖法の場合はload factorの増加に対して線形に性能が悪化する。しかし開番地法の場合は衝突したキーが配列の空いた番地に格納されるため、load factorが0.8を超える付近で性能が急激に悪化する。 この問題を回避するため、load factorが一定を超えた場合に、より大きいサイズのハッシュテーブルを用意して格納し直す操作が必要となる。これをリハッシュ (rehash) と呼ぶ。この操作はすべての要素のハッシュ値を再計算して新たなハッシュテーブルに格納するためO(n)であるが、配列のサイズを指数的に拡張する事で、動的配列の末尾追加操作と同様に償却解析によって計算量をO(1)とみなす事ができる。 より単純な回避方法として、あらかじめ想定されるエントリの数に対して十分に大きなサイズの配列を用意する方法もあるが、エントリの数を事前に想定できない場合には適用できない。
※この「ハッシュテーブルの自動拡張」の解説は、「ハッシュテーブル」の解説の一部です。
「ハッシュテーブルの自動拡張」を含む「ハッシュテーブル」の記事については、「ハッシュテーブル」の概要を参照ください。
ウィキペディア小見出し辞書の「ハッシュテーブルの自動拡張」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。
お問い合わせ。
- ハッシュテーブルの自動拡張のページへのリンク
