お気楽Ｃ言語プログラミング超入門

ハッシュ法

今回は高速な探索アルゴリズムである「ハッシュ法 (hashing)」を取り上げます。ハッシュ法はコンパイラやインタプリタなどで、予約語、関数名、変数名などの管理に使われている方法です。また、Perl, Python, Ruby など連想配列をサポートしているスクリプト言語では、その実装にハッシュ法が使われています。

ハッシュ法は、設計をうまく行えば 1 回の比較でデータを見つけることができます。実際、コンパイラの予約語のように探索するデータが固定されている場合は、そのように設計することが可能です。不特定多数のデータが探索対象になる場合は、すべてのデータを 1 回の比較で見つけることはできませんが、数回程度の比較で見つけるように設計することは可能です。今回はＣ言語でハッシュ法のプログラムを作ってみましょう。

●ハッシュ法の仕組み

ハッシュ法は「ハッシュ表 (hash table)」と呼ばれるデータを格納する配列と、データを数値に変換する「ハッシュ関数 (hash function)」を用意します。たとえば、ハッシュ表の大きさを M とすると、ハッシュ関数はデータを 0 から M - 1 までの整数値に変換します。この値を「ハッシュ値 (hash value)」と呼びます。ハッシュ値はハッシュ表の添字に対応し、この位置にデータを格納します。つまり、ハッシュ関数によってデータを格納する位置を決める探索方法がハッシュ法なのです。

ハッシュ法で不特定多数のデータを扱う場合、異なるデータでも同じハッシュ値が生成される可能性があります。これをハッシュ値の「衝突 (collision)」といいます。つまり、データをハッシュ表に登録しようとしても、すでに先客が居座っているわけです。この場合、2 種類の解決方法があります。

第 1 の方法はハッシュ表に複数のデータを格納することです。配列には一つのデータしか格納できないので、複数個のデータをまとめて格納する工夫が必要になります。このときよく利用されるデータ構造が「連結リスト (linked list)」です。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。これを「チェイン法 (chaining)」といいます。連結リストのほかに二分木を使う方法もあります。

第 2 の方法は空いている場所を探して、そこにデータを入れる方法です。この場合、最初とは違うハッシュ関数を用意して、新しくハッシュ値を計算させて場所を決めます。この処理を空いている場所が見つかるまで繰り返します。空き場所が見つからない場合、つまりハッシュ表が満杯の場合はデータを挿入することはできません。この方法を「オープンアドレス法 (open addressing)」といいます。

●チェイン法

それでは、チェイン法から説明します。チェイン法の場合、ハッシュ表にはデータをそのまま格納しないで、連結リストへのポインタを格納します。ハッシュ表からデータを探索する場合、まずハッシュ値を求め、そこに格納されている連結リストの中からデータを探索します。

簡単な例を示しましょう。次の図を見てください。

     hash value 0 1 2 3 4 5 6
    --------------------------
                A B C D E F G
                H I J K L M N
                O P Q R S T U
                V W X Y Z

HASH TABLE 0 [        ] -> [O] -> [H] -> [A] -> NULL
           1 [        ] -> [B] -> NULL
           2 [  NULL  ]
           3 [        ] -> [Y] -> [D] -> NULL
           4 [  NULL  ]
           5 [        ] -> [M] -> [F] -> NULL
           6 [        ] -> [G] -> NULL


                図 : チェイン法

たとえば、上図のようにハッシュ関数とハッシュ表が構成されているとします。データ A の場合、ハッシュ値は 0 なのでハッシュ表の 0 の位置に格納されている連結リストを探索します。A は連結リストの中に登録されているので探索は成功です。データ C の場合、ハッシュ値は 2 ですが、ハッシュ表に連結リストがないので探索は失敗です。データ U の場合、ハッシュ値は 6 ですが、連結リストの中に U が登録されていないので探索は失敗です。

ところで、チェイン法はハッシュ値の衝突が頻繁に発生すると、データを格納する連結リストが長くなるので、探索に時間がかかることになります。効率良く探索するには、うまくハッシュ値を分散させることが必要になります。

