ハッシュ法

オープンアドレス法を用いた辞書の実装

以下は，オープンアドレス法によるデータ管理を行う辞書を実現するC言語プログラムであり，教科書リスト3.2 (p.54) をベースに実装されている． ソースコードは，open_addressing.h，open_addressing.c，main_open_addressing.c に分割されている．

サンプルコードはこちらからダウンロード可能．

ヘッダーファイル open_addressing.h

#ifndef INCLUDE_GUARD_OPEN_ADDRESSING_H
#define INCLUDE_GUARD_OPEN_ADDRESSING_H

typedef enum state {
  EMPTY,
  DELETED,
  OCCUPIED
} State;

typedef struct dict_data {
  int name;
  State state;
} DictData;

typedef struct dict_open_addr {
  DictData *H;
  int B;
} DictOpenAddr;

DictOpenAddr *create_dict(int len);
int h(DictOpenAddr *dict, int d, int count);
void insert_hash(DictOpenAddr *dict, int d);
int search_hash(DictOpenAddr *dict, int d);
void delete_hash(DictOpenAddr *dict, int d);
void display(DictOpenAddr *dict);
void delete_dict(DictOpenAddr *dict);

#endif  // INCLUDE_GUARD_OPEN_ADDRESSING_H

ソースファイル main_open_addressing.c

#include <stdio.h>
#include <stdlib.h>
#include "open_addressing.h"

int main(void) {
  DictOpenAddr *test_dict = create_dict(10);

  insert_hash(test_dict, 1);
  insert_hash(test_dict, 2);
  insert_hash(test_dict, 3);
  insert_hash(test_dict, 11);
  insert_hash(test_dict, 12);
  insert_hash(test_dict, 21);
  display(test_dict);

  printf("Search 1 ...\t%d\n", search_hash(test_dict, 1));
  printf("Search 2 ...\t%d\n", search_hash(test_dict, 2));
  printf("Search 21 ...\t%d\n", search_hash(test_dict, 21));
  printf("Search 5 ...\t%d\n", search_hash(test_dict, 5));

  delete_hash(test_dict, 3);
  display(test_dict);

  delete_hash(test_dict, 11);
  display(test_dict);

  delete_dict(test_dict);

  return EXIT_SUCCESS;
}

C言語特有の記法について簡単に説明する．

typedef enum state {
  EMPTY,
  DELETED,
  OCCUPIED
} State;

enumは一定数の定数（列挙型）を定義するためのキーワードである．上記では，State の列挙型を定義しており，State型の変数 state には、EMPTY, DELETED, OCCUPIED のいずれかの値を入れることができる．こうすることによって，データを格納する各配列要素の使用状況を表すためのラベルとして用いることができる．

コンパイルと実行

以下の内容の Makefile を作成する．

ファイル Makefile

open_addressing: open_addressing.o main_open_addressing.o

コマンドラインでmakeコマンドを実行すると，Cコンパイラによって実行ファイルが生成される． 実行ファイル open_addressing を実行すると，表示はvoid display(DictOpenAddr *dict)関数の実装によるが，例えば以下のような結果が表示される．

mac$ make
cc    -c -o open_addressing.o open_addressing.c
cc    -c -o main_open_addressing.o main_open_addressing.c
cc   open_addressing.o main_open_addressing.o   -o open_addressing
mac$ ./open_addressing
Dictionary created!
e 1 2 3 11 12 21 e e e
Search 1 ...    1
Search 2 ...    2
Search 21 ...   6
Search 5 ...    -1
e 1 2 d 11 12 21 e e e
e 1 2 d d 12 21 e e e
Dictionary deleted!
mac$

基本課題

