基本情報技術者試験「ハッシュ表の負荷率」の問題
スロット数が500のハッシュ表に、現在350個のデータが格納されている。このハッシュ表の負荷率(占有率)はいくらか。
ア負荷率は約1.43
イおよそ0.35
ウ0.7
エおおよそ0.5付近
正解
ウ．0.7
ハッシュ表の負荷率はα=格納データ数÷スロット数で定義される。350÷500=0.7となり、表の7割が埋まっている状態を表すため正しい。
?選択肢ごとの解説
ア ×約1.43は500÷350であり、分子と分母を逆に取ったため負荷率が1を超えてしまった誤りである。チェイン法でない限り占有率は1以下になる。
イ ×およそ0.35は350を1000で割るなど分母を取り違えた誤りで、分母は実際のスロット数500とすべきである。
ウ ○ハッシュ表の負荷率はα=格納データ数÷スロット数で定義される。350÷500=0.7となり、表の7割が埋まっている状態を表すため正しい。
エ ×おおよそ0.5付近はスロット数を増減して見積もるなどの概算ミスであり、正確には350÷500=0.7である。
✎くわしく
負荷率はハッシュ表の混み具合を示し、値が大きいほど衝突が増えて探索効率が落ちる。オープンアドレス法では負荷率が1に近づくと急激に性能が悪化するため、一定値(例:0.7前後)を超えるとリハッシュで拡張する設計が一般的である。定義の分子分母を間違えないことが核心である。
✓本番での押さえどころ
試験のコツ
負荷率=『中身÷器』=格納数÷スロット数、と分子分母を固定する。1を超える答え(オープンアドレス法)は逆算ミスを疑う。
覚え方
負荷率は『容器の埋まり具合』。350個を500席に入れたら7割埋まる=0.7、と席の埋まりでイメージする。
よくある誤り
分子と分母を逆にして1を超える値を出す、または分母に総スロットでなく別の数を使う誤りが多い。
アルゴリズムとプログラミングの他の問題
次の擬似言語で表される手続 sumOdd を、引数として要素数 5 の整数型の配列 {12, 125, 1008,…次の擬似言語は、整数型の配列 arr に対して隣接交換を行う手続の一部であり、外側ループの 1 回目（1…次の擬似言語は昇順に整列された配列 arr に対する二分探索の手続である。arr = {2, 4, 6, 8, 10,…次の擬似言語で表される再帰手続 f を、引数 n = 20 で呼び出したとき、戻り値として返される値はどれか。
```…単方向連結リストの各ノードはメンバ val（整数）と next（次ノードへの参照。なければ NULL）をもつ。先頭ノード…スタックに対する push（積む）と…
この問題を、AIの8-ways解説つきで。
無料ではじめる →基本情報技術者試験の演習を、一問ごとに「なぜ」まで。まずは無料で。
ukamiru 過去問 · 基本情報技術者試験 · fe-a3-0131