●ハッシュ表と操作関数

それでは、チェイン法のプログラムを作りましょう。プログラムを簡単にするため、今回はキーを文字列、値を整数 (int) に限定します。最初にデータ構造を定義します。次のリストを見てください。

リスト : ハッシュ表の定義

// 連結リスト
typedef struct cell {
  char *key;
  int  value;
  struct cell *next;
} Cell;

// ハッシュ表
typedef struct {
  int size, count;
  Cell **table;
} HashTable;

構造体 Cell が連結リストのセルを表します。メンバ変数 key がキーを、value が値を格納します。next が次のセルへのポインタです。連結リストの終端は NULL で表します。構造体 HashTable がハッシュ表を表します。メンバ変数 size がハッシュ表の大きさ、count がデータ数、table がハッシュ表の本体になります。table はセルへのポインタを格納する配列になるので、データ型は Cell ** になります。

次はハッシュ表の操作関数を説明します。下表を見てください。

表 : ハッシュ表の操作関数
関数名	機能
HashTable *make_hash_table(int size);	大きさが size のハッシュ表を作成する
int search_hash(HashTable ht, const char key, bool *err);	ハッシュ表 ht からキー key を探索してその値を返す。見つからない場合は *err に false をセットして 0 を返す。
bool insert_hash(HashTable ht, const char key, int val);	ハッシュ表 ht にキー key と値 val を追加する。既存のキーは値を書き換えて false を返す。新しいキーは true を返す。
bool delete_hash(HashTable ht, const char key);	ハッシュ表 ht からキー key とその値を削除する。削除できた場合は true を返す。キーが見つからない場合は false を返す。
void foreach_hash(void (f)(const char , int), HashTable *ht);	ハッシュ表 ht に格納されているキーと値を関数 f に渡して呼び出す。
bool is_empy_hash(HashTable *ht);	ハッシュ表 ht が空ならば true を返す。
int length_hash(HashTable *ht);	ハッシュ表 ht に格納されているデータ数を返す。
void clear_hash(HashTable *ht);	ハッシュ表 ht を空にする。

関数 search_hash は key を見つけたら *err に true を、そうでなければ false をセットします。関数 insert_hash は、引数 key と同じキーを見つけた場合は、その値を引数 val に書き換えて false を返します。新規のキーであれば、key と val をハッシュ表に追加して true を返します。関数 delete_hash はキーを削除できた場合は true を、キーが見つからない場合は false を返します。あとは特に難しいところはないと思います。

●セルの生成と廃棄

次は、セルの生成と廃棄を行う関数 make_cell と delete_cell を作ります。

リスト : セルの生成と廃棄

// セルの生成
Cell *make_cell(const char *key, int val, Cell *next)
{
  Cell *cp = malloc(sizeof(Cell));
  if (cp != NULL) {
    cp->key = malloc(strlen(key) + 1);
    if (cp->key == NULL) {
      free(cp);
      return NULL;
    }
    strcpy(cp->key, key);
    cp->value = val;
    cp->next = next;
  }
  return cp;
}

// セルの廃棄
void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *xs = cp->next;
    free(cp->key);
    free(cp);
    cp = xs;
  }
}

最初に malloc で Cell 本体の領域を取得します。次に、文字列 key の領域を取得して、関数 strcpy でコピーします。あとは、メンバ変数 value と next に引数の値をセットして、return でセルを返します。セルの廃棄も簡単です。while ループでセルをたどり、文字列の領域を free(key) で解放してから、セル本体を free(cp) で解放します。

●ハッシュ表の生成と廃棄

次はハッシュ表を生成する関数 make_hash_table と廃棄する関数 delete_hash_table を作ります。

リスト : ハッシュ表の生成と廃棄

// ハッシュ表の生成
HashTable *make_hash_table(int size)
{
  HashTable *ht = malloc(sizeof(HashTable));
  if (ht != NULL) {
    ht->size = size;
    ht->table = malloc(sizeof(Cell *) * size);
    if (ht->table == NULL) {
      free(ht);
      return NULL;
    }
    // 初期化
    for (int i = 0; i < size; i++) ht->table[i] = NULL;
  }
  return ht;
}