1. データとして整数値をとるオープンアドレス法を用いた辞書を実現するプログラム open_addressing を実装せよ．open_addressing.c には，最低限以下の関数を定義すること．
   • DictOpenAddr *create_dict(int len): サイズ len の辞書配列を作成・初期化する．処理が完了したら，Dictionary created!を標準出力し，DictOpenAddr型のポインタを返す．
   • int h(DictOpenAddr *dict, int d, int count): ハッシュ関数．
   • void insert_hash(DictOpenAddr *dict, int d): データ d を辞書に挿入する．
   • int search_hash(DictOpenAddr *dict, int d): データ d が辞書内に含まれるかを探索し，該当データが存在するなら d が格納されている配列要素のインデックスを返し，存在しないなら -1 を返す．
   • void delete_hash(DictOpenAddr *dict, int d): データ d を辞書から削除する．
   • void display(DictOpenAddr *dict): 辞書配列の要素を全て表示する．具体的には，辞書配列の要素の状態がOCCUPIEDなら値を表示，EMPTYなら空であることを示す文字(たとえば'e'など)を表示，DELETEDならデータが消去されたことを示す文字(たとえば'd')を表示する．
   • void delete_dict(DictOpenAddr *dict): 辞書配列を破棄する．処理が完了したら，Dictionary deleted!を標準出力する．
2. 以下の要件を全て満たすことを確認すること．
   • 辞書に整数を格納できること
   • 格納した整数を探索できること
   • 同じハッシュ値をもつ整数を，それぞれ他の配列要素に格納できること
   • 同じハッシュ値をもつ複数の整数を探索できること
   • データを挿入しようとして，配列に空きがなく挿入できない時，その旨を標準エラー出力すること

発展課題

再ハッシュのためのハッシュ関数として，線形走査法を使用したプログラム linear_probing と2重ハッシュ法（教科書 p. 56 コラムを参照）を使用したプログラム double_hashing を作成し，占有率α(登録したデータ数/全バケット数)が0，0.1，0.2，，，1.0の場合における探索に要する実行時間をそれぞれのプログラム内で調べ，結果をグラフを用いて分析しなさい．

• 2重ハッシュ法では，2次ハッシュ関数 (教科書 p. 56 コラムにおける g(d)) が出力するハッシュ値とハッシュ表のサイズが互いに素 (両者の最大公約数が1である関係) でないと，全てのバケットを調べ尽くすことができないので注意すること
  • g(d) と ハッシュ表のサイズ B の最大公約数が k のとき，探索するバケットの総数は B/k となる
  • いくつかのハッシュ関数については，例えばここに記載がある
• 実行時間に十分な差が出るハッシュ表のサイズにすること
• 登録データは，プログラム中で乱数を生成しても、予め用意したファイルから読み込んでも構わない．ただし，ハッシュ値の衝突がおこるように，ハッシュ表のサイズよりも十分大きな範囲の数値とすること
  • たとえば，ハッシュ表のサイズがBで，登録するデータが0，1，2，，，B-2，B-1だと線形走査法ですら一度も再ハッシュすることなく全てのデータを登録することができてしまうので，そのような登録データは認めない
  • サンプルのデータを格納したファイルを添付する：dict-sample.txt
• 実行時間の計測に用いるクロック関数については特に制限しないが，clock_gettime() を推奨する．使用するクロック関数の分解能について計測前にしっかり調べておくこと (clock_gettime() の分解能は clock_getres() で調べることができる)
  • プログラムを走らせる環境によって分解能が異なることがあるので注意すること (例: clock_gettime() の分解能は MacOS と Linux とで異なる)
  • 分解能よりも短い処理時間を計測したい場合，下記のように繰り返し処理にして，全体にかかった時間を繰り返し回数で割ることで求めることができる (get_time()は秒に変換されたタイムスタンプをdouble型で返す自作関数)．このとき，プログラムの実行を複数回行い計測した処理時間にゆらぎがないかを確認すること (繰り返し回数を多くすることによって，処理時間は収束していく)
  • 分解能よりも長い処理時間であっても，クロック関数が起動するタイミングはプログラムによって異なることから処理時間のゆらぎは起こり得るので，プログラムの実行を複数回行い計測した処理時間にゆらぎがないかを確認すること．

