BUILD YOUR UNDERSTANDING
情報処理技術者試験の用語集
言葉の意味を確かめて、問題への理解を一歩深めましょう。
ハッシュ表
キーから格納場所を求める
ハッシュ表は、キーにハッシュ関数を適用して格納場所の候補を求め、対応する値を保存・検索するデータ構造です。社員番号から社員情報を取り出す辞書のような用途に使います。条件が適切なら平均的に少ない手順で探索できますが、異なるキーが同じ場所へ対応する衝突を扱う必要があります。
小さな例
格納場所が七個あり、キーを7で割った余りを場所とする方法を考えます。10と17はどちらも余り3なので、同じ場所へ入れようとします。元のキーが違う以上、片方を単純に上書きしてはいけません。実際のハッシュ関数はより複雑な場合がありますが、有限の場所へ写す限り、衝突への備えが重要です。
衝突の処理
連鎖法では、同じ場所に対応した要素をリストなどにつなぎます。開番地法では、別の空き位置を決められた規則で探します。削除するときに、後ろへずれた要素の探索経路を壊さない工夫が必要になる場合があります。キーの比較を省いて、ハッシュ値が同じだから同じデータと判断してはいけません。
負荷率と再構成
要素数が格納場所に比べて増えると衝突が多くなり、探索が長くなる場合があります。容量を増やして各要素の位置を計算し直す再ハッシュなどで調整します。この処理には一時的な費用がかかるため、平均的な速さと、ある一回の操作にかかる時間は区別します。最悪時まで常にO(1)と断定するのは正確ではありません。
順序を扱う場合
ハッシュ表は等しいキーを探すのに向きますが、大小順の範囲検索をそのまま効率よく行う構造とは限りません。順序を保持する実装もありますが、基本のハッシュ計算だけから順序が保証されるわけではありません。試験では、衝突、負荷率、再ハッシュ、範囲検索の違いを整理します。暗号学的ハッシュの改ざん検出などの用途と、探索用のハッシュ表という用途も分けて理解しましょう。
キーを変更すると対応する位置も変わり得るため、保存中のキーを勝手に書き換えない設計が必要です。検索と登録で同じ比較規則を使うことも確認します。
参考資料
内容確認日:2026-11-13
この用語に関連する問題
1問用語一覧
10件パーミッション・マーケティング
パーミッション・マーケティング とは、パーミッション(permition)は、日本語で 許可。 この事から、お客様より許可をとった上で行うマーケティング手法にな...
バイラルマーケティング
バイラル・マーケティングとは、 英語表記では Viral marketing . バイラルとは、「ウィルス性の」という意味であり、口コミなどでウィルスのように繁殖して広...
バックアップ
復元のために別の状態を保存する バックアップは、障害や誤操作などで失われたデータを戻せるよう、別の保存先や世代にデータを保管することです。現在のデータ...
ハッシュ表
キーから格納場所を求める ハッシュ表は、キーにハッシュ関数を適用して格納場所の候補を求め、対応する値を保存・検索するデータ構造です。社員番号から社員情...
ハッシュ関数
意味と用途 ハッシュ関数は、入力データから一定の規則で値を計算する関数です。暗号の分野では、任意の長さのデータから固定長のハッシュ値を得る仕組みがよく...
バッファオーバーフロー
確保した領域を越えて書き込む バッファオーバーフローは、データを一時的に置くためのメモリー領域に、その容量を超えて書き込んでしまう問題です。隣接するデ...
バブルソート
隣同士を比べて交換する バブルソートは、隣り合う要素を比較し、順序が逆なら交換する操作を繰り返して整列する方法です。一回の走査で大きな値が末尾へ移るな...
バリュー・チェーン
バリューチェーン分析とは、企業の価値の連鎖と呼ばれるもので、企業が生み出す付加価値の繋がりを分類したものである。 5つの主活動と4つの支援活動からなる。...
パレート図
値が降順にプロットされた棒グラフとその累積構成比を表す折れ線グラフを組み合わせた複合グラフ。 どの問題がどの程度占めているか、また、いくつ改善すれば全...
幅優先探索
近いところから順に調べる 幅優先探索は、開始点の隣接頂点を調べ、次にその一段先を調べるように、距離の層を広げていく探索方法です。BFSと略します。先に見つ...