【C言語】ハッシュ法についてサンプルコード付きで解説

2023-09-102024-07-27

ハッシュ法は、データを効率的に管理したり、素早く検索したりするための重要な技術です。

この記事では、ハッシュ法について基本的な概念からC言語での実装方法、そして実際の応用例までをわかりやすく解説します。

初心者の方でも理解できるように、サンプルコードや具体的な例を交えながら説明しますので、ぜひ最後まで読んでみてください。

目次から探す

ハッシュ法の基本概念

ハッシュ法とは

ハッシュ法の定義

ハッシュ法とは、データを特定のサイズの値(ハッシュ値)に変換する技術です。

このハッシュ値は、元のデータを一意に識別するために使用されます。

ハッシュ法は、主にデータの検索や管理を効率化するために利用されます。

ハッシュ法の目的と利点

ハッシュ法の主な目的は、データの検索速度を向上させることです。

具体的には、以下のような利点があります。

高速な検索: ハッシュ法を使用することで、データの検索時間を大幅に短縮できます。

特に、大量のデータを扱う場合にその効果が顕著です。

メモリ効率: ハッシュテーブルを使用することで、メモリの使用効率が向上します。

データを連続的に格納する必要がないため、メモリの断片化を防ぐことができます。

簡単なデータ管理: データの挿入や削除が容易で、動的なデータ管理が可能です。

ハッシュ関数の役割

ハッシュ関数の定義

ハッシュ関数は、任意のサイズのデータを固定サイズのハッシュ値に変換する関数です。

このハッシュ値は、元のデータの特性を反映しつつ、短い形式で表現されます。

ハッシュ関数は、データの一意性を保ちながら、効率的にデータを管理するために不可欠です。

ハッシュ関数の特性

ハッシュ関数には、いくつかの重要な特性があります。

一意性

理想的なハッシュ関数は、異なる入力データに対して異なるハッシュ値を生成します。

これにより、データの衝突(異なるデータが同じハッシュ値を持つこと)を最小限に抑えることができます。

効率性

ハッシュ関数は、計算が迅速である必要があります。

データの挿入や検索の際に、ハッシュ関数の計算がボトルネックにならないように設計されるべきです。

衝突耐性

衝突耐性とは、異なるデータが同じハッシュ値を生成する可能性を低くする特性です。

衝突が発生すると、データの検索や管理が困難になるため、ハッシュ関数はこの特性を持つことが重要です。

理想的には、衝突が発生しないように設計されるべきですが、実際には完全に衝突を避けることは難しいため、適切な衝突解決手法が必要です。

C言語におけるハッシュ法の実装

ハッシュ関数の実装

簡単なハッシュ関数の例

ハッシュ関数は、入力データを固定長のハッシュ値に変換する関数です。

ここでは、文字列を受け取り、その長さを基にした簡単なハッシュ関数を実装してみます。

#include <stdio.h>
#include <string.h>
unsigned int simple_hash(const char *str) {
    unsigned int hash = 0;
    while (*str) {
        hash += *str; // 各文字のASCII値を加算
        str++;
    }
    return hash;
}
int main() {
    const char *key = "example";
    printf("Hash value: %u\n", simple_hash(key)); // ハッシュ値を表示
    return 0;
}

この例では、文字列の各文字のASCII値を加算してハッシュ値を生成しています。

このような単純なハッシュ関数は、衝突が発生しやすいため、実際のアプリケーションではより複雑な関数を使用することが推奨されます。

ハッシュ関数の選び方

ハッシュ関数を選ぶ際には、以下のポイントを考慮する必要があります。

衝突耐性: 異なる入力が同じハッシュ値を生成することを避けるため、衝突が少ない関数を選ぶことが重要です。
計算効率: ハッシュ関数は迅速に計算できる必要があります。

特に大量のデータを扱う場合、計算時間がパフォーマンスに影響を与えます。

均等分布: ハッシュ値が均等に分布することで、ハッシュテーブルの性能が向上します。

ハッシュテーブルの実装

ハッシュテーブルは、ハッシュ法を用いてデータを格納するデータ構造です。

ここでは、基本的なハッシュテーブルの実装を行います。

ハッシュテーブルの構造体定義

まず、ハッシュテーブルの構造体を定義します。