// ハッシュ表の廃棄
void delete_hash_table(HashTable *ht)
{
  for (int i = 0; i < ht->size; i++)
    delete_cell(ht->table[i]);
  free(ht);
}

最初に malloc で HashTable 本体の領域を取得します。次に、ハッシュ表 (table) の領域を取得します。大きさは sizeof(Cell *) * size になります。Cell ではなく Cell * を指定することに注意してください。table は NULL で初期化します。HashTable を廃棄する delete_hash_table も簡単です。delete_cell で table に格納されている連結リストを廃棄してから、free(ht) で HashTable 本体を解放します。

●ハッシュ関数の作成

次は、ハッシュ値を計算する関数 hash_func を作ります。

リスト : ハッシュ関数

int hash_func(HashTable *ht, const char *key)
{
  unsigned int value = 0;
  for (; *key != '\0'; key++)
    value = (value << 3) + *key;
  return value % ht->size;
}

value を 3 ビット左シフトして、そこに *key を加算していきます。最後に、value % ht->size を返します。適当な関数ですが、これでもハッシュ法は十分に機能します。ところで、参考文献 3 ではハッシュ表の大きさを M とすると、『M を素数にしておくと安心である』とのことです。

●データの探索

次は、データの探索と挿入を行う関数 search_hash を作ります。

リスト : データの探索

// 作業用関数
Cell *search_cell(HashTable *ht, const char *key, int hval)
{
  Cell *cp = ht->table[hval];
  for (; cp != NULL; cp = cp->next) {
    if (strcmp(cp->key, key) == 0) {
      return cp;
    }
  }
  return NULL;
}

int search_hash(HashTable *ht, const char *key, bool *err)
{
  Cell *cp = search_cell(ht, key, hash_func(ht, key));
  if (cp != NULL) {
    *err = true;
    return cp->value;
  }
  *err = false;
  return 0;
}

関数 serach_cell は作業用の関数で、ハッシュ表 ht->table[hval] からキー key と等しいセルを線形探索します。見つからなければ NULL を返します。関数 search_hash は hash_func でハッシュ値を求め、それを search_cell に渡してセルを求めます。見つけた場合は *err に true をセットして、値 value を返します。見つからない場合は *err に false をセットして 0 を返します。

●データの挿入

次はデータを挿入する関数 insert_hash を作ります。

リスト : データの挿入

bool insert_hash(HashTable *ht, const char *key, int val)
{
  int hval = hash_func(ht, key);
  Cell *cp = search_cell(ht, key, hval);
  if (cp == NULL) {
    // 先頭に追加
    ht->table[hval] = make_cell(key, val, ht->table[hval]);
    ht->count++;
    return true;
  } else {
    // 値を書き換える
    cp->value = val;
    return false;
  }
}

insert_hash は search_cell で key と等しいセルを求めます。見つからない場合は新しいセルを作って連結リストの先頭に追加します。それから、count を +1 して true を返します。セルを見つけたならば、その値を引数 val に書き換えて false を返します。

●データの削除

データを削除する関数 delete はちょっとだけ複雑です。次のリストを見てください。

リスト : データの削除

bool delete_hash(HashTable *ht, const char *key)
{
  int hval = hash_func(ht, key);
  Cell *cp = ht->table[hval];
  if (cp != NULL) {
    if (strcmp(cp->key, key) == 0) {
      // 先頭データを削除
      ht->table[hval] = cp->next;
      ht->count--;
      free(cp->key);
      free(cp);
      return true;
    } else {
      // リストの途中から削除
      for (; cp->next != NULL; cp = cp->next) {
        if (strcmp(cp->next->key, key) == 0) {
          Cell *del = cp->next;
          cp->next = cp->next->next;
          ht->count--;
          free(del->key);
          free(del);
          return true;
        }
      }
    }
  }
  return false;
}

