【C言語】第8章第9回：ハッシュテーブルの概念と実装

2025年1月15日 a-mun

ハッシュテーブルは、データを効率的に格納および検索するためのデータ構造です。本記事では、ハッシュテーブルの基本的な概念から実装方法、応用例までを学びます。

0. 記事の概要

この記事を読むメリット

効率的なデータ管理：ハッシュテーブルを使用して高速な検索と格納が可能になります。
応用力の向上：データ構造とアルゴリズムの深い理解が得られます。
実践的なスキル：C言語でのハッシュテーブルの実装方法を習得できます。

この記事で学べること

ハッシュテーブルの基本的な概念と特性
ハッシュ関数と衝突解決の手法
実際の実装例と動作の仕組み

活用のイメージ

ハッシュテーブルは、辞書型データ構造、キャッシュシステム、データベースのインデックスなど、さまざまな分野で使用されています。

1. ハッシュテーブルの基本

1.1 ハッシュテーブルとは？

ハッシュテーブルは、キーと値のペアを効率的に格納し、検索するためのデータ構造です。

主な特徴：

高速な検索：キーに基づいて直接値を検索できます。
キーと値：キーを使用してデータをユニークに識別します。

1.2 ハッシュ関数の役割

ハッシュ関数は、キーをハッシュ値（整数）に変換し、データを効率的に格納および検索するためのインデックスを提供します。

1.3 衝突とその解決方法

異なるキーが同じハッシュ値を持つ場合、衝突が発生します。以下の方法で解決できます：

チェイン法：ハッシュ値が同じデータをリンクリストで管理
オープンアドレッシング：別のハッシュ値を探す

2. ハッシュテーブルの実装

2.1 基本構造の定義

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define TABLE_SIZE 10

// ノードの定義
typedef struct Node {
    char key[50];
    char value[50];
    struct Node* next;
} Node;

// ハッシュテーブルの定義
typedef struct HashTable {
    Node* table[TABLE_SIZE];
} HashTable;

// ノードの作成
Node* createNode(const char* key, const char* value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    strcpy(newNode->key, key);
    strcpy(newNode->value, value);
    newNode->next = NULL;
    return newNode;
}

2.2 ハッシュ関数の実装

// ハッシュ関数
int hashFunction(const char* key) {
    int hash = 0;
    for (int i = 0; key[i] != '\0'; i++) {
        hash = (hash + key[i]) % TABLE_SIZE;
    }
    return hash;
}

2.3 データの挿入

// データの挿入
void insert(HashTable* table, const char* key, const char* value) {
    int index = hashFunction(key);
    Node* newNode = createNode(key, value);

    if (table->table[index] == NULL) {
        table->table[index] = newNode;
    } else {
        Node* temp = table->table[index];
        while (temp->next != NULL) {
            temp = temp->next;
        }
        temp->next = newNode;
    }
}

2.4 データの検索

// データの検索
char* search(HashTable* table, const char* key) {
    int index = hashFunction(key);
    Node* temp = table->table[index];
    while (temp != NULL) {
        if (strcmp(temp->key, key) == 0) {
            return temp->value;
        }
        temp = temp->next;
    }
    return NULL;
}

2.5 ハッシュテーブルの表示

// ハッシュテーブルを表示
void display(HashTable* table) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        printf("Index %d: ", i);
        Node* temp = table->table[i];
        while (temp != NULL) {
            printf("(%s, %s) -> ", temp->key, temp->value);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    HashTable table = {NULL};

    insert(&table, "name", "Alice");
    insert(&table, "age", "25");
    insert(&table, "city", "New York");

    printf("Hash Table:\n");
    display(&table);

    char* value = search(&table, "name");
    if (value != NULL) {
        printf("Search Result: %s\n", value);
    } else {
        printf("Key not found.\n");
    }

    return 0;
}

動作解説

データ構造の定義：ノードとハッシュテーブルの基本構造を定義します。
ハッシュ関数：キーをハッシュ値に変換します。
挿入操作：データを適切なインデックスに挿入します。
検索操作：キーに基づいて値を検索します。
表示操作：ハッシュテーブル全体を視覚化します。

3. 練習問題

以下の課題に挑戦して、ハッシュテーブルの理解を深めましょう。

オープンアドレッシングを使用したハッシュテーブルを実装してください。
重み付きハッシュ関数を作成して、キーの分布を改善してください。
ハッシュテーブルを動的に拡張する機能を追加してください。

4. 練習問題の解答と解説

問1の解答

// オープンアドレッシングを使用したハッシュテーブル
typedef struct {
    char key[50];
    char value[50];
    int isOccupied;
} HashTableOA;

void insertOA(HashTableOA* table, const char* key, const char* value) {
    int index = hashFunction(key);
    while (table[index].isOccupied) {
        index = (index + 1) % TABLE_SIZE;
    }
    strcpy(table[index].key, key);
    strcpy(table[index].value, value);
    table[index].isOccupied = 1;
}

char* searchOA(HashTableOA* table, const char* key) {
    int index = hashFunction(key);
    while (table[index].isOccupied) {
        if (strcmp(table[index].key, key) == 0) {
            return table[index].value;
        }
        index = (index + 1) % TABLE_SIZE;
    }
    return NULL;
}

この実装では、オープンアドレッシングを使用して衝突を解決します。

5. まとめ

本記事では、ハッシュテーブルの基本的な概念と実装方法を学びました。次回は、さらに高度なハッシュテーブルの応用について掘り下げます。