先頭へ戻る

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

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” のハッシュ値も同じになります。このように、異なった文字列でも同じ結果を生むことが多く、衝突の頻度が高くなってしまいます。

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

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” が現れる位置が異なるので、掛け合わされる重みも異なることになり、最終的なハッシュ値も異なります。


参考リンク


更新履歴

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

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

’2012/3/17 新規作成。



第6章のメインページへ

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

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー