ハッシュ探索①（チェイン法）　解答ページ | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第６章

問題① 🔗

問題①　サンプルプログラムを改造して、ハッシュ表の状況を出力するコマンドを実装してください。

hash.c/h に関数を追加します。

/*
    ハッシュ表をダンプ
*/
void hash_dump(Hash hash)
{
    for( size_t i = 0; i < hash->size; ++i ){
        printf( "%d:", i );

        struct PPPSIntSlist_tag* elem = hash->table[i]->next;
        while( elem != NULL ){
            printf( " %d", elem->value );
            elem = elem->next;
        }

        printf( "\n" );
    }
}

問題② 🔗

問題②　ハッシュ表に登録されている要素数を返す関数を作成してください。

ppps_int_slist.h には、連結リスト内の要素数を返す関数が用意されているので、それを使ってしまえば簡単にできます。

/*
    ハッシュ表に登録されているデータの個数を返す
*/
size_t hash_count(Hash hash)
{
    size_t count = 0;

    for( size_t i = 0; i < hash->size; ++i ){
        count += ppps_int_slist_count( hash->table[i] );
    }

    return count;
}

もちろん、自力で連結リストを実装しているのなら、自力でリスト内をたどっていくことになりますが、目的の仕事をこなす道具がすでにあるのなら、それを使う方が簡単で確実です。

問題③ 🔗

問題③　次の文字列専用のハッシュ関数は、あまり良い実装ではありません。なぜでしょうか。また、どうすればより良くなるでしょうか。

size_t hash_func(Hash hash, const char* key)
{
    int h = 0;

    while( *key != '\0' ){
        h += *key;
        ++key;
    }

    return h % hash->size;
}

このハッシュ関数は、文字列を構成している各文字の文字コードの合計を計算し、ハッシュ表の要素数による剰余によって、ハッシュ値を求めています。

しかしこういう実装では、たとえば、“ABC”、“ACB”、“BAC”、“BCA”、“CAB”、“CBA” のように、文字を入れ替えただけの異なる文字列が、すべて同じハッシュ値になってしまいます。

また、ASCIIコードを前提とすると、“A”、“B”、“C” のコード値は 1ずつ異なるので、“ABC” と “BBB” のハッシュ値も同じになります。このように、異なった文字列でも同じ結果を生むことが多く、衝突の頻度が高くなってしまいます。

解決策として考えられるのは、各文字に何らかの重み付けをすることです。たとえば、各桁に 16⁰、16¹、16² といった重みを掛け合わせるのです。プログラムで書くと次のようになります。

size_t hash_func(Hash hash, const char* key)
{
    int h = 0;
    int weight = 0;

    while( *key != '\0' ){
        h += (int)(*key * pow(16.0, weight));
        
        weight = (weight + 1) % 8;  // 16^8 までいくと 32bit の上限を超える
        ++key;
    }

    return h % hash->size;
}

これなら、“ABC” と “CBA” とでは、“A” と “C” が現れる位置が異なるので、掛け合わされる重みも異なることになり、最終的なハッシュ値も異なります。

参考リンク 🔗

• Programming Place Plus　アルゴリズムとデータ構造編　参考書籍
  　– 当サイトの参考書籍一覧ページ。アルゴリズムとデータ構造に関する書籍を多数紹介。
• Programming Place Plus　アルゴリズムとデータ構造編　リンク集
  　– 当サイトの参考Webサイト集。アルゴリズムとデータ構造の全般的な学習に有益なサイトを紹介。

更新履歴 🔗

• 2019/12/10
  • 全体的に見直して、大幅に修正
• 2019/9/4
  • 対応規格を C95 から C99 へ上げる
    • コメントに // を使う
• 2019/9/3
  • 対応規格を C95 から C99 へ上げる
    • 変数宣言をブロックの先頭以外でも行う
• 2019/9/2
  • 対応規格を C95 から C99 へ上げる
    • ループ制御変数を for文の初期設定式で宣言するように修正

’2018/2/22　要素数を意味している「サイズ」について、「要素数」に表記を改めた。

’2013/6/1　練習問題③のコードで、変数key が変化しないため無限ループに陥っていたのを修正。

’2012/3/17　新規作成。

第６章のメインページへ

アルゴリズムとデータ構造編のトップページへ

Programming Place Plus のトップページへ