Index

HOME > プログラムTOP > C++


C++の壺・ハッシュ篇

　C++の基本テクニックのTipsです。ハッシュとは、データを数値に変換する手法で、データ検証やデータ検索に利用されます。ハッシュ篇では、データ検索におけるハッシュ法の基本的な用法を扱います。ハッシュを利用すると、大量のデータを高速で検索することが可能となります。
[INDEX] 　・ハッシュ関数
　・ハッシュテーブル
　・データ処理

sasaraan programming

Exposition

●ハッシュ関数

　ハッシュ関数とは、可変長のデータから固定長のデータを求める関数です。データ検索では、主に、文字列（キー）を一定範囲の数値（ハッシュ値）に変換する関数を指します。この場合、ハッシュ値は、配列の添え字（インデックス）に利用されます。
　ハッシュ関数は、同じキーからは常に同じハッシュ値を返す必要があります。また、ハッシュ値に偏りがなく、ある程度はばらつくことが求められます。通常は、素数を掛けたり割ったりすることで分布をばらつかせる演出が行われます。
　下例は、文字コードを足していくだけの単純なものです。この中で、引数 mod は用意する配列の要素数です。通常はばらつきを確保するために素数が用いられます。これにより、 0以上 要素数未満（ = 最大添え字以下）の整数値を求めることができ、直接配列の添え字として利用することが可能となります。
　このようなハッシュ関数には様々な定義の仕方があり、実際にはデータの量や性質により内容を設計していく必要があります。例えば、キー文字列が数百文字に及ぶ可能性がある時は、下記のハッシュ関数は向いていません。
// ハッシュ関数の例
#include <stdio.h>     // printf
#include <conio.h>    // getch

// ハッシュ関数
// ... 戻値 : ハッシュ値
// ... 引数 : key（キー）, mod（割る数）
unsigned int hash(char* key, int mod) {
    unsigned int n = 0;
    // 文字コードを順番に足していく
    while (key != '\0') {
        n += *key;
        key++;
    }
    return n % mod;  // 割った余りを返す
}
// main 関数
void main() {
    int nSize = 17;
    unsigned int n;

    n = hash("Monet", nSize);    // 5
    n = hash("Picasso", nSize);  // 8
    n = hash("Gogh", nSize);     // 15
    n = hash("Lautrec", nSize);  // 6
    n = hash("Sisley", nSize);      // 4
    n = hash("Chagall", nSize);    // 4
    n = hash("Seurat", nSize);    // 16
    n = hash("Dogas", nSize);     // 1

    if (getch()) return;
}

●ハッシュテーブル

　ハッシュ関数によって管理されるデータの体系をハッシュテーブルと呼びます。そのおおもとは通常の配列と変わりがありません。ハッシュ関数によって得られた整数値を配列の添え字と解し、データを配列要素として組み込みます。この要素数は、データをばらつかせるため、素数が望ましいとされています。
　また、各データはキーと値の両方を保持する必要があり、構造体やクラスが利用されます。ただし、異なる文字列（キー）でも同じハッシュ値を生成することが考えられます。前節の main 関数で、同じハッシュ値 4 を生成する "Sisley" と "Chagall" は衝突しています。この時はどちらかのデータを捨てるか、さらにデータを配列化して両方とも取り入れるか、いずれかの選択が必要です。本ページでは、各データを自己参照構造体にして、リスト構造を利用してデータを繋いでいく例（詳しくはリスト篇を参照してください）を次節に挙げています。この方法はチェイン法と呼ばれ、不定数量のデータが衝突しても安全にテーブルに格納することが可能です。

// 自己参照構造体の例
struct xdata {
　　char key[32];　 // キー
　　int value;　　　　// 値
　　xdata* next;　　// 次のデータへのポインタ
};

　右図はハッシュテーブルの概念の一例で、要素数17（素数）の配列とリスト構造化された各要素から成っています。各要素には先頭データ（自己参照構造体）へのアドレスが格納され、ない時は NULL が当てられることになります。データが衝突した時（添え字 4, 6, 11の箇所）は、リスト構造で連結していきます。
　この図からも分る通り、ハッシュテーブルでは、使われない要素の分もメモリを占有します。また、各データにはキー文字列やポインタも格納します。ハッシュテーブルは、高速検索を実現するためにメモリを大量に消費する性格を持ちますので、メモリ管理にも気を配る必要があります。このため、多くの場合、new / delete、malloc / free などを使ってデータやテーブルを動的に作成・破棄する方法が採られます。

●データ処理

