C言語 ALDS1_4_C Dictionary ハッシュ法

問題

コード

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

/* ダブルハッシュ法を使うのでハッシュテーブルのサイズは素数である必要がある */
# define HASH_TABLE_LEN 1046527

/* Hash_tableash Table */
/* グローバル宣言:ゼロクリアされているため初期化は不要 */
static char Hash_table[HASH_TABLE_LEN][13];

/* 文字列から数値に変換 */
int getChar(char ch)
{
    if (ch == 'A')
        return 1;
    else if (ch == 'C')
        return 2;
    else if (ch == 'G')
        return 3;
    else if (ch == 'T')
        return 4;

    return 0;
}

/* convert a string into an integer value */
int getKey(char str[])
{
    int str_convert = 0;
    int p = 1;
    int str_len = (int)strlen(str);

    for (int i = 0; i < str_len; i++)
    {
        str_convert += p * (getChar(str[i]));
        /* ここで5を乗算しているのは、文字を1から4の数値に置き換えているため */
        p *= 5;
    }
    return str_convert;
}

int hash_func1(int key)
{
    return key % HASH_TABLE_LEN;
}

int hash_func2(int key)
{
    /* HASH_TABLE_LENと,HASH_TABLE_LEN - 1は「互いに素」 */
    return (1 + (key % (HASH_TABLE_LEN - 1)));
}

int hash_func(int key, int i)
{
    return ((hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN);
}

int find(char str[])
{
    int key, hash_index;
    key = getKey(str);
    for (int i = 0;; i++)
    {
        hash_index = hash_func(key, i);

        /* 文字列が一致すれば1,値が格納されていなければ0 */
        if (strcmp(Hash_table[hash_index], str) == 0)
            return 1;
        else if (Hash_table[hash_index][0] == '\0')
            return 0;
    }
}

int insert(char str[])
{
    int key;
    int i;
    int hash_index;

    key = getKey(str);

    for (i = 0;; i++)
    {
        hash_index = (hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN;
        if (strcmp(Hash_table[hash_index], str) == 0)
            return 1;
        else if (strlen(Hash_table[hash_index]) == 0)
        {
            strcpy(Hash_table[hash_index], str);
            return 0;
        }
    }

    for (i = 0;; i++)
    {
        hash_index = (hash_func1(key) + i * hash_func2(key)) % HASH_TABLE_LEN;
        if (strcmp(Hash_table[hash_index], str) == 0)
            return 1;
        else if (strlen(Hash_table[hash_index]) == 0)
        {
            strcpy(Hash_table[hash_index], str);
            return 0;
        }
    }
    return 0;
}

int main()
{
    int i, N;
    char str[12];
    char order[7];

    scanf("%d", &N);
    for (i = 0; i < N; i++)
    {
        scanf("%s %s", order, str);
        if (order[0] == 'i')
            insert(str);
        else
        {
            if (find(str))
                printf("yes\n");
            else
                printf("no\n");
        }
    }
    return 0;
}

ポイント

ダブルハッシュ法注意点

• ハッシュ表の要素数と、２次ハッシュのハッシュ値とを互いに素の関係にすること。

ダブルハッシュ法の利点

• 線形探査のだとハッシュの塊（クラスター）が出来て、検索効率が下がってしまう。
• ダブルハッシュだとデータ間を広くとることができるため、クラスター化は起きにくい。

実装のポイント

• return (1 + (key % (HASH_TABLE_LEN - 1)));
• この書き方は、互いに素であり、なるべく大きい数を採用した方がクラスター化を防げるため
• +1しているのは、keyの値が(HASH_TABLE_LEN - 1)と等しいときに0が返らないようにするため。

所感

• 解答の変数が省略されていて理解しづらいため、読む過程でわかりやすい変数名に置き換えていった。
• ハッシュ関数の理解ができず、質問サイトに投げた
• 問題で取りうるパターンは2236962通り、ハッシュテーブルは1046527で圧倒的に足りない。ここのところの理解が甘いが、一旦は置いておいて前に進む。
  • 与えられる指示の最大数が1,000,000通りだからその次の素数として1046527になっていると今気づいた。
• 自分の環境だとHASH_TABLE_LEN 1046527と置いたときにすごく時間がかかる。このメモリをどれくらい使うと、遅くなるのか、という知識も持っておきたい。

参考

ハッシュ探索②（オープンアドレス法） | Programming Place Plus　アルゴリズムとデータ構造編【探索アルゴリズム】　第７章
https://programming-place.net/ppp/contents/algorithm/search/007.html#double_hasing

ネット上に落ちてたハッシュ法の解説のPDF
http://yamweb.comp.ae.keio.ac.jp/japanese/2018-A%E8%AB%96/6after%E3%83%8F%E3%83%83%E3%82%B7%E3%83%A5%E6%B3%95.pdf