探索アルゴリズム(ハッシュ)

連続しての投稿です

今日は探索アルゴリズムの一つのハッシュ法についてです

ハッシュ法

    基本動作

      データを格納、探索するときに順に格納するのではなく一定の条件の下で格納、探索するアルゴリズム

      このとき、条件は複数に当てはまりにくいものにする方がいい

    具体的な動作

      入力は数値、ハッシュ法を行う時の条件をある数で割ったあまりを用いるとする

      この時、あまりを求める条件にする数値は素数が適している(割り切れる数が少ない、あまりが多く確保できるなどの利点があるから)

      この時のデータ領域data[13]に数値を格納するアルゴリズムを考える

      この時13で割ったあまりをデータ格納に用いる

      入力   18の時   18%13=5  だからdata[5]に18が格納される

      入力   11の時   11%13=11  だからdata[11]に11が格納される

     また、あまりが同じ時にはオープンアドレス法を用いて格納場所を変更するなどの方法がある

      入力   5の時   5%13=5   この時data[5]にはすでに18が格納されているので次の領域data[6]に格納する

      探索についても同様の方法で行われる

      data={13,14,2,16,4,18,5,33,21,35,10,11,37}

      を探索する

      dataから14を探索  14%13=1 data[1]を確認すると14が格納されている

                                                       よって探索終了

      dataから5を探索   5%13=5   data[5]を確認すると18が格納されている

                                                     次の領域data[6]を確認すると5が格納されている

                                                     よって探索終了

    実際のソース

      ハッシュの計算を行うソースの例(C言語)

//ハッシュ関数

//main関数から入力され値 inと割ったあまりを格納する変数 iを受け取る

int hash(int in,int i){

  //入力を13で割った余りを求める
  i=in%13;

  //あまりの値を返す
  return i;
}

      格納する場所を変更するソースの例(C言語)

//オープンアドレス関数

//main関数から格納する領域data[13],入力された値 inと入力のあまり iを受け取る

void openaddress(int data[13],int in,int i){

  //iの次の値を求める

  i++;

  //次の領域が空欄("0")か確認する
  while(data[i]!=0){

    //空じゃない時は次のデータを確認する
    i++;
  }

  //空欄("0")の時に値を格納
  data[i]=in;
}

        自分が作ったソースコードはこんな感じです

    このアルゴリズムの長所と短所

      長所

         様々な動作に活用できる

         短時間で探索ができる

      短所

        データが少ない場合は計算を行うことで処理に要する時間が長くなる

        一致ではなく近隣の値を探索することはできない

ということで今日は探索アルゴリズムをまとめてみました