まず、hash_func でハッシュ値を求め、ハッシュ表 hash_table から先頭のセルを取り出します。cp が NULL の場合は空リストなので false を返します。そうでなければ、key を線形探索します。cp->key と key が等しい場合は、先頭のセルを削除します。これは hash_table[hval] の値を cp->next に書き換えるだけです。そうでなければ、連結リストをたどって key を探索します。見つけた場合は、cp->next の値を cp->next->next に書き換えてセルを削除します。削除したセルは free で解放することをお忘れなく。

あとのプログラムは簡単なので説明を割愛いたします。詳細はプログラムリスト１をお読みください。

●実行例１

それでは実際に実行してみましょう。次に示す簡単なテストを行ってみました。

リスト : 簡単なテスト

void test1(void)
{
  char buff[8][12];
  HashTable *ht = make_hash_table(5);
  bool err;
  printf("-- %d, %d --\n", is_empty_hash(ht), length_hash(ht));
  printf("----- insert -----\n");
  for (int i = 0; i < 8; i++) {
    sprintf(buff[i], "%d", rand());
    printf("%s, %d\n", buff[i], insert_hash(ht, buff[i], i));
  }
  printf("-- %d, %d --\n", is_empty_hash(ht), length_hash(ht));
  printf("------ search ------\n");
  for (int i = 0; i < 8; i++) 
    printf("%s, %d\n", buff[i], search_hash(ht, buff[i], &err)); 
  printf("------ delete ------\n");
  for (int i = 0; i < 8; i++) {
    printf("%s %d\n", buff[i], delete_hash(ht, buff[i]));
    int x = search_hash(ht, buff[i], &err);
    printf("%s, %d, %d\n", buff[i], x, err);
  } 
  printf("-- %d, %d --\n", is_empty_hash(ht), length_hash(ht));
  printf("----- delete hash -----\n");
  delete_hash_table(ht);
}

実行結果を示します。

$ clang hash.c
$ ./a.out
-- 1, 0 --
----- insert -----
1804289383, 1
846930886, 1
1681692777, 1
1714636915, 1
1957747793, 1
424238335, 1
719885386, 1
1649760492, 1
-- 0, 8 --
------ search ------
1804289383, 0
846930886, 1
1681692777, 2
1714636915, 3
1957747793, 4
424238335, 5
719885386, 6
1649760492, 7
------ delete ------
1804289383 1
1804289383, 0, 0
846930886 1
846930886, 0, 0
1681692777 1
1681692777, 0, 0
1714636915 1
1714636915, 0, 0
1957747793 1
1957747793, 0, 0
424238335 1
424238335, 0, 0
719885386 1
719885386, 0, 0
1649760492 1
1649760492, 0, 0
-- 1, 0 --
----- delete hash -----

ところで、ハッシュ法はハッシュ関数やハッシュ表の大きさによって、性能が大きく左右されます。興味のある方はいろいろ試してみてください。

●実行例２

もう一つ簡単な例題として、乱数で異なるキーを N 個生成する処理を作ってみましょう。生成するキーの個数が少なければ、ハッシュ法を使わなくても線形探索で十分です。プログラムは次のようになります。

リスト : 乱数による異なるキーの生成 (1)

#define N 20000
char data[N][12];

// 線形探索
bool liner_search(const char *key, int size)
{
  for (int i = 0; i < size; i++) {
    if (strcmp(key, data[i]) == 0) return true;
  }
  return false;
}

void test2(int size)
{
  int i = 0;
  while (i < size) {
    sprintf(data[i], "%d", rand());
    if (!liner_search(data[i], i)) i++;
  }
}

int main(void)
{
  for (int i = 2500; i <= N; i *= 2) {
    clock_t s = clock();
    test2(i);
    printf("%d, %.3f\n", i, (double)(clock() - s) / CLOCKS_PER_SEC);
  }
  return 0;
}

