※上記の広告は60日以上更新のないWIKIに表示されています。更新することで広告が下部へ移動します。



チェイン法(超簡略)

データ追加

1) 追加データよりハッシュ値を求める
2) ハッシュ値より(格納する)該当エントリを求める
3) 該当エントリの最終チェインを求める
4) チェインの最後にデータを追加する

データ検索

1) 検索データよりハッシュ値を求める
2) ハッシュ値より該当エントリを求める
3) チェインを最初から最後まで検索
  ・見つかった場合~
  ・見つからなかった場合~

備考

  • データの素性やハッシュ値の求め方は考えない
  • ハッシュ値がエントリ外になるパターンは考えない
  • エントリの表現方法は考えない
  • チェインの実現方法は考えない
  • ホントは(チェーンは)ソートしといた方がいいけど、ここではパス
  • 同じ値の追加を許すか否かは考えない

チェイン法の例(その1)

前提条件

  • データは自然数とする
  • ハッシュ値は10で割った余りとする
    • 余り=格納する該当エントリになる
  • データを保持する領域は10×10の二次元配列とする
    • チェーンで繋ぐのはメンドウなので(汗
  • 各エントリの現在の格納数を示すカウンターを持つ
    • 上記は「データ無し」で初期化されている

データ追加

1) 追加する自然数を入力する
2) 上記を10で割った余りを求める
3) 該当エントリのカウンターをチェック
  ・すでに10個格納されていたら追加できない
4) 該当エントリのカウンターを1加算する
  ・ソートするならこのへんのタイミングで
5) 該当エントリのカウンターが示す位置にデータを格納する

データ検索

1) 検索する自然数を入力する
2) 上記を10で割った余りを求める
3) 該当エントリを最初からカウンター位置まで検索
  ・見つかった場合の処理
  ・見つからなかった場合の処理