プログラミング技法とデータ構造

ハッシュ探索

ちょっとしたアドレス帳などのソフトウェアから本格的なデータベースシステムまで，よく使用されている探索アルゴリズムが，ハッシュ法である．ハッシュ法は，ハッシュ関数と呼ばれるキーの値から代表値(ハッシュ値と呼ぶ)を計算する関数を用いて，データの検索位置を決定する方法である．

まずデータを登録する表tableを考える，大きさは例えば100程度とし，table[100]とする．ここにデータを登録していく時点で，どの位置にデータを登録するかも，ハッシュ関数次第で決定する．検索キーに対してハッシュ関数で計算を行い，仮に18と計算されたとする．その場合には，table[18]にそのデータを登録する．逆に，データを検索するときには，検索キーを使ってまたハッシュ関数を計算し，答え18を得る．すると一発でtable[18]からデータを引き出せることになる．

例えば，五十音の電話帳に用いるハッシュ関数として単純なものでは，「あ」から始まる名前なら0，「い」なら1，などと先頭のよみだけで番号化するハッシュ関数が考えられる．他には，学籍番号をキーと考えれば，学籍番号と表の大きさの剰余(あまり)などが考えられる．

ハッシュ関数は，任意で構わないが，決定する際に問題となる点がハッシュ値の衝突(collision)である．違うキーに対するハッシュを計算した時に，同じハッシュ値が計算されることを衝突と呼ぶ．例えば，先ほどの五十音の例では，「たかはし」「たかだ」などの名前で衝突が起こる．

この衝突は，次のような具体的な問題を生じる．データ格納時に衝突が起こった場合には，格納先にすでに別のデータが格納されていることになる．また，データを探索している時には，衝突により探した先に目的のデータがないことになる．

表の大きさを，データの数と比較して十分大きくとり，ハッシュ関数の値域を広げることで衝突する頻度を減らすことができる．理論的には，限界まで表を広げられれば衝突は0になる．つまり，取りうるIDすべてを格納できる大きな表を用意できれば，衝突を0にできる．このときのハッシュ関数はなにもせず，IDそのままがハッシュ値となる．例えば日本工大の学籍番号を考えた場合，7桁の数字であるため，0番から9999999番までの表を用意できれば，衝突なしに直接必要なデータにアクセスできる．

しかし，当然そのためには膨大なメモリ量を必要とし，また現在在学している5000人程度の学生に対して，表の中の空き部分が非常に多くなり，メモリの効率があまりに悪い．ハッシュ法は，5000人の学生に対してせいぜい10000程度の大きさの表を用意し，7桁の学籍番号からハッシュ関数により0から9999までのハッシュ値に変換することで，高速な検索性能とメモリ効率の両方を満足しようとしているわけである．ちなみに，ハッシュ(hashing)とは，元々は肉を切り刻む言葉からきており，元のIDを切り刻んで小さくするイメージにより名づけられている．

衝突が起こった場合，対応の仕方によりハッシュ法はいくつかに分類される．代表的なものが，オープンアドレス法とチェーン法である．

オープンアドレス法

オープンアドレス法では，衝突が起こった場合には，再ハッシュを行う方式である．再ハッシュには，そのための別関数を用意する．別関数は任意だが，単純なものでは，元のハッシュ値に+1して表のサイズとの剰余をとったものなどがある．つまり，基本的に衝突したらとなりの場所を探させるわけである．再ハッシュしても衝突した場合には，再ハッシュを繰り返すことになる．

これにより，データを格納しようとした時にすでに別データが格納されている場合には，再ハッシュし，再ハッシュ先が空ならばそこに格納する．もしもそこも別データで埋まっていたら，空きを見つけるまで再ハッシュを繰り返す．もしも表の大きさに等しい回数再ハッシュを行っても空きが見つからない場合には，表が全部埋まっているため格納は失敗と判断させる．

データを探索する時には，ハッシュした値で探索し，目的のデータでなかった場合には，再ハッシュし，再ハッシュ先が目的のデータかどうか確認する．もしもそこも別データであったら，見つけるまで再ハッシュを繰り返す．もしも表の大きさに等しい回数再ハッシュを行っても目的のデータが見つからない場合，表が全部調べても見つからなかったとして失敗と判断させる．また，再ハッシュのいずれかで空に出会った時には，目的のデータがそもそも格納されていないとして，失敗と判断する．

チェイン法

チェイン法は，配列と線形リストを組み合わせたデータ構造を使用する．表として配列を用意するが，この表にはデータは格納せず，線形リストへのポインタを格納する．ハッシュ関数によりハッシュ値を計算し，その値によって配列の線形リストの一つを選択し，その線形リストにデータを追加する．

この方法では，衝突が起こっても，同じハッシュ値のデータを線形リストに追加したり，その線形リストをたどって探索すればよい．

スタックとキューとは

データの配列に対し，読み書きできる要素に一定のルールに従ってアクセスさせるようにプログラム内容を制限することで，機械的に分かりやすい機能を実現することもできる．スタック(stack)は，配列の末尾だけにデータを追加削除できるように制限したものである．キュー(queue)は，配列の末尾だけにデータを追加できるようにし，先頭だけからデータを取り出すことができるようにしたものである．

スタックの利用は，プログラミング言語で一般に利用されている関数呼び出しなど，特に再帰呼び出しの手法を実現するために用いられる．現代の代表的なプログラミング言語では関数呼び出しの機能を有しているため，現代のCPUはすべてスタックを実現補助するためのハードウェア機構を有している．