生成したキーは配列 data に格納します。関数 test2 は乱数でキーを一つ生成し、それが今まで生成したキーと異なることを関数 liner_search でチェックします。同じキーがなければ data に追加ます。liner_search は線形探索なので、個数が増えると時間がかかるようになります。実際に 2500, 5000, 10000, 20000 個のキーを作ったときの実行時間を示します。

$ clang -O2 hash.c
$ ./a.out
2500, 0.013
5000, 0.050
10000, 0.179
20000, 0.692

実行環境 : clang version 14.0.0, Ubunts 22.04 LTS (WSL2, Windows 10), Intel Core i5-6200U 2.30GHz
最適化オプション : -O2

キーの個数が増えると実行時間が大幅に増加することがわかります。それでは線形探索の代わりにハッシュ法を使ってみましょう。プログラムは次のようになります。

リスト : 乱数によるキーの生成 (2)

void test3(int size)
{
  HashTable *ht = make_hash_table(10007);
  bool err;
  char buff[12];
  while (length_hash(ht) < size) {
    sprintf(buff, "%d", rand());
    search_hash(ht, buff, &err);
    if (!err) insert_hash(ht, buff, 1);
  }
  delete_hash_table(ht);
}

ハッシュ表の大きさは 99991 (素数) としました。実行結果は次のようになります。

$ clang -O2 hash.c
$ ./a.out
2500, 0.002
5000, 0.003
10000, 0.005
20000, 0.013

ハッシュ法の方が断然速いですね。簡単なハッシュ関数を使いましたが、ハッシュ法の効果は十分に出ています。

●実行例３

次は二分探索木と比較してみましょう。二分探索木のプログラムを示します。

リスト :  二分探索木

// 節の定義
typedef struct node {
  char *key;
  int value;
  struct node *left;
  struct node *right;
} Node;

// 節の生成
Node *make_node(const char *key, int val)
{
  Node *node = malloc(sizeof(Node));
  if (node != NULL) {
    node->key = malloc(strlen(key) + 1);
    if (node->key == NULL) {
      free(node);
      return NULL;
    }
    strcpy(node->key, key);
    node->value = val;
    node->left = NULL;
    node->right = NULL;
  }
  return node;
}

// 探索
int search_node(const char *key, Node *node, bool *err)
{
  while (node != NULL) {
    int r = strcmp(key, node->key);
    if (r == 0) {
      *err = true;
      return node->value;
    } else if (r < 0)
      node = node->left;
    else
      node = node->right;
  }
  *err = false;
  return 0;
}

// 挿入
Node *insert_node(const char *key, int val, Node *node)
{
  if (node == NULL)
    return make_node(key, val);
  else {
    int r = strcmp(key, node->key);
    if (r < 0)
      node->left = insert_node(key, val, node->left);
    else if (r > 0)
      node->right = insert_node(key, val, node->right);
    return node;
  }
}

節にキー key と値 value を格納します。あとは特に難しいところはないと思います。

テストプログラムは次のようになります。

リスト : 二分探索木のテスト

void test4(int size)
{
  Node *root = NULL;
  int i = 0;
  char buff[12];
  bool err;
  while (i < size) {
    sprintf(buff, "%d", rand());
    search_node(buff, root, &err);
    if (!err) {
      root = insert_node(buff, i, root);
      i++;
    }
  }
}

キーの個数は 100000, 200000, 400000, 800000 とし、ハッシュ表のサイズは 99991 に増やしました。実行結果を示します。

  表 : 実行結果 (単位 : 秒)

 個数  : Hash  : Tree
-------+-------+-------
100000 : 0.043 : 0.127
200000 : 0.099 : 0.285
400000 : 0.267 : 0.671
800000 : 0.750 : 1.618

ハッシュ法のほうが高速ですね。二分木の場合、平衡木を使うと探索はもう少し速くなると思います。興味のある方は試してみてください。

今回はここまでです。次回はオープンアドレス法について説明します。

●プログラムリスト１

//
// hash.c : ハッシュ法 (チェイン法)
//
//          Copyright (C) 2015-2023 Makoto Hiroi
//
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
#include <time.h>