#define TABLE_SIZE 10
typedef struct Entry {
    char *key;
    int value;
    struct Entry *next; // チェイン法による衝突解決
} Entry;
typedef struct HashTable {
    Entry **table; // エントリの配列
} HashTable;

この構造体では、各エントリがキーと値を持ち、次のエントリへのポインタを持つことで、衝突を解決します。

挿入関数の実装

次に、ハッシュテーブルにデータを挿入する関数を実装します。

HashTable *create_table() {
    HashTable *ht = malloc(sizeof(HashTable));
    ht->table = malloc(sizeof(Entry *) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL; // 初期化
    }
    return ht;
}
unsigned int hash(const char *key) {
    return simple_hash(key) % TABLE_SIZE; // ハッシュ値をテーブルサイズで割った余り
}
void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key);
    Entry *new_entry = malloc(sizeof(Entry));
    new_entry->key = strdup(key);
    new_entry->value = value;
    new_entry->next = ht->table[index]; // 先頭に追加
    ht->table[index] = new_entry;
}

この関数では、ハッシュ値を計算し、そのインデックスに新しいエントリを追加します。

検索関数の実装

次に、ハッシュテーブルからデータを検索する関数を実装します。

int search(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Entry *entry = ht->table[index];
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value; // 値を返す
        }
        entry = entry->next; // 次のエントリへ
    }
    return -1; // 見つからなかった場合
}

この関数では、指定されたキーに対応する値を返します。

見つからない場合は-1を返します。

削除関数の実装

最後に、ハッシュテーブルからデータを削除する関数を実装します。

void delete(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Entry *entry = ht->table[index];
    Entry *prev = NULL;
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            if (prev == NULL) {
                ht->table[index] = entry->next; // 先頭を削除
            } else {
                prev->next = entry->next; // 中間のエントリを削除
            }
            free(entry->key);
            free(entry);
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}

この関数では、指定されたキーに対応するエントリを削除します。

サンプルコード

完全なハッシュテーブルの実装例

以下に、ハッシュテーブルの全体的な実装例を示します。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define TABLE_SIZE 10
typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;
} Entry;
typedef struct HashTable {
    Entry **table;
} HashTable;
unsigned int simple_hash(const char *str) {
    unsigned int hash = 0;
    while (*str) {
        hash += *str;
        str++;
    }
    return hash;
}
HashTable *create_table() {
    HashTable *ht = malloc(sizeof(HashTable));
    ht->table = malloc(sizeof(Entry *) * TABLE_SIZE);
    for (int i = 0; i < TABLE_SIZE; i++) {
        ht->table[i] = NULL;
    }
    return ht;
}
unsigned int hash(const char *key) {
    return simple_hash(key) % TABLE_SIZE;
}
void insert(HashTable *ht, const char *key, int value) {
    unsigned int index = hash(key);
    Entry *new_entry = malloc(sizeof(Entry));
    new_entry->key = strdup(key);
    new_entry->value = value;
    new_entry->next = ht->table[index];
    ht->table[index] = new_entry;
}
int search(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Entry *entry = ht->table[index];
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            return entry->value;
        }
        entry = entry->next;
    }
    return -1;
}
void delete(HashTable *ht, const char *key) {
    unsigned int index = hash(key);
    Entry *entry = ht->table[index];
    Entry *prev = NULL;
    while (entry != NULL) {
        if (strcmp(entry->key, key) == 0) {
            if (prev == NULL) {
                ht->table[index] = entry->next;
            } else {
                prev->next = entry->next;
            }
            free(entry->key);
            free(entry);
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}
void free_table(HashTable *ht) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        Entry *entry = ht->table[i];
        while (entry != NULL) {
            Entry *temp = entry;
            entry = entry->next;
            free(temp->key);
            free(temp);
        }
    }
    free(ht->table);
    free(ht);
}
int main() {
    HashTable *ht = create_table();
    insert(ht, "apple", 1);
    insert(ht, "banana", 2);
    insert(ht, "orange", 3);
    printf("Value for 'apple': %d\n", search(ht, "apple")); // 1
    printf("Value for 'banana': %d\n", search(ht, "banana")); // 2
    delete(ht, "banana");
    printf("Value for 'banana' after deletion: %d\n", search(ht, "banana")); // -1
    free_table(ht);
    return 0;
}