ハッシュ法

ベースとなるソースコードの公開について

オープンアドレス法を用いた辞書の実装（線形探索法）

以下は，オープンアドレス法によるデータ管理を行う辞書を実現する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 を実行すると，以下のような結果が表示される．

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
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
mac$

基本課題

  1. データとして整数値をとるオープンアドレス法を用いた辞書を実現するプログラム open_addressing を実装せよ．open_addressing.c には，最低限以下の関数を定義すること．
    • DictOpenAddr *create_dict(int len): サイズ len の辞書配列を作成・初期化する．処理が完了したら，DictOpenAddr型のポインタを返す．
    • int h(DictOpenAddr *dict, int d, int count): ハッシュ関数．
      • 線形探索法に基づいたハッシュ関数として実装すること．h(dict,d,count) = (h_0(d) + count) mod Bである．ここで，h_0は任意のハッシュ関数，Bは辞書時配列の要素数．
    • 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): 辞書配列の要素を全て表示する．
      • この関数は，辞書配列の状態を1行に表示するものである．
      • 辞書配列の要素について，OCCUPIEDなら格納されている値を表示，EMPTYなら文字列"e"を表示，DELETEDなら文字列"d"を表示すること．
      • 要素間は，出力例にあるように半角空白1文字で区切って表示すること
      • 最後の要素の後には，改行を1文字表示すること．
    • void delete_dict(DictOpenAddr *dict): 辞書を破棄する．
      • 辞書が確保したメモリをすべて開放すること．
  2. その他，エラーが発生しプログラムの続行が難しい場合は，標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
    • エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．
  3. 以下の要件を全て満たすことを確認すること．
    • 辞書に整数を格納できること
    • 格納した整数を探索できること
    • 同じハッシュ値をもつ整数を，それぞれ他の配列要素に格納できること
    • 同じハッシュ値をもつ複数の整数を探索できること
    • データを挿入しようとして配列に空きがなく挿入できない時は，標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
      • エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．

オープンアドレス法を用いた辞書の実装（2重ハッシュ法）

ソースファイル double_hashing.h

#ifndef INCLUDE_GUARD_DOUBLE_HASHING_H
#define INCLUDE_GUARD_DOUBLE_HASHING_H

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

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

typedef struct dict_double_hashing {
    DictData* H;
    int B;
} DictDoubleHashing;

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

#endif  // INCLUDE_GUARD_DOUBLE_HASHING_H

ソースファイル main_double_hashing.c

/* main関数の見本は提供しない．線形走査法のコードを参考に自分で実装すること． */

int main(void) {
    return EXIT_SUCCESS;
}

発展課題

  1. 再ハッシュのためのハッシュ関数として，2重ハッシュ法（教科書 p. 56 コラムを参照）を使用したプログラム double_hashing を作成しなさい．
    • 関数h()は2重ハッシュ法の関数である．h(dict, d, count) = (h_0(d) + count * g(d, B)) mod Bとする．
    • ここで，h_0()は任意のハッシュ関数，Bは辞書配列の要素数とする．
    • また，関数g()は任意のハッシュ関数である．ただし，h_0()とは異なるものを用いること．
    • h()とg()以外の関数については，線形走査法を用いる課題の定義を参照すること．
  2. 占有率α(登録したデータ数/全バケット数)が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型で返す自作関数)．このとき，プログラムの実行を複数回行い計測した処理時間にゆらぎがないかを確認すること (繰り返し回数を多くすることによって，処理時間は収束していく)
      • 分解能よりも長い処理時間であっても，クロック関数が起動するタイミングはプログラムによって異なることから処理時間のゆらぎは起こり得るので，プログラムの実行を複数回行い計測した処理時間にゆらぎがないかを確認すること．
  3. その他，エラーが発生しプログラムの続行が難しい場合は，標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
    • エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．
  4. 以下の要件を全て満たすことを確認すること．
    • 辞書に整数を格納できること
    • 格納した整数を探索できること
    • 同じハッシュ値をもつ整数を，それぞれ他の配列要素に格納できること
    • 同じハッシュ値をもつ複数の整数を探索できること
    • データを挿入しようとして配列に空きがなく挿入できない時は，標準エラー出力にエラーメッセージを表示し，exit関数を用いてプログラムを異常終了させること．
      • エラーメッセージの文面は任意だが，発生した問題の意味がわかる文が望ましい．

時間測定について

プログラム中での時間計測は，例えば，現在時刻を秒の単位で取得する関数get_time()があるとして，以下のようにして行う．

const int numtry = 1000;
int i;

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

double elapsed_time = (end - start) / (double)(numtry);
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 関数の中身を書き換え，テストパターンを追加してください．

また，レポートには，

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

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

提出物について

自動採点の注意点

  • レポートの自動採点を行うため，以下の指示に従ってプログラムを作成，提出すること．
    • 課題中で，関数名，引数，戻り値等が指定されている場合，これらを変更しないこと．
    • 画面出力の書式は，指定されたものを守ること．

提出ファイル一覧

  • report3.pdf （レポート）
  • Makefile
  • open_addressing.c
  • open_addressing.h
  • main_open_addressing.c
  • double_hashing.c（発展課題）
  • double_hashing.h（発展課題）
  • main_double_hashing.c（発展課題）

提出ファイルの構成

  • ディレクトリ class3 を作成して，その中に上記ファイルを配置すること．
  • class3 を ZIP で圧縮した class3.zip ファイルを manaba に提出すること．
（class3.zip）の構造）
class3/
  +-report3.pdf
  +-Makefile
  +-open_addressing.c
  +-open_addressing.h
  +-main_open_addressing.c
  +-double_hashing.c
  +-double_hashing.h
  +-main_double_hashing.c

提出締切

  • 2024年11月7日（木）13:30