// 連結リスト
typedef struct cell {
  char *key;
  int  value;
  struct cell *next;
} Cell;

// ハッシュ表
typedef struct {
  int size, count;
  Cell **table;
} HashTable;

// セルの生成
Cell *make_cell(const char *key, int val, Cell *next)
{
  Cell *cp = malloc(sizeof(Cell));
  if (cp != NULL) {
    cp->key = malloc(strlen(key) + 1);
    if (cp->key == NULL) {
      free(cp);
      return NULL;
    }
    strcpy(cp->key, key);
    cp->value = val;
    cp->next = next;
  }
  return cp;
}

// セルの廃棄
void delete_cell(Cell *cp)
{
  while (cp != NULL) {
    Cell *xs = cp->next;
    free(cp->key);
    free(cp);
    cp = xs;
  }
}

// ハッシュ表の生成
HashTable *make_hash_table(int size)
{
  HashTable *ht = malloc(sizeof(HashTable));
  if (ht != NULL) {
    ht->size = size;
    ht->count = 0;
    ht->table = malloc(sizeof(Cell *) * size);
    if (ht->table == NULL) {
      free(ht);
      return NULL;
    }
    // 初期化
    for (int i = 0; i < size; i++) ht->table[i] = NULL;
  }
  return ht;
}

// ハッシュ表の廃棄
void delete_hash_table(HashTable *ht)
{
  for (int i = 0; i < ht->size; i++)
    delete_cell(ht->table[i]);
  free(ht);
}

// ハッシュ関数
int hash_func(HashTable *ht, const char *key)
{
  unsigned int value = 0;
  for (; *key != '\0'; key++)
    value = (value << 3) + *key;
  return value % ht->size;
}

// 作業用関数
Cell *search_cell(HashTable *ht, const char *key, int hval)
{
  Cell *cp = ht->table[hval];
  for (; cp != NULL; cp = cp->next) {
    if (strcmp(cp->key, key) == 0) {
      return cp;
    }
  }
  return NULL;
}

// 探索
int search_hash(HashTable *ht, const char *key, bool *err)
{
  Cell *cp = search_cell(ht, key, hash_func(ht, key));
  if (cp != NULL) {
    *err = true;
    return cp->value;
  }
  *err = false;
  return 0;
}

// 挿入
bool insert_hash(HashTable *ht, const char *key, int val)
{
  int hval = hash_func(ht, key);
  Cell *cp = search_cell(ht, key, hval);
  if (cp == NULL) {
    // 先頭に追加
    ht->table[hval] = make_cell(key, val, ht->table[hval]);
    ht->count++;
    return true;
  } else {
    // 値を書き換える
    cp->value = val;
    return false;
  }
}

// 削除
bool delete_hash(HashTable *ht, const char *key)
{
  int hval = hash_func(ht, key);
  Cell *cp = ht->table[hval];
  if (cp != NULL) {
    if (strcmp(cp->key, key) == 0) {
      // 先頭データを削除
      ht->table[hval] = cp->next;
      ht->count--;
      free(cp->key);
      free(cp);
      return true;
    } else {
      // リストの途中から削除
      for (; cp->next != NULL; cp = cp->next) {
        if (strcmp(cp->next->key, key) == 0) {
          Cell *del = cp->next;
          cp->next = cp->next->next;
          ht->count--;
          free(del->key);
          free(del);
          return true;
        }
      }
    }
  }
  return false;
}

// 巡回
void foreach_hash(void (*func)(const char *, int), HashTable *ht)
{
  for (int i = 0; i < ht->size; i++) {
    for (Cell *cp = ht->table[i]; cp != NULL; cp = cp->next)
      func(cp->key, cp->value);
  }
}

// ハッシュは空か
bool is_empty_hash(HashTable *ht)
{
  return ht->count == 0;
}

// 要素数を返す
int length_hash(HashTable *ht)
{
  return ht->count;
}