キューは，その名のとおり待ち行列を用いた処理を実現するためのデータ構造である．

スタックの動作

スタックにデータを登録することをプッシュ(push)，スタックからデータを取り出すことをポップ(pop)と呼ぶ．スタックはデータをプッシュした逆順に取り出すことができる．

動作例としては，スタックに「333」をプッシュする．次に「222」をプッシュする．

222

333

次にデータを一つポップすると，最後にプッシュされた「222」が取り出される．

333

そして「444」と「666」をプッシュする．

666

444

333

データを順にポップすると，プッシュされた逆順に「666」「444」「333」が取り出される．このように，データのプッシュとポップは途中不揃いの回数で行われるため，いろいろと複雑な動きをすることもある．

スタックの実現

スタックは，配列データと最後のデータが保存されている位置を示すスタックポインタにより管理される．

#define SIZE 100
typedef struct {
  int data[SIZE];
  int sp;
} STACK;

STACK stack;
stack.sp=0; //初期化

スタックポインタはポインタ変数として実現されることも，配列に対する添字を覚えておくための整数型であることもある．

push動作とpop動作は次のようになる．

void push(int val)
{
  if(stack.sp>=SIZE)
    エラー処理
  stack.data[stack.sp++] = val; //valをpush
}

int pop(void)
{
  if(stack.sp!=0)
    return stack.data[--stack.sp];
  else
    エラー処理
}

再帰呼び出し

実はC言語の関数呼び出し機能は，機械語に翻訳されるときにCPUのスタック機能を利用して実現されている．ここでは機械語の詳細については触れずに概念的な説明を行う．

例えば，次のように関数funcAの中で別の関数を呼び出すことを考える．

void funcA(void)
{
   funcB();//(1)
   funcC();//(3)
}

void funcB(void)
{
   funcD();//(2)
}

(1)を実行すると，CPUのスタックには「funcA」と「funcB」が積まれる．

funcB

funcA

次にfuncBの中でさらに(2)でfuncDが呼び出されるため，「funcC」がつまれる．

funcD

funcB

funcA

そしてfuncDが終了すると，funcDがpopされてfuncBに戻り，それからfuncBも終了するとfuncAに戻る．そして続きとして(3)でfuncCが呼び出される．

funcC

funcA

このように関数呼び出しによる動作は，論理的にスタック動作と同一である．

特に，次のように関数の中から自分自身を呼び出す再帰呼び出しを実現する際に有効である．次の関数は，再帰によりフィボナッチ数を計算する関数である．

int Fibo(int n)
{
    if(n==1 || n==2)
      return 1;
    else
      return Fibo(n-1)+Fibo(n-2);
             /* (a) */ /* (b) */
} 

例えば，Fibo(4)を計算するとすると，これもスタックを使って説明できる．先ほどとは異なり関数名Fiboは共通なので引数nの値をスタックに積むような表記とする．まず，最初のFibo(4)を計算するためにn=4がつまれ，その中で(a)の方で子にあたるFibo(3)が呼び出される．この時点ではスタックにn=3が積まれる．

n=3

n=4

次にFibo(3)を計算するために，その中で(1)のFibo(2)が呼び出される．Fibo(2)は，そのままreturn 1される．

n=2

n=3

n=4

スタックのn=2がpopされ，n=3のFibo(3)に戻り，その中の(b)にあたるFibo(1)が呼び出される．

n=1

n=3

n=4

Fibo(1)もすぐにreturn 1されて終了する．これでFibo(3)は1+1で2になって終了する．Fibo(3)すなわちFibo(4)の(a)が終了したので，今度は(b)のFibo(2)が計算される．

n=2

n=4

Fibo(2)はすぐにreturn 1されるので終了し，Fibo(4)は，2+1となり3で終了する．

キュー

キューの実現

キューは，スタックと異なり，最初に入れたデータから順に取り出していく．このため，配列を使用して実現するとデータを配列先頭から埋めていき，先頭から順に取り出していくことになる．読み出し位置と書き込み位置が，それぞれ別に存在するためポインタも二つ必要となる．

また，配列先頭から順にデータを使用していくため，使用が進むと配列末尾へ書き込み・読み込みポインタ共に一方向に配列後方へ移動していき，そのうち末尾に達することになる．このため，末尾に達したところで先頭に戻るような，リングバッファとして実現することが多い．

リングバッファの実現として，データの書き込み意味を示すtailと，読み出し位置を示すheadを用意する．初期状態では両者とも配列先頭の0を指している．この両者の大小関係だけでは，このデータが空の初期状態と，リングバッファが全部埋まってしまった状態を区別することができないため，要素数numも設定しておく．

#define SIZE 100
typedef struct 
{
  int data[SIZE];
  int head,tail;
  int num;       //登録されている数
} QUEUE;

QUEUE q;
q.tail=q.head=q.num=0; //初期化

void enqueue(int val)
{
  if(num==SIZE)
    エラー処理
  q.data[q.tail]=val;
  q.tail=(q.tail+1)%SIZE;
  q.num++;
}

int dequeue(void)
{
  int ret;
  if(num==0)
    エラー処理
  ret=q.data[q.head]
  q.head = (q.head+1)%SIZE;
  q.num--;
  return ret;
}