const int trynum = 1000;
int i;

double start = get_time();
for(i = 0; i < trynum; i++) {
// ~~~~~ Do something ~~~~~
}
double end = get_time();

double elapsed_time = (end - start) / (double)(trynum);
printf("time %lf[sec]\n", elapsed_time);

タイムスタンプを取得する自作関数の実装例としては以下の様なものがある． 関数ポインタを構造体のメンバで扱うことによって，オブジェクト指向プログラミングにおけるメソッドのような振る舞いを実現している．

#include <time.h>

typedef struct timer {
  double seconds;
  double ref;
  void (*reset)(struct timer *this_timer);
  void (*start)(struct timer *this_timer);
  void (*stop)(struct timer *this_timer);
  void (*display)(struct timer *this_timer);
  double (*result)(struct timer *this_timer);
} Timer;

void timer_reset(Timer *this_timer) {
  this_timer->seconds = 0.0;
  this_timer->ref = 0.0;
  printf("Timer reset\n");
  struct timespec ts;
  clock_getres(CLOCK_MONOTONIC, &ts);
  printf("Time precision:\t%ld.%09ld sec\n", (long)ts.tv_sec, ts.tv_nsec);
}

void timer_start(Timer *this_timer) {
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  this_timer->ref = (double)(ts.tv_sec) + (double)ts.tv_nsec*1e-9;
}

void timer_stop(Timer *this_timer) {
  this_timer->seconds -= this_timer->ref;
  struct timespec ts;
  clock_gettime(CLOCK_MONOTONIC, &ts);
  this_timer->ref = (double)(ts.tv_sec) + (double)ts.tv_nsec*1e-9;
  this_timer->seconds += this_timer->ref;
}

void timer_display(Timer *this_timer) {
  printf("Elapsed time: \t%lf sec\n", this_timer->seconds);
}

double timer_result(Timer *this_timer) {
  return this_timer->seconds;
}

int main() {
  Timer stop_watch = {
    0.0,
    0.0,
    timer_reset,
    timer_start,
    timer_stop,
    timer_display,
    timer_result
  };

  stop_watch.reset(&stop_watch);
  stop_watch.start(&stop_watch);
  // ~~~~~ Do something ~~~~~
  stop_watch.stop(&stop_watch);
  stop_watch.display(&stop_watch);

  return EXIT_SUCCESS;
}

有効数字

よく「実行時間は 27.777753 usec だった」というような書き方をするレポートが出没しますが，理系の文章で 27.777753 という記述をすると どのような条件であっても 27.777753 の精度を保証する ということを意味するので，ちゃんと有効数字を適用して下さい (プレゼンスライドでこのような記述をするとかなり恥をかきます)．

たとえば，測定値が 27.777753 usec，27.679703 usec，27.890031 usec，28.100957 usec，，，の場合は有効数字 2 桁に丸め 28 (28±0.5) usec と書くべきです．どのくらいの不確かさになるかは，使用したクロック関数の精度を踏まえて判断して下さい．数値の丸め方についてはこちらを参考にしましょう．

• 注: 確認しておきますが，28 と 28.0 は別物です．28 は有効数字2桁で 28±0.5 なので，範囲は 27.5 ~ 28.5 です．28.0 は有効数字3桁で 28.0±0.05 なので，範囲は 27.95 ~ 28.05 です．

再掲：要件確認についての注意事項

要件確認するためには，各自で適宜 main 関数の中身を書き換え，テストパターンを追加してください．

また，レポートには，

• 「プログラムの入力となるデータが何で，それがプログラムのどの部分でどのようなロジックで処理されているため，このような実行結果が得られるから，要件を満たしている」という説明文
• その実行結果

の両方を書いてください．そうでないと，レポートの読み手(採点者)は，要件を満たすことを本当に確認出来ているのか判断出来ません．

提出締切 (前日・前々日は全学停電中なので注意してください！)

2022年10月31日（月）13:30