　リスト構造を利用したハッシュテーブルのサンプルを以下に掲げておきます。データの登録では、既存のキーを調べ、あれば値の上書きを行っています。この時、データは、先入れ方式での登録（先頭に挿入）となります。また、データは new 演算子で動的に作成していますので、使い終わった後は delete 演算子で削除しています。
　この程度のデータ数では効果は希薄ですが、サンプルのハッシュ関数では、値に素数31 を掛けながらハッシュ値を算出して、よりばらけるようにしています。実際には莫大な量のデータを扱うことが多いので、さらに複雑で柔軟なハッシュ関数やデータ操作が求められます。 
// ハッシュテーブル

#include <stdio.h>     // printf
#include <string.h>    // strcpy
#include <conio.h>    // getch

// データ : xdata 構造体
struct xdata {
    char key[32];   // キー
    int value;        // 値
    xdata* next;    // 次のデータ
};

// テーブル : xtable 構造体
struct xtable {
    xdata** array;  // 配列
    int size;         // サイズ
};

// 関数プロトタイプ
unsigned int hash(char*, int); 
xdata* table_push(xtable*, char*, int);
xdata* table_search(xtable*, char*);
void table_clear(xtable*); 
void table_display(xtable*);

// main 関数
void main() 
{
    int i;
    const int nSize = 17;  // 要素数
    xdata* aData[nSize];   // 配列

    // テーブルの作成
    xtable oTable = {aData, nSize};

    // テーブルの初期化
    for (i=0; i<oTable.size; i++) {
        oTable.array[i] = NULL;
    }

    // データの登録
    table_push(&oTable, "Monet", 1000);
    table_push(&oTable, "Picasso", 1100);
    table_push(&oTable, "Gogh", 1200);
    table_push(&oTable, "Lautrec", 1300);
    table_push(&oTable, "Gauguin", 1400);
    table_push(&oTable, "Mattice", 1500);
    table_push(&oTable, "Sisley", 1600);
    table_push(&oTable, "Chagall", 1700);
    table_push(&oTable, "Seurat", 1800);
    table_push(&oTable, "Dogas", 1900);
    table_push(&oTable, "Pizarro", 2000);
    table_push(&oTable, "Cezanne", 2100);
    table_push(&oTable, "Renoir", 2200);
    table_push(&oTable, "Goya", 2300);
    table_push(&oTable, "Millet", 2400);

    // 全データの表示
    table_display(&oTable);

    // データの検索
    char key[32];  // 検索文字列
    xdata* p;        // データ
    strcpy(key, "Sisley");
    p = table_search(&oTable, key);
    if (p != NULL) {
        printf("%s, %d\n", key, p->value);
    }
    strcpy(key, "Renoir");
    p = table_search(&oTable, key);
    if (p != NULL) {
        printf("%s, %d\n", key, p->value);
    }

    // テーブルのクリア
    table_clear(&oTable);

    if (getch()) return;
}
// ハッシュ関数
unsigned int hash(char* key, int mod)
{
    unsigned int n = 0;
    while (*key != '\0') {
        n = n * 31 + *key;
        key++;
    }
    return n % mod;
}

// データの登録
// 戻値 : 追加（修正）したデータへのポインタ
// 引数 : table(テーブル),key(キー),value(値)
xdata* table_push(
        xtable* table, char* key, int value){
    int index = hash(key, table->size);
    xdata* curx = table->array[index];

    // データ検索（あれば上書き）
    while (curx != NULL) {
        if (strcmp(key, curx->key) == 0) {
            curx->value = value;
            return curx;
        }
        curx = curx->next;
    }

    // 新データの作成
    xdata* newx = new xdata;
    strcpy(newx->key, key);
    newx->value = value;
    newx->next = table->array[index];

    // データの付け替え
    table->array[index] = newx;
    return newx;    
}

// データの検索
// 戻値 : データへのポインタ(ない時はNULL)
// 引数 : table（テーブル）, key（キー）
xdata* table_search(xtable* table, char* key){
    int index = hash(key, table->size);
    xdata* data = table->array[index];
    while (data != NULL) {
        if ((strcmp(key, data->key)) == 0) {
            return data;
        }
        data = data->next;
    }
    return NULL;
}

// テーブルのクリア
// 引数 : table（テーブル）
void table_clear(xtable* table) {
    int i;
    for (i=0; i<table->size; i++) {
        xdata* curr = table->array[i];
        while (curr != NULL) {
            xdata* next = curr->next;
            delete curr;
            curr = next;
        }
        table->array[i] = NULL;
    }
}

// 全データの表示
void table_display(xtable* table) {
    for (int i=0; i<table->size; i++) {
        xdata* curr = table->array[i];
        while (curr != NULL) {
            printf("%s, %d\n", 
                curr->key, curr->value);
            curr = curr->next;
        }
    }
}

www.sasaraan.net

(c) morijoh