オープンアドレス法によるハッシュ探索

http://www.geocities.jp/ky_webid/algorithm/015.html

前回に引き続き、ハッシュ探索のお話です。

今回はオープンアドレス法という処理方法になります。

チェイン法と違って、同じ格納位置が生成されたときに元のハッシュテーブルを拡張し、データの重複を防ぎます。

しかしあれですね。そうなると僕が前回チェイン法の時に作ったハッシュ関数

int hashkey (char *s) {
    int key = 0;
    
    while(*s) {
        key += *s++;
    }
    
    return key % HASHMAX;
}

これだとあまり良くないですね。"ab"と"ba"は必ず同じハッシュ値になるのでハッシュテーブル拡張しても同じになるので処理の無駄になりそうです。

というわけで新しくハッシュ関数を考えないといけないわけですが、さすがに分からないので今回はとりあえずWikipediaに載ってるコードを参考にさせていただきます。

unsigned int hash(char *s) {
    unsigned int h = 0;
    for (;*s != '\0'; s++) {
        h = h * 137 + *s;
    }
    return h % 1987;
}

ハッシュ関数 - Wikipedia

というわけで実装してみます。

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

#define HASH_DEGAULT 8

typedef struct {
    int data;
    char key[128];
} HASHITEM;

typedef struct {
    unsigned int hashmax;
    HASHITEM *item;
} HASH;


void set_hash (HASH *hash,char *s,int data);
void create_hash(HASH *hash);
void rehash (HASH *hash);
void del_hash (HASH *hash,char *s);
int get_hash (HASH *hash,char *s);
unsigned int hashkey(HASH *hash,char *s);

unsigned int hashkey(HASH *hash,char *s) {
    unsigned int h = 0;
    for (;*s != '\0'; s++) {
        h = h * 137 + *s;
    }
    return h % hash->hashmax;
}

void create_hash(HASH *hash) {
    hash->hashmax = HASH_DEGAULT;
    hash->item = (HASHITEM *)calloc(hash->hashmax, sizeof(HASHITEM));
    if ( hash->item == NULL ) {
        return;
    }
}

void rehash (HASH *hash) {
    HASHITEM *p = hash->item;
    unsigned int max = hash->hashmax;
    unsigned int i;
    
    // ハッシュテーブルの拡張
    hash->item = (HASHITEM *)calloc(hash->hashmax <<= 1, sizeof(HASHITEM));
    if ( hash->item == NULL ) {
        return;
    }
    
    for(i=0;i<max;++i){
        if ( strlen(p[i].key) ) {
            // 既存のデータの再配置
            set_hash(hash,p[i].key,p[i].data);
        }
    }
    
    free(p);
    p = NULL;
}


void set_hash (HASH *hash,char *s,int data) {
    int key = hashkey(hash,s);
    unsigned int i;
    
    for(i=0;i<hash->hashmax;++i){
        if ( strlen(hash->item[key].key) == 0 ) {
            strcpy_s(hash->item[key].key,sizeof(hash->item[key].key),s);
            hash->item[key].data = data;
            return;
        }
        // 指定のキーが埋まってたら＋1のキーを調べる
        key = (key + 1) % hash->hashmax;
    }
    
    // 全て埋まっていたらハッシュテーブルの拡張を行う
    rehash(hash);
    set_hash(hash,s,data);
}

int get_hash (HASH *hash,char *s) {
    int key = hashkey(hash,s);
    unsigned int i;
    
    for(i=0;i<hash->hashmax;++i){
        if ( hash->item[key].key != NULL && strcmp(hash->item[key].key,s) == 0 ) {
            return hash->item[key].data;
        }
        key = (key + 1) % hash->hashmax;
    }
    
    // 無い場合どうしようか
    return 0;
}

void del_hash (HASH *hash,char *s) {
    int key = hashkey(hash,s);
    unsigned int i;
    
    for(i=0;i<hash->hashmax;++i){
        if ( hash->item[key].key != NULL && strcmp(hash->item[key].key,s) == 0 ) {
            // 削除はとりあえず\0で
            hash->item[key].key[0] = '\0';
            return;
        }
        key = (key + 1) % hash->hashmax;
    }
}

int main (void) {
    HASH hash;
    int i;
    char str[10];
    
    create_hash(&hash);
    
    // データのセット
    for(i=48;i<100;++i){
        str[0] = (char)i;
        str[1] = '\0';
        set_hash(&hash,str,i);
    }
    
    // ひとつ消してみる
    del_hash(&hash,"R");
    
    // 表示
    for(i=48;i<100;++i){
        str[0] = (char)i;
        str[1] = '\0';
        printf("%s => %d\n",str,get_hash(&hash,str));
    }
    
    return 0;
}

$ main
0 => 48
1 => 49
2 => 50
3 => 51
4 => 52
5 => 53
6 => 54
7 => 55
8 => 56
9 => 57
: => 58
; => 59
< => 60
= => 61
> => 62
? => 63
@ => 64
A => 65
B => 66
C => 67
D => 68
E => 69
F => 70
G => 71
H => 72
I => 73
J => 74
K => 75
L => 76
M => 77
N => 78
O => 79
P => 80
Q => 81
R => 0
S => 83
T => 84
U => 85
V => 86
W => 87
X => 88
Y => 89
Z => 90
[ => 91
\ => 92
] => 93
^ => 94
_ => 95
` => 96
a => 97
b => 98
c => 99

かなり難しかった・・・。色々と穴だらけではありますが何とかできました。

ひとつ微妙なのが空文字のキーが使えない部分ですね。今del_hashで削除した場合にkeyに\0を入れてるだけなので空文字のキーが渡されたらそことマッチしてしまう可能性があります。

処理の流れを軽く説明しますと、set_hashで値が設定されたときに、まずハッシュ値を割り出します。でそのハッシュ値にデータがまだ格納されてなければそこに格納します。データが格納されていればハッシュ値＋1の値が空いてるかどうかを確認し、空きが見つかるまでハッシュテーブルの大きさ分ループして検索します。そしてもし満杯まで使用していたらハッシュテーブルの拡張を行います。とりあえず今の計算方法としては2乗でやっていますが、2倍とかの方がいいのかもしれませんね。ハッシュテーブルを拡張したら今度は今まで格納されてた値の再配置を行わないといけないのでループしてset_hashを呼びます。

ざっとこんな感じですね。我ながら良く実装できたな、と感心します。