現在、AIZU ONLINE JUDEGE ALDS1_4_Cをやっています。
その中で、ダブルハッシュを使用したオープンアドレス法を学んでいます。
以下がオープンアドレス法のコードです。
#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;
}
この中で、文字を数値に変える関数GetKey
の中でやっていることが分かりません。
具体的には、
sum += p*(GetChar(str[i]));
p *= 5;
このpが存在している意味が分かりません。
似ている文字だったら、この後ハッシュ関数に変えたインデックスの値が近くなるので
それを避けるために、文字列の数によってp
を掛けたり、p
を1回のループが終わるごとに5を乗算しているでしょうか?
ネット上で、ここで5を乗算しているのは、文字を1から4の数値に置き換えているため
というのを見たのですがどういうことか理解できません。
ご教授宜しくお願い致します。