// ハッシュを空にする
void clear_hash(HashTable *ht)
{
  ht->count =0;
  for (int i = 0; i < ht->size; i++) {
    delete_cell(ht->table[i]);
    ht->table[i] = NULL;
  }
}

//
// 二分探索木
//

// 節の定義
typedef struct node {
  char *key;
  int value;
  struct node *left;
  struct node *right;
} Node;

// 節の生成
Node *make_node(const char *key, int val)
{
  Node *node = malloc(sizeof(Node));
  if (node != NULL) {
    node->key = malloc(strlen(key) + 1);
    if (node->key == NULL) {
      free(node);
      return NULL;
    }
    strcpy(node->key, key);
    node->value = val;
    node->left = NULL;
    node->right = NULL;
  }
  return node;
}

// 探索
int search_node(const char *key, Node *node, bool *err)
{
  while (node != NULL) {
    int r = strcmp(key, node->key);
    if (r == 0) {
      *err = true;
      return node->value;
    } else if (r < 0)
      node = node->left;
    else
      node = node->right;
  }
  *err = false;
  return 0;
}

// 挿入
Node *insert_node(const char *key, int val, Node *node)
{
  if (node == NULL)
    return make_node(key, val);
  else {
    int r = strcmp(key, node->key);
    if (r < 0)
      node->left = insert_node(key, val, node->left);
    else if (r > 0)
      node->right = insert_node(key, val, node->right);
    return node;
  }
}

// 簡単なテスト
void test1(void)
{
  char buff[8][12];
  HashTable *ht = make_hash_table(5);
  bool err;
  printf("-- %d, %d --\n", is_empty_hash(ht), length_hash(ht));
  printf("----- insert -----\n");
  for (int i = 0; i < 8; i++) {
    sprintf(buff[i], "%d", rand());
    printf("%s, %d\n", buff[i], insert_hash(ht, buff[i], i));
  }
  printf("-- %d, %d --\n", is_empty_hash(ht), length_hash(ht));
  printf("------ search ------\n");
  for (int i = 0; i < 8; i++) 
    printf("%s, %d\n", buff[i], search_hash(ht, buff[i], &err)); 
  printf("------ delete ------\n");
  for (int i = 0; i < 8; i++) {
    printf("%s %d\n", buff[i], delete_hash(ht, buff[i]));
    int x = search_hash(ht, buff[i], &err);
    printf("%s, %d, %d\n", buff[i], x, err);
  } 
  printf("-- %d, %d --\n", is_empty_hash(ht), length_hash(ht));
  printf("----- delete hash -----\n");
  delete_hash_table(ht);
}

#define N 2500
char data[N][12];

// 線形探索
bool liner_search(const char *key, int size)
{
  for (int i = 0; i < size; i++) {
    if (strcmp(key, data[i]) == 0) return true;
  }
  return false;
}

void test2(int size)
{
  int i = 0;
  while (i < size) {
    sprintf(data[i], "%d", rand());
    if (!liner_search(data[i], i)) i++;
  }
}

// ハッシュ
void test3(int size)
{
  HashTable *ht = make_hash_table(99991);  // 10007 から変更
  bool err;
  char buff[12];
  while (length_hash(ht) < size) {
    sprintf(buff, "%d", rand());
    search_hash(ht, buff, &err);
    if (!err) insert_hash(ht, buff, 1);
  }
  delete_hash_table(ht);
}

// 二分探索木
void test4(int size)
{
  Node *root = NULL;
  int i = 0;
  char buff[12];
  bool err;
  while (i < size) {
    sprintf(buff, "%d", rand());
    search_node(buff, root, &err);
    if (!err) {
      root = insert_node(buff, i, root);
      i++;
    }
  }
}

int main(void)
{
  test1();
  /*
  for (int i = 100000; i <= N; i *= 2) {
    clock_t s = clock();
    test3(i);
    printf("%d, %.3f\n", i, (double)(clock() - s) / CLOCKS_PER_SEC);
  }
  */
  return 0;
}

初版 2015 年 3 月 15 日
改訂 2023 年 4 月 2 日

Linux Programming