91615


現在、[AIZU ONLINE JUDEGE
ALDS1_4_C](https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/4/ALDS1_4_C)をやっています。  
その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。

以下がオープンアドレス法のコードです。

[code]

    #include <stdio.h>
    #include <string.h>
    
    using namespace std;
    using ll =long long;
    
    #define M 1000003
    #define L 14
    
    char H[M][L]; /* Hash Table */
    
    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;
    }
    
    ll GetKey(char str[]){
        ll sum=0, p=1, i;
        for (i=0; i<strlen(str); i++){
            sum += p*(GetChar(str[i]));
            p *= 5;
        }
        return sum;
    }
    
    int Hash1(ll key){ return key % M; }
    int Hash2(ll key){ return (1 + (key%(M - 1)); }
    
    int find(char str[]){
        ll key = GetKey(str);
        int k=0;
        while(true){
            int hash_index = (Hash1(key) + k*Hash2(key)) % M;
            if(strcmp(H[hash_index],str) == 0) return 1;
            if(strlen(H[hash_index]) == 0){
                return 0;
            }
            k++;
        }
        return 0;
    }
    
    int insert(char str[]){
        ll key = GetKey(str);
        int k=0;
        while(true){
            ll hash_index = (Hash1(key) + k*Hash2(key)) % M;
            if(strcmp(H[hash_index],str) == 0) return 1;
            if(strlen(H[hash_index]) == 0){
                strcpy(H[hash_index], str);
                return 1;
            }
            k++;
        }
        return 0;
    }
    
    int main(){
        int i, n;
        char str[L], com[9];
        for (i=0; i<M; i++) H[i][0] = '\0';
    
        scanf("%d", &n);
    
        for(i=0; i<n; i++){
            scanf("%s %s", com, str);
    
            if (com[0]=='i'){
                insert(str);
            }else{
                if(find(str)){
                    printf("yes\n");
                }else{
                    printf("no\n");
                }
            }
        }
    
        return 0;
    }
    
[/code]

この中で、文字を数値に変える関数`GetKey`の中でやっていることが分かりません。  
具体的には、

[code]

    sum += p*(GetChar(str[i]));
    p *= 5;
    
[/code]

このpが存在している意味が分かりません。  
似ている文字だったら、この後ハッシュ関数に変えたインデックスの値が近くなるので  
それを避けるために、文字列の数によって`p`を掛けたり、`p`を1回のループが終わるごとに５を乗算しているでしょうか？  
ネット上で、`ここで5を乗算しているのは、文字を1から4の数値に置き換えているため`というのを見たのですがどういうことか理解できません。

ご教授宜しくお願い致します。


CC BY-SA 4.0
2022-10-15T12:09:02.000
91613
2022-10-15T13:15:08.203
2022-10-15T12:44:04.310
7347
47147
question
アルゴリズム データ構造
ダブルハッシュを使用したオープンアドレス法について


簡単に言えば、ACGTからなる文字列を[文字無し]=0,A=1,C=2,G=3,T=4とした逆順の5進数とみなして、Keyとしているというものです。入力例に出てくる文字列を5進数(0pXXX)で表現すると次のようになります。

[code]

    AAA = 0p111 = 31
    AAC = 0p211 = 56 # 1文字目が1桁目に相当することに注意
    CCC = 0p222 = 62
    AGA = 0p131 = 41
    AGG = 0p331 = 91
    TTT = 0p444 = 124
    T   = 0p4   = 4
    
[/code]

上の例にあるとおり、1文字目が1桁目なので1を掛けますが、2文字目は5、3文字目は25(5*5)とn文字目には5のn乗を掛けるとなります。`p *=
5;`というのがその5のn乗の`p`ということです。

なお、この方法では文字列とKeyは1対1に対応しています。コードではKeyはハッシュ値を求める所でしか使用していませんが、Keyをそのままテーブルに入れて利用した方が比較などがより高速になるはずです。また、最大でも、12文字`TTTTTTTTTTTT`
= `0p444444444444` = `244140624`なので、`long
long`ではなく`long`でも十分のはずで、そこらへんも最適化はできそうです。


CC BY-SA 4.0
2022-10-15T13:15:08.203
91615
2022-10-15T13:15:08.203
7347
91613
answer